|
| |
|
|
A048994
|
|
Triangle of Stirling numbers of first kind, s(n,k), n >= 0, 0 <= k <= n.
|
|
204
|
|
|
|
1, 0, 1, 0, -1, 1, 0, 2, -3, 1, 0, -6, 11, -6, 1, 0, 24, -50, 35, -10, 1, 0, -120, 274, -225, 85, -15, 1, 0, 720, -1764, 1624, -735, 175, -21, 1, 0, -5040, 13068, -13132, 6769, -1960, 322, -28, 1, 0, 40320, -109584, 118124, -67284, 22449, -4536, 546, -36, 1, 0, -362880, 1026576, -1172700, 723680, -269325, 63273, -9450, 870, -45, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
COMMENTS
|
The unsigned numbers are also called Stirling cycle numbers: |s(n,k)| = number of permutations of n objects with exactly k cycles.
Also the triangle gives coefficients T(n,k) of x^k in the expansion of C(x,n) = (a(k)*x^k)/n!. - Mokhtar Mohamed, Dec 04 2012
This is the Sheffer triangle of Jabotinsky type (1, log(1 + x)). See the e.g.f. of the triangle below.
This is the inverse Sheffer triangle of the Stirling2 Sheffer triangle A008275.
The a-sequence of this Sheffer triangle (see a W. Lang link in A006232)
is from the e.g.f. A(x) = x/(exp(x) -1) a(n) = Bernoulli(n) = A027641(n)/A027642(n), for n >= 0. The z-sequence vanishes.
The Boas-Buck sequence for the recurrences of columns has o.g.f. B(x) = Sum_{n>=0} b(n)*x^n = 1/((1 + x)*log(1 + x)) - 1/x. b(n) = (-1)^(n+1)*A002208(n+1)/A002209(n+1), b = {-1/2, 5/12, -3/8, 251/720, -95/288, 19087/60480,...}. For the Boas-Buck recurrence of Riordan and Sheffer triangles see the Aug 10 2017 remark in A046521, adapted to the Sheffer case, also for two references. See the recurrence and example below. - Wolfdieter Lang, Nov 14 2018
|
|
|
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.
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.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 245.
J. Riordan, An Introduction to Combinatorial Analysis, p. 48.
|
|
|
LINKS
|
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].
|
|
|
FORMULA
|
s(n, k) = A008275(n,k) for n >= 1, k = 1..n; column k = 0 is {1, repeat(0)}.
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.
Triangle (signed) = [0, -1, -1, -2, -2, -3, -3, -4, -4, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...]; Triangle(unsigned) = [0, 1, 1, 2, 2, 3, 3, 4, 4, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...]; where DELTA is Deléham's operator defined in A084938.
Sum_{k=0..n} (-m)^(n-k)*s(n, k) = A000142(n), A001147(n), A007559(n), A007696(n), ... for m = 1, 2, 3, 4, ... .- Philippe Deléham, Oct 29 2005
T(n,k) = n!*[x^k]([t^n]exp(x*log(1+t))). - Peter Luschny, Dec 30 2010, updated Jun 07 2020
Recurrence from the Sheffer a-sequence (see a comment above): s(n, k) = (n/k)*Sum_{j=0..n-k} binomial(k-1+j, j)*Bernoulli(j)*s(n-1, k-1+j), for n >= 1 and k >= 1, with s(n, 0) = 0 if n >= 1, and s(0,0) = 1.
Boas-Buck type recurrence for column k: s(n, k) = (n!*k/(n - k))*Sum_{j=k..n-1} b(n-1-j)*s(j, k)/j!, for n >= 1 and k = 0..n-1, with input s(n, n) = 1. For sequence b see the Boas-Buck comment above. (End)
|
|
|
EXAMPLE
|
Triangle begins:
n\k 0 1 2 3 4 5 6 7 8 9 ...
0 1
1 0 1
2 0 -1 1
3 0 2 -3 1
4 0 -6 11 -6 1
5 0 24 -50 35 -10 1
6 0 -120 274 -225 85 -15 1
7 0 720 -1764 1624 -735 175 -21 1
8 0 -5040 13068 -13132 6769 -1960 322 -28 1
9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1
------------------------------------------------------------------
Recurrence: s(5,2)= s(4, 1) - 4*s(4, 2) = -6 - 4*11 = -50.
Recurrence from the a- and z-sequences: s(6, 3) = 2*(1*1*(-50) + 3*(-1/2)*35 + 6*(1/6)*(-10) + 10*0*1) = -225.
Boas-Buck recurrence for column k = 3, with b = {-1/2, 5/12, -3/8, ...}:
s(6, 3) = 6!*((-3/8)*1/3! + (5/12)*(-6)/4! + (-1/2)*35/5!) = -225. (End)
|
|
|
MAPLE
|
seq(print(seq(coeff(expand(k!*binomial(x, k)), x, i), i=0..k)), k=0..9); # Peter Luschny, Jul 13 2009
A048994_row := proc(n) local k; seq(coeff(expand(pochhammer(x-n+1, n)), x, k), k=0..n) end: # Peter Luschny, Dec 30 2010
|
|
|
MATHEMATICA
|
Table[StirlingS1[n, m], {n, 0, 9}, {m, 0, n}] (* Peter Luschny, Dec 30 2010 *)
|
|
|
PROG
|
(PARI) a(n, k) = if(k<0 || k>n, 0, if(n==0, 1, (n-1)*a(n-1, k)+a(n-1, k-1)))
(PARI) trg(nn)=for (n=0, nn-1, for (k=0, n, print1(stirling(n, k, 1), ", "); ); print(); ); \\ Michel Marcus, Jan 19 2015
(Maxima) create_list(stirling1(n, k), n, 0, 12, k, 0, n); /* Emanuele Munarini, Mar 11 2011 */
(Haskell)
a048994 n k = a048994_tabl !! n !! k
a048994_row n = a048994_tabl !! n
a048994_tabl = map fst $ iterate (\(row, i) ->
(zipWith (-) ([0] ++ row) $ map (* i) (row ++ [0]), i + 1)) ([1], 0)
|
|
|
CROSSREFS
|
See especially A008275 which is the main entry for this triangle. A132393 is an unsigned version, and A008276 is another version.
A000142(n) = Sum_{k=0..n} |s(n, k)| for n >= 0.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
