%I A008275
%S A008275 1,1,1,2,3,1,6,11,6,1,24,50,35,10,1,120,274,225,85,15,1,720,
%T A008275 1764,1624,735,175,21,1,5040,13068,13132,6769,1960,322,28,
%U A008275 1,40320,109584,118124,67284,22449,4536,546,36,1,362880,1026576
%V A008275 1,-1,1,2,-3,1,-6,11,-6,1,24,-50,35,-10,1,-120,274,-225,85,-15,1,720,
%W A008275 -1764,1624,-735,175,-21,1,-5040,13068,-13132,6769,-1960,322,-28,
%X A008275 1,40320,-109584,118124,-67284,22449,-4536,546,-36,1,-362880,1026576
%N A008275 Triangle read by rows of Stirling numbers of first kind, s(n,k), n >=
1, 1<=k<=n.
%C A008275 The unsigned numbers are also called Stirling cycle numbers: |s(n,k)|
= number of permutations of n objects with exactly k cycles.
%C A008275 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 (wieder.thomas(AT)t-online.de), Aug 04 2005
%C A008275 Row sums equal 0 - Jon Perry (perry(AT)globalnet.co.uk), Nov 14 2005
%C A008275 |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.
%C A008275 |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
%D A008275 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 A008275 E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations
and random generation, Theoretical Computer Science, 159, 1996, 29-42.
%D A008275 A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of
combinatorial proof, M.A.A. 2003, p. 93ff.
%D A008275 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.
%D A008275 L. Comtet, Advanced Combinatorics, Reidel, 1974; Chapter V, also p. 310.
%D A008275 J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY,
1996, p. 93.
%D A008275 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied
Tables, Cambridge, 1966, p. 226.
%D A008275 H. H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977;
Section 2.7.
%D A008275 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley,
Reading, MA, 1990, p. 245.
%D A008275 J. Hines, A generalization of the S-Stirling numbers, Math. Mag., 29
(1956), 200-203.
%D A008275 Yoshinari Inaba, Hyper-Sums of Powers of Integers and the Akiyama-Tanigawa
Matrix, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.7.
%D A008275 Knessl, Charles; Keller, Joseph B. Stirling number asymptotics from recursion
equations using the ray method. Stud. Appl. Math. 84 (1991), no.
1, 43-56.
%D A008275 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]
%D A008275 J. Riordan, An Introduction to Combinatorial Analysis, p. 48.
%D A008275 R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms,
Addison-Wesley, Reading, MA, 1996.
%D A008275 J. Stirling, The Differential Method, London, 1749; see p. 10.
%D A008275 N. M. Temme, Asymptotic estimates of Stirling numbers, Stud. Appl. Math.
89 (1993), no. 3, 233-243.
%D A008275 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.
%H A008275 T. D. Noe, <a href="b008275.txt">Rows 1 to 100 of triangle, flattened.</
a>
%H A008275 K. A. Penson, P. Blasiak, A. Horzela, G. H. E. Duchamp and A. I. Solomon,
<a href="http://arxiv.org/abs/0904.0369">Laguerre-type derivatives:
Dobinski relations and combinatorial identities</a>, J. Math. Phys.
vol. 50, 083512 (2009)
%H A008275 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A008275 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.nrbook.com/
abramowitz_and_stegun/">Handbook of Mathematical Functions</a>, National
Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972
[alternative scanned copy].
%H A008275 R. M. Dickau, <a href="http://mathforum.org/advanced/robertd/stirling1.html">
Stirling numbers of the first kind</a>
%H A008275 D. B. Gruenberg, <a href="http://arXiv.org/abs/math.CO/0607514">On asymptotics,
Stirling numbers, Gamma function and polylogs</a>
%H A008275 A. F. Labossiere, <a href="http://members.lycos.co.uk/sobalian/index.html">
Sobalian Coefficients</a>.
%H A008275 A. F. Labossiere, <a href="http://members.lycos.co.uk/stereotomography/
index.html">Miscellaneous</a>.
%H A008275 W. Lang, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
On generalizations of Stirling number triangles</a>, J. Integer Seqs.,
Vol. 3 (2000), #00.2.4.
%H A008275 D. E. Loeb, <a href="http://arXiv.org/abs/math.CO/9502217">[math/9502217]
A generalization of Stirling numbers</a>
%H A008275 R. P. Stanley, <a href="http://arXiv.org/abs/math.CO/0501256">Ordering
events in Minkowski space</a>
%H A008275 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
PermutationCycle.html">Link to a section of The World of Mathematics.</
a>
%H A008275 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
StirlingNumberoftheFirstKind.html">Link to a section of The World
of Mathematics.</a>
%H A008275 Thomas Wieder, <a href="a008275.txt">Comments on A008275</a>
%F 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.
%F A008275 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.
%F A008275 E.g.f. for m-th column (unsigned): ((-ln(1-x))^m)/m!.
%F A008275 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, ...].
%F A008275 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
%F A008275 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 (perry(AT)globalnet.co.uk), Nov 14 2005
%F A008275 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
%e A008275 |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)).
%e A008275 Triangle begins:
%e A008275 ..................................1
%e A008275 ................................-1, 1
%e A008275 ...............................2, -3, 1
%e A008275 ............................-6, 11, -6, 1
%e A008275 .........................24, -50, 35, -10, 1
%e A008275 .....................-120, 274, -225, 85, -15, 1
%e A008275 .................720, -1764, 1624, -735, 175, -21, 1
%e A008275 ............-5040, 13068, -13132, 6769, -1960, 322, -28, 1
%e A008275 ......40320, -109584, 118124, -67284, 22449, -4536, 546, -36, 1
%e A008275 Another version of the same triangle, from Joerg Arndt, Oct 05 2009:
%e A008275 s(n,k) := number of permutations of n elements with exactly k cycles
("Stirling cycle numbers")
%e A008275 ..n:...total...m=..1......2......3.....4.....5.....6....7...8...9
%e A008275 ..1:.......1.......1
%e A008275 ..2:.......2.......1......1
%e A008275 ..3:.......6.......2......3......1
%e A008275 ..4:......24.......6.....11......6.....1
%e A008275 ..5:.....120......24.....50.....35....10.....1
%e A008275 ..6:.....720.....120....274....225....85....15.....1
%e A008275 ..7:....5040.....720...1764...1624...735...175....21....1
%e A008275 ..8:...40320....5040..13068..13132..6769..1960...322...28...1
%e A008275 ..9:..362880...40320.109584.118124.67284.22449..4536..546..36...1
%e A008275 |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 (wolfdieter.lang(AT)physik.uni-karlsruhe.de),
Feb 22 2008
%p A008275 with (combinat):seq(seq(stirling1(n, k), k=1..n), n=1..10); - Zerinvary
Lajos (zerinvarylajos(AT)yahoo.com), Jun 03 2007
%p A008275 for i from 0 to 9 do seq(stirling1(i, j), j = 1 .. i) od; - Zerinvary
Lajos (zerinvarylajos(AT)yahoo.com), Nov 29 2007
%o A008275 (PARI) T(n,k)=if(n<1,0,n!*polcoeff(binomial(x,n),k))
%o A008275 (PARI) T(n,k)=if(n<1,0,n!*polcoeff(polcoeff((1+x+x*O(x^n))^y,n),k))
%o A008275 (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
%Y A008275 Cf. A048994, A008277 (Stirling numbers of second kind), A039814-A039817,
A048993.
%Y A008275 Cf. A084938, A094216, A008276, A094262, A008277, A008278, A121632.
%Y A008275 A130534 is a signed version.
%Y A008275 A000142(n) = sum(|s(n, k)|) k=0..n, n >= 0,
%Y A008275 Sequence in context: A165675 A138771 A121748 this_sequence A130534 A107416
A105613
%Y A008275 Adjacent sequences: A008272 A008273 A008274 this_sequence A008276 A008277
A008278
%K A008275 sign,tabl,nice,core
%O A008275 1,4
%A A008275 N. J. A. Sloane (njas(AT)research.att.com).
|
