|
| |
|
|
A143496
|
|
4-restricted Stirling numbers of the second kind.
|
|
15
| |
|
|
1, 4, 1, 16, 9, 1, 64, 61, 15, 1, 256, 369, 151, 22, 1, 1024, 2101, 1275, 305, 30, 1, 4096, 11529, 9751, 3410, 545, 39, 1, 16384, 61741, 70035, 33621, 7770, 896, 49, 1, 65536, 325089, 481951, 305382, 95781, 15834, 1386, 60, 1, 262144, 1690981, 3216795
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 4,2
|
|
|
COMMENTS
| This is the case r = 4 of the r-restricted Stirling numbers of the second kind. The 4-restricted Stirling numbers of the second kind count the number of ways of partitioning the set {1,2,...,n} into k nonempty disjoint subsets with the restriction that the elements 1, 2, 3 and 4 belong to distinct subsets. For remarks on the general case see A143494 (r = 2). The corresponding array of 4-restricted Stirling numbers of the first kind is A143493. The theory of r-restricted Stirling numbers of both kinds is developed in [Broder]. For 4-restricted Lah numbers refer to A143499.
From Wolfdieter Lang, Sep 29 2011 (Start)
T(n,k)=S(n,k,4), n>=k>=4, in Mikhailov's first paper, eq.(28) or (A3). E.g.f. column k from (A20) with k->4, r->k. Therefore, with offset [0,0], this triangle is the Sheffer triangle (exp(4*x),exp(x)-1) with e.g.f. of column no. m>=0: exp(4*x)*((exp(x)-1)^m)/m!. See one of the formulae given below. For Sheffer matrices see the W. Lang link under A006232 with the S. Roman reference, also found in A132393.
(End)
|
|
|
REFERENCES
| V. V. Mikhailov, Ordering of some boson operator functions, J. Phys A: Math. Gen. 16 (1983) 3817-3827.
V. V. Mikhailov, Normal ordering and generalised Stirling numbers, J. Phys A: Math. Gen. 18 (1985) 231-235.
|
|
|
LINKS
| Broder Andrei Z., The r-Stirling numbers, Discrete Math. 49, 241-259 (1984)
Neuwirth Erich, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 No. 1-3, 33-51 (2001)
L. Liu, Y. Wang, A unified approach to polynomial sequences with only real zeros [From Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008]
|
|
|
FORMULA
| T(n+4,k+4) = 1/k!*sum {i = 0..k} (-1)^(k-i)*C(k,i)*(i+4)^n, n,k >= 0. T(n,k) = Stirling2(n,k) - 6*Stirling2(n-1,k) + 11*Stirling2(n-2,k) - 6*Stirling2(n-3,k) for n,k >= 4. Recurrence relation: T(n,k) = T(n-1,k-1) + k*T(n-1,k) for n > 4 with boundary conditions: T(n,3) = T(3,n) = 0 for all n; T(4,4) = 1; T(4,k) = 0 for k > 4. Special cases: T(n,4) = 4^(n-4); T(n,5) = 5^(n-4) - 4^(n-4).
E.g.f. (k+4)-th column (with offset 4): 1/k!*exp(4x)*(exp(x)-1)^k. O.g.f. k-th column: sum {n = k..inf} T(n,k)*x^n = x^k/((1-4x)(1-5x)...(1-kx)). E.g.f.: exp(4*t + x*(exp(t)-1)) = sum {n = 0..inf} sum(k = 0..n) T(n+4,k+4) *x^k*t^n/n! = sum {n = 0..inf} B_n(4;x)*t^n/n! = 1 + (4+x)*t/1! + (16+9x+x^2)*t^2/2! + ..., where the row polynomials, B_n(4;x) := sum {k = 0..n} T(n+4,k+4)*x^k, may be called the 4-restricted Bell polynomials. Dobinski-type identities: Row polynomial B_n(4;x) = exp(-x)*sum {i = 0..inf} (i+4)^n*x^i/i!; Sum {k = 0..n} k!*T(n+4,k+4)*x^k = sum {i = 0..inf} (i+4)^n*x^i/(1+x)^(i+1).
The T(n,k) are the connection coefficients between the falling factorials and the shifted monomials (x+3)^(n-4). For example, 16 + 9(x-1) + (x-1)(x-2) = (x+3)^2; 64 + 61(x-1) + 15(x-1)(x-2) + (x-1)(x-2)(x-3) = (x+3)^3. This array is the matrix product P^3 * S, where P denotes Pascal's triangle, A007318 and S denotes the lower triangular array of Stirling numbers of the second kind, A008277 (apply Theorem 10 of [Neuwirth]).
The inverse array is A049459, the signed 4-restricted Stirling numbers of the first kind.
Contribution from Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008: (Start)
Let D be the derivative operator d/dx and E the Euler operator x*d/dx. Then x^(-4)*E^n*x^4 = sum {k = 0..n} T(n+4,k+4)*x^k*D^k.
The row generating polynomials R_n(x) := sum {k= 4..n} T(n,k)*x^k satisfy the recurrence R_(n+1)(x) = x*R_n(x) + x*d/dx(R_n(x)) with R_4(x) = x^4. It follows that the polynomials R_n(x) have only real zeros (apply Corollary 1.2. of [Liu and Wang]).
Relation with the 4-restricted Eulerian numbers E_4(n,j) := A144698(n,j): T(n,k) = 4!/k!*sum {j = n-k..n-4} E_4(n,j)*binomial(j,n-k) for n >= k >= 4.
(End)
|
|
|
EXAMPLE
| Triangle begins
n\k|.....4.....5.....6.....7.....8.....9
========================================
4..|.....1
5..|.....4.....1
6..|....16.....9.....1
7..|....64....61....15.....1
8..|...256...369...151....22.....1
9..|..1024..2101..1275...305....30.....1
...
T(6,5) = 9. The set {1,2,3,4,5,6} can be partitioned into five subsets such that 1, 2, 3 and 4 belong to different subsets in 9 ways: {{1,5}{2}{3}{4}{6}}, {{1,6}{2}{3}{4}{5}}, {{2,5}{1}{3}{4}{6}}, {{2,6}{1}{3}{4}{5}}, {{3,5}{1}{2}{4}{6}}, {{3,6}{1}{2}{4}{5}}, {{4,5}{1}{2}{3}{6}}, {{4,6}{1}{2}{3}{5}} and {{5,6}{1}{2}{3}{4}}.
|
|
|
MAPLE
| with combinat: T := (n, k) -> 1/(k-4)!*add ((-1)^(k-i)*binomial(k-4, i)*(i+4)^(n-4), i = 0..k-4): for n from 4 to 13 do seq(T(n, k), k = 4..n) end do;
|
|
|
MATHEMATICA
| t[n_, k_] := StirlingS2[n, k] - 6*StirlingS2[n-1, k] + 11*StirlingS2[n-2, k] - 6*StirlingS2[n-3, k]; Flatten[ Table[ t[n, k], {n, 4, 13}, {k, 4, n}]] (* From Jean-François Alcover, Dec 02 2011 *)
|
|
|
CROSSREFS
| Cf. A003468 (column 7), A005060 (column 5), A008277, A016103 (column 6), A045379 (row sums), A049459 (matrix inverse), A143493, A143494, A143495, A143499.
Sequence in context: A138681 A038231 A104855 * A143697 A117438 A075499
Adjacent sequences: A143493 A143494 A143495 * A143497 A143498 A143499
|
|
|
KEYWORD
| easy,nonn,tabl
|
|
|
AUTHOR
| Peter Bala (pbala(AT)toucansurf.com), Aug 20 2008
|
| |
|
|
