%I #121 Oct 26 2024 10:47:44

%S 1,1,3,9,31,121,523,2469,12611,69161,404663,2512769,16485691,

%T 113842301,824723643,6249805129,49416246911,406754704841,

%U 3478340425563,30845565317189,283187362333331,2687568043654521,26329932233283223,265946395403810289,2766211109503317451

%N The Gould numbers.

%C Number of permutations beginning with 21 and avoiding 1-23. - _Ralf Stephan_, Apr 25 2004

%C Originally defined as main diagonal of an array of binomial recurrence coefficients (see Gould and Quaintance). Also second-from-right diagonal of triangle A121207.

%C Starting (1, 3, 9, 31, 121, ...) = row sums of triangle A153868. - _Gary W. Adamson_, Jan 03 2009

%C Equals eigensequence of triangle A074909 (reflected). - _Gary W. Adamson_, Apr 10 2009

%C The divergent series g(x=1,m) = 1^m*1! - 2^m*2! + 3^m*3! - 4^m*4! + ..., m=>-1, is related to the sequence given above. For m=-1 this series dates back to Euler. We discovered that g(x=1,m) = (-1)^m * (A040027(m) - A000110(m+1) * A073003) with A073003 Gompertz's constant and A000110 the Bell numbers, see A163940; A040027(m = -1) = 0. - _Johannes W. Meijer_, Oct 16 2009

%C Compare the o.g.f. to the o.g.f. B(x) of the Bell numbers, where B(x) = 1 + x*B(x/(1-x))/(1-x). - _Paul D. Hanna_, Mar 23 2012

%C a(n) is the number of set partitions of {1,2,...,n+1} in which the last block is a singleton: the blocks are arranged in order of their least element. An example is given below. - _Peter Bala_, Dec 17 2014

%H Reinhard Zumkeller, <a href="/A040027/b040027.txt">Table of n, a(n) for n = 0..500</a>

%H Walaa Asakly, Aubrey Blecher, Charlotte Brennan, Arnold Knowfmacher, Toufik Mansour, and Stephan Wagner, <a href="http://dx.doi.org/10.1016/j.jmaa.2014.02.061">Set partition asymptotics and a conjecture of Gould and Quaintance</a>, Journal of Mathematical Analysis and Applications, Volume 416, Issue 2, 15 August 2014, Pages 672-682.

%H Jean-Luc Baril and José L. Ramírez, <a href="https://arxiv.org/abs/2410.15434">Some distributions in increasing and flattened permutations</a>, arXiv:2410.15434 [math.CO], 2024. See pp. 8-9,17.

%H Robert Dougherty-Bliss, <a href="https://arxiv.org/abs/2210.13520">Gosper's algorithm and Bell numbers</a>, arXiv:2210.13520 [cs.SC], 2022.

%H Robert Dougherty-Bliss, <a href="https://sites.math.rutgers.edu/~zeilberg/Theses/RobertDoughertyBlissThesis.pdf">Experimental Methods in Number Theory and Combinatorics</a>, Ph. D. Dissertation, Rutgers Univ. (2024). See p. 69.

%H Branko Dragovich, <a href="https://arxiv.org/abs/1702.02569">On Summation of p-Adic Series</a>, arXiv:1702.02569 [math.NT], 2017.

%H Branko Dragovich, Andrei Yu. Khrennikov and Natasa Z. Misic, <a href="http://arxiv.org/abs/1508.05079">Summation of p-Adic Functional Series in Integer Points</a>, arXiv:1508.05079 [math.NT], 2015.

%H B. Dragovich and N. Z. Misic, <a href="http://dx.doi.org/10.1134/S2070046614040025">p-Adic invariant summation of some p-adic functional series</a>, P-Adic Numbers, Ultrametric Analysis, and Applications, October 2014, Volume 6, Issue 4, pp 275-283.

%H H. W. Gould and Jocelyn Quaintance, <a href="https://doi.org/10.2298/AADM0702371G">A linear binomial recurrence and the Bell numbers and polynomials</a>, Applicable Analysis and Discrete Mathematics, 1 (2007), 371-385.

%H R. K. Guy, <a href="/A002186/a002186.pdf">Letters to N. J. A. Sloane, June-August 1968</a> [The letter gives the g.f. for this sequence as e^{e^x} Integral_{0..x} e^{e^t-1} dt but the correct g.f. is e^{e^x-1} Integral_0^x e^{1-e^t} dt. - _Don Knuth_, Feb 01 2018]

%H Sergey Kitaev, <a href="https://www.mat.univie.ac.at/~slc/wpapers/s48kitaev.html">Generalized pattern avoidance with additional restrictions</a>, Sem. Lothar. Combinat. B48e (2003).

%H Sergey Kitaev and Toufik Mansour, <a href="https://arxiv.org/abs/math/0205182">Simultaneous avoidance of generalized patterns</a>, arXiv:math/0205182 [math.CO], 2002.

%H Don Knuth, <a href="/A040027/a040027.txt">Email to N. J. A. Sloane</a>, Jan 29 2018

%F a(n) = b(n-2), n>1, b(n) = Sum_{k = 1..n} binomial(n, k-1)*b(n-k), b(0) = 1. - _Vladeta Jovovic_, Apr 28 2001

%F E.g.f. satisfies A'(x) = exp(x)*A(x)+1. - _N. J. A. Sloane_

%F With offset 0, e.g.f.: x + exp(exp(x)) * Integral_{t=0..x} t*exp(-exp(t)+t) dt (fits the recurrence up to n=215). - _Ralf Stephan_, Apr 25 2004

%F Recurrence: a(1)=1, a(2)=1, for n > 2, a(n) = n - 1 + Sum_{j=2..n-1} binomial(n-1, j)*a(j)) [gives a(n+1)]. - _Jon Perry_, Apr 26 2005

%F O.g.f. satisfies: A(x) = 1 + x*A( x/(1-x) ) / (1-x)^2. - _Paul D. Hanna_, Mar 23 2012

%F From _Peter Bala_, Dec 17 2014: (Start)

%F Starting from A(x) = 1 + O(x) (big Oh notation) we can get a series expansion for the o.g.f. by repeatedly applying the above functional equation of Hanna: A(x) = 1 + O(x) = 1 + x/(1-x)^2 + O(x^2) = 1 + x/(1-x)^2 + x^2/((1-x)*(1-2*x)^2) + O(x^3) = ... = 1 + x/(1-x)^2 + x^2/((1-x)*(1-2*x)^2) + x^3/((1-x)*(1-2*x)*(1-3*x)^2) + x^4/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)^2) + ....

%F a(n) = Sum_{k = 0..n} ( Sum_{j = k..n} Stirling2(j,k)*k^(n-j) ).

%F Row sums of A108458. First column of A124496. (End)

%F Conjecture: a(n) = Sum_{k = 0..n} A058006(k)*A048993(n+1, k+1) - _Velin Yanev_, Aug 31 2021

%e a(3) = 9: Arranging the blocks of the 15 set partitions of {1,2,3,4} in order of their least element we find 9 set partitions for which the last block is a singleton, namely, 123|4, 124|3, 134|2, 1|24|3, 1|23|4, 12|3|4, 13|2|4, 14|2|3, and 1|2|3|4. - _Peter Bala_, Dec 17 2014

%p A040027 := proc(n)

%p option remember;

%p if n = 0 then

%p 1;

%p else

%p add(binomial(n,k-1)*procname(n-k),k=1..n) ;

%p end if;

%p end proc: # _Johannes W. Meijer_, Oct 16 2009

%t a[0] = a[1] = 1; a[n_] := a[n] = Sum[Binomial[n, k + 1]*a[k], {k, 0, n - 1}]; Table[a[n], {n, 0, 22}] (* _Jean-François Alcover_, Jul 02 2013 *)

%t Rest[CoefficientList[Assuming[Element[x, Reals], Series[E^E^x*(ExpIntegralEi[-E^x] - ExpIntegralEi[-1]), {x, 0, 20}]], x] * Range[0, 20]!] (* _Vaclav Kotesovec_, Feb 28 2014 *)

%o (PARI) {a(n)=local(A=1+x);for(i=1,n,A=1+x*subst(A,x,x/(1-x+x*O(x^n)))/(1-x)^2);polcoeff(A,n)} /* _Paul D. Hanna_, Mar 23 2012 */

%o (Haskell)

%o a040027 n = head $ a046936_row (n + 1) -- _Reinhard Zumkeller_, Jan 01 2014

%o (Python)

%o # The function Gould_diag is defined in A121207.

%o A040027_list = lambda size: Gould_diag(2, size)

%o print(A040027_list(24)) # _Peter Luschny_, Apr 24 2016

%Y Left-hand border of triangle A046936. Cf. also A011971, A014619, A298804.

%Y Cf. A153868. - _Gary W. Adamson_, Jan 03 2009

%Y Cf. A074909. - _Gary W. Adamson_, Apr 10 2009

%Y Row sums of A163940. - _Johannes W. Meijer_, Oct 16 2009

%Y Cf. A108458 (row sums), A124496 (column 1).

%K easy,nonn,nice

%O 0,3

%A _Henry Gould_

%E Entry revised by _N. J. A. Sloane_, Dec 11 2006

%E Gould reference updated by _Johannes W. Meijer_, Aug 02 2009

%E _Don Knuth_, Jan 29 2018, suggested that this sequence should be named after H. W. Gould. - _N. J. A. Sloane_, Jan 30 2018