|
| |
|
|
A008275
|
|
Triangle read by rows of Stirling numbers of first kind, s(n,k), n >= 1, 1<=k<=n.
|
|
162
|
|
|
|
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. W. 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). W. Lang, Oct 12 2007, Feb 22 2008
T(n,k) = A048993(n,k), for k=1..n. - Reinhard Zumkeller, Mar 18 2013
|
|
|
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.
Nikita Alexeev and Peter Zograf, Hultman numbers, polygon gluings and matrix integrals, Arxiv preprint arXiv:1111.3061, 2011
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, 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.
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.
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, http://www.tandfonline.com/doi/abs/10.1080/0020739X.2011.582172
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.
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.
Knessl, Charles; Keller, Joseph B. Stirling number asymptotics from recursion equations using the ray method. Stud. Appl. Math. 84 (1991), no. 1, 43-56.
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]
J. Riordan, An Introduction to Combinatorial Analysis, p. 48.
Scurr, Raymond; Olive, Gloria. Stirling numbers revisited. Discrete Math. 189 (1998), no. 1-3, 209--219. MR1637761 (99d:11019)
R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.
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
J. Stirling, The Differential Method, London, 1749; see p. 10.
N. M. Temme, Asymptotic estimates of Stirling numbers, Stud. Appl. Math. 89 (1993), no. 3, 233-243.
Timashev, A. N. 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.
|
|
|
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].
Joerg Arndt, Fxtbook, p.277
R. M. Dickau, Stirling numbers of the first kind
D. B. Gruenberg, On asymptotics, Stirling numbers, Gamma function and polylogs
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
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)
Warren D. Smith, Puzzle: Counting new records
R. P. Stanley, Ordering events in Minkowski space
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): ((-ln(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 Deleham'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) - ..... ]. - Andre F. Labossiere (boronali(AT)laposte.net), Mar 27 2006
|
|
|
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 (zerinvarylajos(AT)yahoo.com), Jun 03 2007
for i from 0 to 9 do seq(stirling1(i, j), j = 1 .. i) od; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 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 [From Luc Roy (luc.rg.roy(AT)gmail.com), Jul 27 2010]
Flatten[Table[StirlingS1[n, k], {n, 1, 10}, {k, 1, n}]][[1 ;; 47]] (* From 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
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
