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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008275 Triangle read by rows of Stirling numbers of first kind, s(n,k), n >= 1, 1<=k<=n. 179
1, -1, 1, 2, -3, 1, -6, 11, -6, 1, 24, -50, 35, -10, 1, -120, 274, -225, 85, -15, 1, 720, -1764, 1624, -735, 175, -21, 1, -5040, 13068, -13132, 6769, -1960, 322, -28, 1, 40320, -109584, 118124, -67284, 22449, -4536, 546, -36, 1, -362880, 1026576 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

The unsigned numbers are also called Stirling cycle numbers: |s(n,k)| = number of permutations of n objects with exactly k cycles.

The unsigned numbers are also the number of permutations of 1..n with k left to right maxima (see Khovanova and Lewis, Smith).

With P(n) = the number of integer partitions of n, T(i,n) = the number of parts of the i-th partition of n, D(i,n) = the number of different parts of the i-th partition of n, p(j,i,n) = the j-th part of the i-th partition of n, m(j,i,n) = multiplicity of the j-th part of the i-th partition of n, sum_[T(i,n)=k]_{i=1}^{P(n)} = sum running from i=1 to i=p(n) but taking only partitions with T(i,n)=k parts into account, prod_{j=1}^{T(i,n)} = product running from j=1 to j=T(i,n), prod_{j=1}^{D(i,n)} = product running from j=1 to j=D(i,n) one has S1(n,k) = sum_[T(i,n)=k]_{i=1}^{P(n)} (n!/prod_{j=1}^{T(i,n)} p(j,i,n))* (1/prod_{j=1}^{D(i,n)} m(j,i,n)!). For example, S1(6,3) = 225 because n=6 has the following partitions with k=3 parts: (114), (123), (222). Their complexions are: (114): (6!/1*1*4)*(1/2!*1!) = 90, (123): (6!/1*2*3)*(1/1!*1!*1!) = 120, (222): (6!/2*2*2)*(1/3!) = 15. The sum of the complexions is 90+120+15=225=S1(6,3). - Thomas Wieder, Aug 04 2005

Row sums equal 0. - Jon Perry, Nov 14 2005

|s(n,k)| enumerates unordered n-vertex forests composed of k increasing non-plane (unordered) trees. Proof from the e.g.f. of the first column and the F. Bergeron et al. reference, especially Table 1, last row (non plane "recursive"), given in A049029. - Wolfdieter Lang, Oct 12 2007

|s(n,k)| enumerates unordered increasing n-vertex k-forests composed of k unary trees (out-degree r from {0,1}) whose vertices of depth (distance from the root) j>=0 come in j+1 colors (j=0 for the k roots). - Wolfdieter Lang, Oct 12 2007, Feb 22 2008

T(n,k) = A048993(n,k), for k=1..n. - Reinhard Zumkeller, Mar 18 2013

A refinement of the unsigned array is A036039. For an association to forests of "naturally grown" rooted non-planar trees, dispositions of flags on flagpoles, and colorings of the vertices of the complete graphs K_n, see A130534. - Tom Copeland, Mar 30 and Apr 05 2014

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.

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 93ff.

B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8. English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 32.

J. L. Cereceda, Iterative Procedure for Hypersums of Powers of Integers, Journal of Integer Sequences, 17 (2014), #14.5.3.

L. Comtet, Advanced Combinatorics, Reidel, 1974; Chapter V, also p. 310.

J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 93.

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

H. H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977; Section 2.7.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 245.

Knessl, Charles; Keller, Joseph B. Stirling number asymptotics from recursion equations using the ray method. Stud. Appl. Math. 84 (1991), no. 1, 43-56.

J. Riordan, An Introduction to Combinatorial Analysis, p. 48.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

J. Stirling, The Differential Method, London, 1749; see p. 10.

LINKS

T. D. Noe, Rows 1 to 100 of triangle, flattened.

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].

Nikita Alexeev and Peter Zograf, Hultman numbers, polygon gluings and matrix integrals, Arxiv preprint arXiv:1111.3061, 2011

Joerg Arndt, Matters Computational (The Fxtbook), p. 277

J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010, 2013

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

Hacene Belbachir and Mourad Rahmani, Alternating Sums of the Reciprocals of Binomial Coefficients, Journal of Integer Sequences, Vol. 15 (2012), #12.2.8.

Thierry Dana-Picard and David G. Zeitoun, Sequences of definite integrals, infinite series and Stirling numbers, International Journal of Mathematical Education in Science and Technology, Jun 19 2011.

R. M. Dickau, Stirling numbers of the first kind

D. B. Gruenberg, On asymptotics, Stirling numbers, Gamma function and polylogs

J. Hines, A generalization of the S-Stirling numbers, Math. Mag., 29 (1956), 200-203.

Yoshinari Inaba, Hyper-Sums of Powers of Integers and the Akiyama-Tanigawa Matrix, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.7.

Tanya Khovanova and Joel Brewster Lewis, Skyscrapers

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

D. E. Loeb, [math/9502217] A generalization of Stirling numbers

Toufik Mansour, Matthias Schork and Mark Shattuck, The Generalized Stirling and Bell Numbers Revisited, Journal of Integer Sequences, Vol. 15 (2012), #12.8.3.

B. H. Margolius, Transient and periodic solution to the time-inhomogeneous quasi-birth death process, Queueing Systems, Volume 56, Numbers 3-4 / August, 2007. [From N. J. A. Sloane, Jul 09 2009]

K. A. Penson, P. Blasiak, A. Horzela, G. H. E. Duchamp and A. I. Solomon, Laguerre-type derivatives: Dobinski relations and combinatorial identities, J. Math. Phys. vol. 50, 083512 (2009)

Raymond Scurr, Gloria Olive, Stirling numbers revisited, Discrete Math. 189 (1998), no. 1-3, 209--219. MR1637761 (99d:11019)

Mark Shattuck, Convolution identities for Stirling numbers of the first kind via involution, INTEGERS, 12, 2012, #A59. - From N. J. A. Sloane, Feb 04 2013

Warren D. Smith, Puzzle: Counting new records

R. P. Stanley, Ordering events in Minkowski space

N. M. Temme, Asymptotic estimates of Stirling numbers, Stud. Appl. Math. 89 (1993), no. 3, 233-243.

A. N., Timashev, On asymptotic expansions of Stirling numbers of the first and second kinds, (Russian) Diskret. Mat. 10 (1998), no. 3,148-159 translation in Discrete Math. Appl. 8 (1998), no. 5, 533-544.

Eric Weisstein's World of Mathematics, Permutation Cycle

Eric Weisstein's World of Mathematics, Stirling Number of the First Kind

Thomas Wieder, Comments on A008275

FORMULA

s(n, k)=s(n-1, k-1)-(n-1)*s(n-1, k), n, k >= 1; s(n, 0)=s(0, k)=0; s(0, 0)=1.

The unsigned numbers a(n, k)=|s(n, k)| satisfy a(n, k)=a(n-1, k-1)+(n-1)*a(n-1, k), n, k >= 1; a(n, 0)=a(0, k)=0; a(0, 0)=1.

E.g.f.: for m-th column (unsigned): ((-log(1-x))^m)/m!.

s(n, k) = T(n-1, k-1), n>1 and k>1, where T(n, k) is the triangle [ -1, -1, -2, -2, -3, -3, -4, -4, -5, -5, -6, -6, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, ...]and DELTA is Deléham's operator defined in A084938. The unsigned numbers are also |s(n, k)| = T(n-1, k-1), for n>0 and k>0, where T(n, k) = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...].

Sum[(-1)^(n-i) StirlingS1[n, i] binomial[i, k], {i,0,n}] == (-1)^(n-k) StirlingS1[n+1, k+1]. - Carlo Wood (carlo(AT)alinoe.com), Feb 13 2007

G.f.: S(n) = product[j=1, n, (x-j)] (i.e., (x-1)(x-2)(x-3) = x^3 - 6x^2 + 11x - 6). - Jon Perry, Nov 14 2005

a(n,k) = s(k,n) = (-1)^(k-n) * S1(k,n) = ( (-1)^(k-n) ) * ( k!/{(n-1)!*2^(k-n)} ) * [ { 1/(k-n)! }*k^(k-n-1) - { (1/6)*(1/(k-n-2)!) }*k^(k-n-2) + { (1/72)*(1/(k-n-4)!) }*k^(k-n-3) - { (1/6480)*(5/(k-n-6)! -36/(k-n-4)!) }*k^(k-n-4) + { (1/155520)*(5/(k-n-8)!-144/(k-n-6)!) }*k^(k-n-5) - { (1/6531840)*(7/(k-n-10)! -504/(k-n-8)!+2304/(k-n-6)!) }*k^(k-n-6) + { (1/1175731200)*(35/(k-n-12)!-5040/(k-n-10)!+87264/(k-n-8)!) }*k^(k-n-7) - { (1/7054387200)*(5/(k-n-14)!-1260/(k-n-12)!+52704/(k-n-10)!-186624/(k-n-8)!) }*k^(k-n-8) + { (1/338610585600)*(5/(k-n-16)!-2016/(k-n-14)!+164736/(k-n-12)!-2156544/(k-n-10)!) }*k^(k-n-9) - ..... ]. - André F. Labossière, Mar 27 2006

As lower triangular matrices A008277*A008275 = I, the identity matrix. - Tom Copeland, Apr 25 2014

EXAMPLE

|s(3,2)| = 3 for the three unordered 2-forest with 3 vertices and two increasing (non plane) trees: ((1),(2,3)), ((2),(1,3)), ((3),(1,2)).

Triangle begins:

..................................1

................................-1, 1

...............................2, -3, 1

............................-6, 11, -6, 1

.........................24, -50, 35, -10, 1

.....................-120, 274, -225, 85, -15, 1

.................720, -1764, 1624, -735, 175, -21, 1

............-5040, 13068, -13132, 6769, -1960, 322, -28, 1

......40320, -109584, 118124, -67284, 22449, -4536, 546, -36, 1

Another version of the same triangle, from Joerg Arndt, Oct 05 2009:

s(n,k) := number of permutations of n elements with exactly k cycles ("Stirling cycle numbers")

..n:...total...m=..1......2......3.....4.....5.....6....7...8...9

..1:.......1.......1

..2:.......2.......1......1

..3:.......6.......2......3......1

..4:......24.......6.....11......6.....1

..5:.....120......24.....50.....35....10.....1

..6:.....720.....120....274....225....85....15.....1

..7:....5040.....720...1764...1624...735...175....21....1

..8:...40320....5040..13068..13132..6769..1960...322...28...1

..9:..362880...40320.109584.118124.67284.22449..4536..546..36...1

|s(4,2)| = 11 for the eleven unordered 2-forest with 4 vertices, composed of two increasing (non plane) trees: ((1),((23)(24))), ((2),((13)(14)), ((3),((12)(14)), ((4),((12)(13)); ((1),(2,3,4)),((2),(1,2,3)), ((3), (1,2,4)), ((4),(1,2,3)); ((1,2),(3,4)), ((1,3),(2,4)), ((1,4),(2, 3)). - Wolfdieter Lang, Feb 22 2008

MAPLE

with (combinat):seq(seq(stirling1(n, k), k=1..n), n=1..10); # Zerinvary Lajos, Jun 03 2007

for i from 0 to 9 do seq(stirling1(i, j), j = 1 .. i) od; # Zerinvary Lajos, Nov 29 2007

MATHEMATICA

(* It appears that the following series has the Stirling numbers of the first kind as its "m" coefficients. *) Simplify[Exp[m Series[Log[x], {x, 1, 10}]]] 1+m (x-1)+1/2 (-1+m) m (x-1)^2+1/6 m (2-3 m+m^2) (x-1)^3+1/24 m (-6+11 m-6 m^2+m^3) (x-1)^4+1/120 m (24-50 m+35 m^2-10 m^3+m^4) (x-1)^5+1/720 m (-120+274 m-225 m^2+85 m^3-15 m^4+m^5) (x-1)^6+(m (720-1764 m+1624 m^2-735 m^3+175 m^4-21 m^5+m^6) (x-1)^7)/5040+(m (-5040+13068 m-13132 m^2+6769 m^3-1960 m^4+322 m^5-28 m^6+m^7) (x-1)^8)/40320+(m (40320-109584 m+118124 m^2-67284 m^3+22449 m^4-4536 m^5+546 m^6-36 m^7+m^8) (x-1)^9)/362880+(m (-362880+1026576 m-1172700 m^2+723680 m^3-269325 m^4+63273 m^5-9450 m^6+870 m^7-45 m^8+m^9) (x-1)^10)/3628800+O[x-1]^11 (* Luc Roy (luc.rg.roy(AT)gmail.com), Jul 27 2010 *)

Flatten[Table[StirlingS1[n, k], {n, 1, 10}, {k, 1, n}]][[1 ;; 47]] (* Jean-François Alcover, May 18 2011 *)

PROG

(PARI) T(n, k)=if(n<1, 0, n!*polcoeff(binomial(x, n), k))

(PARI) T(n, k)=if(n<1, 0, n!*polcoeff(polcoeff((1+x+x*O(x^n))^y, n), k))

(PARI) vecstirling(n)=Vec(factorback(vector(n-1, i, 1-i*'x))) /* (A function that returns all the s(n, k) as a vector) */ \\ Bill Allombert (Bill.Allombert(AT)math.u-bordeaux1.fr), Mar 16 2009

(Maxima) create_list(stirling1(n+1, k+1), n, 0, 30, k, 0, n); /* Emanuele Munarini, Jun 01 2012 */

(Haskell)

a008275 n k = a008275_tabl !! (n-1) !! (k-1)

a008275_row n = a008275_tabl !! (n-1)

a008275_tabl = map tail $ tail a048994_tabl

-- Reinhard Zumkeller, Mar 18 2013

CROSSREFS

Cf. A001303, A000915, A048994, A008277 (Stirling numbers of second kind), A039814-A039817, A048993, A087748.

Cf. A084938, A094216, A008276, A094262, A008277, A008278, A121632.

A130534 is a signed version.

A000142(n) = sum(|s(n, k)|) k=0..n, n >= 0.

Sequence in context: A138771 A121748 A174893 * A130534 A107416 A105613

Adjacent sequences:  A008272 A008273 A008274 * A008276 A008277 A008278

KEYWORD

sign,tabl,nice,core,changed

AUTHOR

N. J. A. Sloane

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 September 2 08:32 EDT 2014. Contains 246339 sequences.