1,4

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

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.

Das, Sajal K., Joydeep Ghosh, and Narsingh Deo. "Stirling networks: a versatile combinatorial topology for multiprocessor systems." Discrete applied mathematics 37 (1992): 119-146.

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.

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.

Tom Copeland, A Class of Differential Operators and the Stirling Numbers

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

D. E. Knuth, Convolution polynomials, The Mathematica J., 2 (1992), 67-78.

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

M. Z. Spivey, A generalized recurrence for Bell Numbers, JIS 11 (2008) 08.2.5

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

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

a(n,k) = s(n,k) = limit as y tends to zero of sum(j=0 to k) (-1)^j binom(k,j) [(-j*y)!/(-j*y-n)!] y^(-k)/k! = sum(j=0 to k) (-1)^(n-j) binom(k,j) [(j*y - 1 + n)!/(j*y-1)!] y^(-k)/k!. - Tom Copeland, Aug 28 2015

|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

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

(* 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 *)

(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

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. A087755 gives triangle mod 2.

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

sign,tabl,nice,core,changed

N. J. A. Sloane

approved