|
| |
|
|
A008299
|
|
Triangle of associated Stirling numbers of second kind.
|
|
16
| |
|
|
1, 1, 1, 3, 1, 10, 1, 25, 15, 1, 56, 105, 1, 119, 490, 105, 1, 246, 1918, 1260, 1, 501, 6825, 9450, 945, 1, 1012, 22935, 56980, 17325, 1, 2035, 74316, 302995, 190575, 10395, 1, 4082, 235092, 1487200, 1636635, 270270, 1, 8177, 731731, 6914908, 12122110
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 2,4
|
|
|
COMMENTS
| T(n,k) counts the number of set partitions of [n] into k blocks of size at least 2. Compare with A008277 (blocks of size at least 1) and A059022 (blocks of size at least 3). See also A200091. Reading the table by diagonals gives A134991. The row generating polynomials are the Mahler polynomials s_n(-x). See [Roman, 4.9]. Rows are of lengths 1,1,2,2,3,3,....
|
|
|
REFERENCES
| L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
A. E. Fekete, Apropos two notes on notation, Amer. Math. Monthly, 101 (1994), 771-778.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 76.
S. Roman, The Umbral Calculus, Dover Publications, New York (2005), pp. 129-130.
|
|
|
LINKS
| P. Bala, Diagonals of triangles with generating function exp(t*F(x)).
L. M. Smiley, Completion of a Rational Function Sequence of Carlitz
Eric Weisstein's World of Mathematics, Mahler polynomial
|
|
|
FORMULA
| E.g.f. with additional constant 1: exp(t*(exp(x)-1-x)) = 1+t*x^2/2!+t*x^3/3!+(t+3*t^2)*x^4/4!+....
Recurrence relation: T(n+1,k) = k*T(n,k) + n*T(n-1,k-1).
T(n,k) = A134991(n-k,k); A134991(n,k) = T(n+k,k).
More generally, if S_r(n,k) counts the number of set partitions of [n] into k blocks of size at least r then we have the recurrence S_r(n+1,k)=k*S_r(n,k)+binomial(n,r-1)*S_r(n-r+1,k-1) (for this sequence, r=2), with associated e.g.f.: sum(S_r(n,k)*u^k*(t^n/n!), n=0..infty, k=0..infty)=exp(u*(e^t-sum(t^i/i!, i=0..r-1))).
a(n, k) = sum_{i=0..k} (-1)^i*binomial(n, i)*[sum_{j=0..k-i} (-1)^j*(k -i -j)^(n-i)/(j!*(k-i-j)!)] - David Wasserman (dwasserm(AT)earthlink.net), Jun 13 2007
|
|
|
EXAMPLE
| There are 3 ways of partitioning a set N of cardinality 4 into 2 blocks each of cardinality at least 2, so S_2(4,2)=3. Table begins
.n\k.|..1....2.....3.....4
= = = = = = = = = = = = = =
..2..|..1
..3..|..1
..4..|..1....3
..5..|..1...10
..6..|..1...25....15
..7..|..1...56...105
..8..|..1..119...490...105
..9..|..1..246..1918..1260
...
Reading the table by diagonals produces the triangle A134991.
|
|
|
MATHEMATICA
| t[n_, k_] := Sum[ (-1)^i*Binomial[n, i]*Sum[ (-1)^j*(k - i - j)^(n - i)/(j!*(k - i - j)!), {j, 0, k - i}], {i, 0, k}]; Flatten[ Table[ t[n, k], {n, 2, 14}, {k, 1, Floor[n/2]}]] (* From Jean-François Alcover, Oct 13 2011, after David Wasserman *)
|
|
|
CROSSREFS
| Rows give A000247, A000478, A058844. Cf. A059022, A059023, A059024, A059025.
Row sums: A000296. A134991. A200091.
Sequence in context: A127613 A178866 A019427 * A016478 A102430 A135573
Adjacent sequences: A008296 A008297 A008298 * A008300 A008301 A008302
|
|
|
KEYWORD
| nonn,tabf,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Formula and cross-references from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 14 2000
More terms from David Wasserman (dwasserm(AT)earthlink.net), Jun 13 2007
Edited by Peter Bala, Dec 04 2011
|
| |
|
|
