A000254 - OEIS

%I M2902 N1165 #321 Apr 15 2024 13:05:04

%S 0,1,3,11,50,274,1764,13068,109584,1026576,10628640,120543840,

%T 1486442880,19802759040,283465647360,4339163001600,70734282393600,

%U 1223405590579200,22376988058521600,431565146817638400,8752948036761600000,186244810780170240000

%N Unsigned Stirling numbers of first kind, s(n+1,2): a(n+1) = (n+1)*a(n) + n!.

%C Number of permutations of n+1 elements with exactly two cycles.

%C Number of cycles in all permutations of [n]. Example: a(3) = 11 because the permutations (1)(2)(3), (1)(23), (12)(3), (13)(2), (132), (123) have 11 cycles altogether. - _Emeric Deutsch_, Aug 12 2004

%C Row sums of A094310: In the symmetric group S_n, each permutation factors into k independent cycles; a(n) = sum k over S_n. - Harley Flanders (harley(AT)umich.edu), Jun 28 2004

%C The sum of the top levels of the last column over all deco polyominoes of height n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. Example: a(2)=3 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, the levels of their last columns being 2 and 1, respectively. - _Emeric Deutsch_, Aug 12 2006

%C a(n) is divisible by n for all composite n >= 6. a(2*n) is divisible by 2*n + 1. - _Leroy Quet_, May 20 2007

%C For n >= 2 the determinant of the n-1 X n-1 matrix M(i,j) = i + 2 for i = j and 1 otherwise (i,j = 1..n-1). E.g., for n = 3 the determinant of [(3, 1), (1, 4)]. See 53rd Putnam Examination, 1992, Problem B5. - _Franz Vrabec_, Jan 13 2008, Mar 26 2008

%C The numerator of the fraction when we sum (without simplification) the terms in the harmonic sequence. (1 + 1/2 = 2/2 + 1/2 = 3/2; 3/2 + 1/3 = 9/6 + 2/6 = 11/6; 11/6 + 1/4 = 44/24 + 6/24 = 50/24;...). The denominator of this fraction is n!*A000142. - _Eric Desbiaux_, Jan 07 2009

%C The asymptotic expansion of the higher order exponential integral E(x,m=2,n=1) ~ exp(-x)/x^2*(1 - 3/x + 11/x^2 - 50/x^3 + 274/x^4 - 1764/x^5 + 13068/x^6 - ...) leads to the sequence given above. See A163931 and A028421 for more information. - _Johannes W. Meijer_, Oct 20 2009

%C a(n) is the number of permutations of [n+1] containing exactly 2 cycles. Example: a(2) = 3 because the permutations (1)(23), (12)(3), (13)(2) are the only permutations of [3] with exactly 2 cycles. - Tom Woodward (twoodward(AT)macalester.edu), Nov 12 2009

%C It appears that, with the exception of n= 4, a(n) mod n = 0 if n is composite and = n-1 if n is prime. - _Gary Detlefs_, Sep 11 2010

%C a(n) is a multiple of A025527(n). - _Charles R Greathouse IV_, Oct 16 2012

%C Numerator of harmonic number H(n) = Sum_{i=1..n} 1/i when not reduced. See A001008 (Wolstenholme numbers) for the reduced numerators. - _Rahul Jha_, Feb 18 2015

%C The Stirling transform of this sequence is A222058(n) (Harmonic-geometric numbers). - _Anton Zakharov_, Aug 07 2016

%C a(n) is the (n-1)-st elementary symmetric function of the first n numbers. - _Anton Zakharov_, Nov 02 2016

%C The n-th iterated integral of log(x) is x^n * (n! * log(x) - a(n))/(n!)^2 + a polynomial of degree n-1 with arbitrary coefficients. This can be proven using the recurrence relation a(n) = (n-1)! + n*a(n-1). - _Mohsen Maesumi_, Oct 31 2018

%C Primes p such that p^3 | a(p-1) are the Wolstenholme primes A088164. - _Amiram Eldar_ and _Thomas Ordowski_, Aug 08 2019

%C Total number of left-to-right maxima (or minima) in all permutations of [n]. a(3) = 11 = 3+2+2+2+1+1: (1)(2)(3), (1)(3)2, (2)1(3), (2)(3)1, (3)12, (3)21. - _Alois P. Heinz_, Aug 01 2020

%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 833.

%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, identities 186-190.

%D N. Bleistein and R. A. Handelsman, Asymptotic Expansions of Integrals, Dover Publications, 1986, see page 2. MR0863284 (89d:41049)

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 217.

%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 226.

%D Shanzhen Gao, Permutations with Restricted Structure (in preparation).

%D K. Javorszky, Natural Orders: De Ordinibus Naturalibus, 2016, ISBN 978-3-99057-139-2.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Seiichi Manyama, <a href="/A000254/b000254.txt">Table of n, a(n) for n = 0..449</a> (terms 0..100 from T. D. Noe)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H E. Barcucci, A. Del Lungo and R. Pinzani, <a href="http://dx.doi.org/10.1016/0304-3975(95)00199-9">"Deco" polyominoes, permutations and random generation</a>, Theoretical Computer Science, 159 (1996), 29-42.

%H J.-L. Baril and S. Kirgizov, <a href="http://jl.baril.u-bourgogne.fr/Stirling.pdf">The pure descent statistic on permutations</a>, preprint, 2016.

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000031">The number of cycles in the cycle decomposition of a permutation</a>.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=31">Encyclopedia of Combinatorial Structures 31</a>.

%H Sergey Kitaev and Jeffrey Remmel, <a href="http://arxiv.org/abs/1201.1323">Simple marked mesh patterns</a>, arXiv:1201.1323 [math.CO], 2012.

%H Sergey Kitaev and Jeffrey Remmel, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Kitaev/kitaev5.html">Quadrant Marked Mesh Patterns</a>, J. Int. Seq. 15 (2012), #12.4.7.

%H Chanchal Kumar and Amit Roy, <a href="https://arxiv.org/abs/2003.10098">Integer Sequences and Monomial Ideals</a>, arXiv:2003.10098 [math.CO], 2020.

%H Mircea Merca, <a href="http://dx.doi.org/10.1007/s10998-014-0034-3">Some experiments with complete and elementary symmetric functions</a>, Periodica Mathematica Hungarica, 69 (2014), 182-189.

%H J. Riordan, <a href="/A000254/a000254.pdf">Letter of 04/11/74</a>.

%H John A. Rochowicz Jr., <a href="http://epublications.bond.edu.au/ejsie/vol8/iss2/4">Harmonic Numbers: Insights, Approximations and Applications</a>, Spreadsheets in Education (eJSiE), 8(2) (2015), Article 4.

%H N. A. Rosenberg, <a href="https://doi.org/10.1086/380416">Informativeness of genetic markers for inference of ancestry</a>, American Journal of Human Genetics 73 (2003), 1402-1422.

%H M. D. Schmidt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Schmidt/multifact.html">Generalized j-Factorial Functions, Polynomials, and Applications</a>, J. Int. Seq. 13 (2010), #10.6.7, Section 4.3.2.

%H J. Scholes, <a href="http://www.kalva.demon.co.uk/putnam/psoln/psol9211.html">53rd Putnam 1992, Problem B5</a>.

%H J. Ser, <a href="/A002720/a002720_4.pdf">Les Calculs Formels des Séries de Factorielles</a>, Gauthier-Villars, Paris, 1933 [Local copy].

%H J. Ser, <a href="/A002720/a002720.pdf">Les Calculs Formels des Séries de Factorielles</a>. (Annotated scans of some selected pages)

%H Jun Yan, <a href="https://arxiv.org/abs/2404.07958">Results on pattern avoidance in parking functions</a>, arXiv:2404.07958 [math.CO], 2024. See p. 5.

%F Let P(n,X) = (X+1)*(X+2)*(X+3)*...*(X+n); then a(n) is the coefficient of X; or a(n) = P'(n,0). - _Benoit Cloitre_, May 09 2002

%F Sum_{k > 0} a(k) * x^k/ k!^2 = exp(x) *(Sum_{k>0} (-1)^(k+1) * x^k / (k * k!)). - _Michael Somos_, Mar 24 2004; corrected by _Warren D. Smith_, Feb 12 2006

%F a(n) is the coefficient of x^(n+2) in (-log(1-x))^2, multiplied by (n+2)!/2.

%F a(n) = n! * Sum_{i=1..n} 1/i = n! * H(n), where H(n) = A001008(n)/A002805(n) is the n-th harmonic number.

%F a(n) ~ 2^(1/2)*Pi^(1/2)*log(n)*n^(1/2)*e^-n*n^n. - Joe Keane (jgk(AT)jgk.org), Jun 06 2002

%F E.g.f.: log(1 - x) / (x-1). (= (log(1 - x))^2 / 2 if offset 1). - _Michael Somos_, Feb 05 2004

%F D-finite with recurrence: a(n) = a(n-1) * (2*n - 1) - a(n-2) * (n - 1)^2, if n > 1. - _Michael Somos_, Mar 24 2004

%F a(n) = A081358(n)+A092691(n). - _Emeric Deutsch_, Aug 12 2004

%F a(n) = n!*Sum_{k=1..n} (-1)^(k+1)*binomial(n, k)/k. - _Vladeta Jovovic_, Jan 29 2005

%F p^2 divides a(p-1) for prime p > 3. a(n) = (Sum_{i=1..n} 1/i) / Product_{i=1..n} 1/i. - _Alexander Adamchuk_, Jul 11 2006

%F a(n) = 3* A001710(n) + 2* A001711(n-3) for n > 2; e.g., 11 = 3*3 + 2*1, 50 = 3*12 + 2*7, 274 = 3*60 + 2*47, ... - _Gary Detlefs_, May 24 2010

%F a(n) = A138772(n+1) - A159324(n). - _Gary Detlefs_, Jul 05 2010

%F a(n) = A121633(n) + A002672(n). - _Gary Detlefs_, Jul 18 2010

%F a(n+1) = Sum_{i=1..floor((n-1)/2)} n!/((n-i)*i) + Sum_{i=ceiling(n/2)..floor(n/2)} n!/(2*(n-i)*i). - _Shanzhen Gao_, Sep 14 2010

%F From _Gary Detlefs_, Sep 11 2010: (Start)

%F a(n) = (a(n-1)*(n^2 - 2*n + 1) + (n + 1)!)/(n - 1) for n > 2.

%F It appears that, with the exception of n = 2, (a(n+1)^2 - a(n)^2) mod n^2 = 0 if n is composite and 4*n if n is prime.

%F It appears that, with the exception of n = 2, (a(n+1)^3 - a(n)^2) mod n = 0 if n is composite and n - 2 if n is prime.

%F It appears that, with the exception of n = 2, (a(n)^2 + a(n+1)^2) mod n = 0 if n is composite and = 2 if n is prime. (End)

%F a(n) = Integral_{x=0..oo} (x^n - n!)*log(x)*exp(-x) dx. - _Groux Roland_, Mar 28 2011

%F a(n) = 3*n!/2 + 2*(n-2)!*Sum_{k=0..n-3} binomial(k+2,2)/(n-2-k) for n >= 2. - _Gary Detlefs_, Sep 02 2011

%F a(n)/(n-1)! = ml(n) = n*ml(n-1)/(n-1) + 1 for n > 1, where ml(n) is the average number of random draws from an n-set with replacement until the total set has been observed. G.f. of ml: x*(1 - log(1 - x))/(1 - x)^2. - _Paul Weisenhorn_, Nov 18 2011

%F a(n) = det(|S(i+2, j+1)|, 1 <= i,j <= n-2), where S(n,k) are Stirling numbers of the second kind. - _Mircea Merca_, Apr 06 2013

%F E.g.f.: x/(1 - x)*E(0)/2, where E(k) = 2 + E(k+1)*x*(k + 1)/(k + 2). - _Sergei N. Gladkovskii_, Jun 01 2013 [Edited by _Michael Somos_, Nov 28 2013]

%F 0 = a(n) * (a(n+4) - 6*a(n+3) + 7*a(n+2) - a(n+1)) - a(n+1) * (4*a(n+3) - 6*a(n+2) + a(n+1)) + 3*a(n+2)^2 unless n=0. - _Michael Somos_, Nov 28 2013

%F For a simple way to calculate the sequence, multiply n! by the integral from 0 to 1 of (1 - x^n)/(1 - x) dx. - _Rahul Jha_, Feb 18 2015

%F From _Ilya Gutkovskiy_, Aug 07 2016: (Start)

%F Inverse binomial transform of A073596.

%F a(n) ~ sqrt(2*Pi*n) * n^n * (log(n) + gamma)/exp(n), where gamma is the Euler-Mascheroni constant A001620. (End)

%F a(n) = ((-1)^(n+1)/2*(n+1))*Sum_{k=1..n} k*Bernoulli(k-1)*Stirling1(n,k). - _Vladimir Kruchinin_, Nov 20 2016

%F a(n) = (n)! * (digamma(n+1) + gamma), where gamma is the Euler-Mascheroni constant A001620. - _Pedro Caceres_, Mar 10 2018

%F From _Andy Nicol_, Oct 21 2021: (Start)

%F Gamma'(x) = a(x-1) - (x-1)!*gamma, where Gamma'(x) is the derivative of the gamma function at positive integers and gamma is the Euler-Mascheroni constant. E.g.:

%F Gamma'(1) = -gamma, Gamma'(2) = 1-gamma, Gamma'(3) = 3-2*gamma,

%F Gamma'(22) = 186244810780170240000 - 51090942171709440000*gamma. (End)

%F From _Peter Bala_, Feb 03 2022: (Start)

%F The following are all conjectural:

%F E.g.f.: for nonzero m, (1/m)*Sum_{n >= 1} (-1)^(n+1)*(1/n)*binomial(m*n,n)* x^n/(1 - x)^(m*n+1) = x + 3*x^2/2! + 11*x^3/3! + 50*x^4/4! + ....

%F For nonzero m, a(n) = (1/m)*n!*Sum_{k = 1..n} (-1)^(k+1)*(1/k)*binomial(m*k,k)* binomial(n+(m-1)*k,n-k).

%F a(n)^2 = (1/2)*n!^2*Sum_{k = 1..n} (-1)^(k+1)*(1/k^2)*binomial(n,k)* binomial(n+k,k). (End)

%F From _Mélika Tebni_, Jun 20 2022: (Start)

%F a(n) = -Sum_{k=0..n} k!*A021009(n, k+1).

%F a(n) = Sum_{k=0..n} k!*A094587(n, k+1). (End)

%F a(n) = n! * 1/(1 - 1^2/(3 - 2^2/(5 - 3^2/(7 - ... - (n - 1)^2/((2*n - 1)))))). - _Peter Bala_, Mar 16 2024

%e (1-x)^-1 * (-log(1-x)) = x + 3/2*x^2 + 11/6*x^3 + 25/12*x^4 + ...

%e G.f. = x + x^2 + 5*x^3 + 14*x^4 + 94*x^5 + 444*x^6 + 3828*x^7 + 25584*x^8 + ...

%p A000254 := proc(n) option remember; if n<=1 then n else n*A000254(n-1)+(n-1)!; fi; end: seq(A000254(n),n=0..21);

%p a := n -> add(n!/k, k=1..n): seq(a(n), n=0..21); # _Zerinvary Lajos_, Jan 22 2008

%t Table[ (PolyGamma[ m ]+EulerGamma) (m-1)!, {m, 1, 24} ] (* _Wouter Meeussen_ *)

%t Table[ n!*HarmonicNumber[n], {n, 0, 19}] (* _Robert G. Wilson v_, May 21 2005 *)

%t Table[Sum[1/i,{i,1,n}]/Product[1/i,{i,1,n}],{n,1,30}] (* _Alexander Adamchuk_, Jul 11 2006 *)

%t Abs[StirlingS1[Range[20],2]] (* _Harvey P. Dale_, Aug 16 2011 *)

%t Table[Gamma'[n + 1] /. EulerGamma -> 0, {n, 0, 30}] (* _Li Han_, Feb 14 2024*)

%o (MuPAD) A000254 := proc(n) begin n*A000254(n-1)+fact(n-1) end_proc: A000254(1) := 1:

%o (PARI) {a(n) = if( n<0, 0, (n+1)! / 2 * sum( k=1, n, 1 / k / (n+1-k)))} /* _Michael Somos_, Feb 05 2004 */

%o (Sage) [stirling_number1(i, 2) for i in range(1, 22)]  # _Zerinvary Lajos_, Jun 27 2008

%o (Maxima)

%o a(n):=(-1)^(n+1)/2*(n+1)*sum(k*bern(k-1)*stirling1(n,k),k,1,n); /* _Vladimir Kruchinin_, Nov 20 2016 */

%o (Magma) a:=[]; for n in [1..22] do a:=a cat [Abs(StirlingFirst(n,2))]; end for; a; // _Marius A. Burtea_, Jan 01 2020

%Y Cf. A000399, A000454, A000482, A001233, A001234, A243569, A243570.

%Y Cf. A000774, A004041, A024167, A046674, A049034, A008275.

%Y Cf. A021009, A081358, A092691, A094587, A151881, A121633.

%Y With signs: A081048.

%Y Column 1 in triangle A008969.

%Y Row sums of A136662.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_