4,2

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.

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]

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. kth 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)

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}}.

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;

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 this_sequence A143697 A117438 A075499

Adjacent sequences: A143493 A143494 A143495 this_sequence A143497 A143498 A143499

easy,nonn,tabl

Peter Bala (pbala(AT)toucansurf.com), Aug 20 2008