login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000254 Unsigned Stirling numbers of first kind, s(n+1,2): a(n+1)=(n+1)*a(n)+n!.
(Formerly M2902 N1165)
110
0, 1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576, 10628640, 120543840, 1486442880, 19802759040, 283465647360, 4339163001600, 70734282393600, 1223405590579200, 22376988058521600, 431565146817638400, 8752948036761600000, 186244810780170240000 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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

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

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

a(n) is divisible by n for all composite n >= 6. a(2n) is divisible by (2n+1). - Leroy Quet, May 20 2007

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

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

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

a(n)=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

a(n)= 3* A001710(n) + 2* A001711(n-3), n>2 .. 11=3*3+2*1, 50 = 3*12+2*7. 274=3*60+2*47.... - Gary Detlefs, May 24 2010

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

a(n)/(n-1)! = ml(n) = n*ml(n-1)/(n-1)+1 for n>1. ml(n): 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

a(n) is a multiple of A025527(n). - Charles R Greathouse IV, Oct 16 2012

REFERENCES

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.

E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

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

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

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

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

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

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

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

LINKS

T. D. Noe, Table of n, a(n) for n = 0..100

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

FindStat - Combinatorial Statistic Finder, The number of cycles in the cycle decomposition of a permutation

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 31

Sergey Kitaev and Jeffrey Remmel, Simple marked mesh patterns, arXiv preprint arXiv:1201.1323, 2012

J. Scholes, 53rd Putnam 1992, Problem B5.

FORMULA

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

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

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

Also a(n) = n!*Sum 1/i, i=1..n = n!*H(n), H(n) = harmonic number = A001008/A002805.

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

E.g.f.: log(1 - x) / (x-1). (= (log(1 - x))^2 / 2 if offset 1). - Michael Somos, Feb 05 2004

a(n) = a(n-1) * (2*n - 1) - a(n-2) * (n - 1)^2, if n>1. - Michael Somos, Mar 24 2004

a(n) = A081358(n)+A092691(n). - Emeric Deutsch, Aug 12 2004

a(n) = n!*Sqrt[Sum[Sum[1/(i*j), {i, 1, n}], {j, 1, n}]]. - Alexander Adamchuk, Oct 26 2004

a(n) = n!*Sum_{k=1..n} (-1)^(k+1)*binomial(n, k)/k. - Vladeta Jovovic, Jan 29 2005

p^2 divides a(p-1) for prime p>3. a(n) = Sum[ 1/i, {i,1,n}] / Product[ 1/i, {i,1,n}]. - Alexander Adamchuk, Jul 11 2006

For n>=1, a(n)=n!*sum(1/(n-k),k=0..n-1). - Milan Janjic, Dec 14 2008

a(n) = A138772(n+1) - A159324(n). - Gary Detlefs, Jul 05 2010

a(n) = A121633(n) + A002672(n). - Gary Detlefs, Jul 18 2010

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

From Gary Detlefs, Sep 11 2010: (Start)

a(n) = (a(n-1)*(n^2-2n+1)+(n+1)!)/(n-1), n>2.

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 4n if n is prime.

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.

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)

a(n) = int((x^n-n!)*log(x)*exp(-x),x=0..infinity). - Groux Roland, Mar 28 2011

a(n) = 3*n!/2 + 2*(n-2)!*sum(k=0..n-3, binomial(k+2,2)/(n-2-k) ), n>=2. - Gary Detlefs, Sep 02 2011

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

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]

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

EXAMPLE

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

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

MAPLE

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);

a := n -> add(n!/k, k=1..n): seq(a(n), n=0..21); # Zerinvary Lajos, Jan 22 2008

MATHEMATICA

Table[ (PolyGamma[ m ]+EulerGamma) (m-1)!, {m, 1, 24} ] (* Wouter Meeussen *)

Table[ n!*HarmonicNumber[n], {n, 0, 19}] (* Robert G. Wilson v, May 21 2005 *)

Table[Sum[1/i, {i, 1, n}]/Product[1/i, {i, 1, n}], {n, 1, 30}] (* Alexander Adamchuk, Jul 11 2006 *)

Abs[StirlingS1[Range[20], 2]] (* Harvey P. Dale, Aug 16 2011 *)

PROG

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

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

(Sage) [stirling_number1(i, 2) for i in xrange(1, 22)] # Zerinvary Lajos, Jun 27 2008

CROSSREFS

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

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

Cf. A081358, A092691, A151881, A121633.

With signs: A081048.

Column 1 in triangle A008969.

Row sums of A136662.

Sequence in context: A230961 A203166 * A081048 A065048 A024335 A203009

Adjacent sequences:  A000251 A000252 A000253 * A000255 A000256 A000257

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Apr 30 1991

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 22 07:03 EST 2014. Contains 252328 sequences.