2,2

This is the case r = 2 of the r-restricted Stirling numbers of the second kind. The 2-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 and 2 belong to distinct subsets.

More generally, the r-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 numbers 1, 2, ..., r belong to distinct subsets. The case r = 1 gives the usual Stirling numbers of the second kind A008277; for other cases see A143495 (r = 3) and A143496 (r = 4).

The lower unitriangular array of r-restricted Stirling numbers of the second kind equals the matrix product P^(r-1) * S (with suitable offsets in the row and column indexing), where P is Pascal's triangle, A007318 and S is the array of Stirling numbers of the second kind, A008277.

For the definition of and entries relating to the corresponding r-restricted Stirling numbers of the first kind see A143491. For entries on r-restricted Lah numbers refer to A143497. The theory of r-restricted Stirling numbers of both kinds is developed in [Broder].

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^(-2)*E^n*x^2 = sum {k = 0..n} T(n+2,k+2)*x^k*D^k.

The row generating polynomials R_n(x) := sum {k= 2..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_2(x) = x^2. It follows that the polynomials R_n(x) have only real zeros (apply Corollary 1.2. of [Liu and Wang]).

Relation with the 2-restricted Eulerian numbers E_2(n,j) := A144696(n,j): T(n,k) = 2!/k!*sum {j = n-k..n-2} E_2(n,j)*binomial(j,n-k) for n >= k >= 2.

(End)

Corcino C.B., Hsu L. C., Tan E. L., Asymptotic approximations of r-Stirling numbers. Approximation Theory Appl. 15, No. 3 13-25 (1999)

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+2,k+2) = (1/k!)*sum {i = 0..k} (-1)^(k-i)*C(k,i)*(i+2)^n, n,k >= 0. T(n,k) = Stirling2(n,k) - Stirling2(n-1,k), n,k >= 2.

Recurrence relation: T(n,k) = T(n-1,k-1) + k*T(n-1,k) for n > 2, with boundary conditions: T(n,1) = T(1,n) = 0 for all n; T(2,2) = 1; T(2,k) = 0 for k > 2. Special cases: T(n,2) = 2^(n-2); T(n,3) = 3^(n-2) - 2^(n-2).

As a sum of monomial functions of degree m: T(n+m,n) = sum {2 <= i_1 <= ... <=i_m <=n} (i_1*i_2*...*i_m). For example, T(6,4) = sum {2<=i<=j<=4} (i*j) = 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4 = 55.

E.g.f. column k+2 (with offset 2): 1/k!*exp(2x)*(exp(x)-1)^k. O.g.f. k-th column: sum {n = k..inf} T(n,k)*x^n = x^k/((1-2x)(1-3x)...(1-kx)). E.g.f.: exp(2*t + x*(exp(t)-1)) = sum {n = 0..inf} sum {k = 0..n} T(n+2,k+2) *x^k*t^n/n! = sum {n = 0..inf} B_n(2;x)*t^n/n! = 1 + (2 + x)*t/1! + (4 + 5x + x^2)*t^2/2! + ..., where the row polynomial B_n(2;x) := sum {k = 0..n} T(n+2,k+2)*x^k denotes the 2-restricted Bell polynomial.

Dobinski-type identities: Row polynomial B_n(2;x) = exp(-x)*sum {i = 0..inf} (i+2)^n*x^i/i!. Sum {k = 0..n} k!*T(n+2,k+2)*x^k = sum {i = 0..inf} (i+2)^n*x^i/(1+x)^(i+1). The T(n,k) are the connection coefficients between falling factorials and the shifted monomials (x+1)^(n-2). For example, from row 4 we have 4 + 5(x-1) + (x-1)(x-2) = (x+1)^2, while from row 5 we have 8 + 19(x-1) + 9(x-1)(x-2) + (x-1)(x-2)(x-3) = (x+1)^3.

The row sums of the array are the 2-restricted Bell numbers, B_n(2;1), equal to A005493(n-2). The alternating row sums are the complementary 2-restricted Bell numbers, B_n(2;-1), equal to (-1)^n*A074051(n-2). This array is the matrix product P * S, where P denotes the Pascal triangle, A007318 and S denotes the lower triangular array of Stirling numbers of the second kind, A008277 (apply Theorem 10 of [Neuwirth]).

Also, this array equals the transpose of the upper triangular array A126351. The inverse array is A049444, the signed 2-restricted Stirling numbers of the first kind. See A143491 for the unsigned version of the inverse.

Triangle begins

n\k|...2....3....4....5....6....7

=================================

2..|...1

3..|...2....1

4..|...4....5....1

5..|...8...19....9....1

6..|..16...65...55...14....1

7..|..32..211..285..125...20....1

...

T(4,3) = 5. The set {1,2,3,4} can be partitioned into three subsets such that 1 and 2 belong to different subsets in 5 ways: {{1}{2}{3,4}}, {{1}{3}{2,4}}, {{1}{4}{2,3}}, {{2}{3}{1,4}} and {{2}{4}{1,3}}; the remaining possibility {{1,2}{3}{4}} is not allowed.

with combinat: T := (n, k) -> 1/(k-2)!*add ((-1)^(k-i)*binomial(k-2, i)*(i+2)^(n-2), i = 0..k-2): for n from 2 to 11 do seq(T(n, k), k = 2..n) end do;

Cf. A001047 (column 3), A005493 (row sums), A008277, A016269 (column 4), A025211 (column 5), A049444 (matrix inverse), A074051 (alt. row sums), A143491, A143495, A143496, A143497.

Sequence in context: A114164 A126182 A154342 this_sequence A124960 A137346 A159971

Adjacent sequences: A143491 A143492 A143493 this_sequence A143495 A143496 A143497

easy,nonn,tabl

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