A241500 Triangle T(n,k): number of ways of partitioning the n-element multiset {1,1,2,3,...,n-1} into exactly k nonempty parts, n>=1 and 1<=k<=n.

1, 1, 1, 1, 2, 1, 1, 5, 4, 1, 1, 11, 16, 7, 1, 1, 23, 58, 41, 11, 1, 1, 47, 196, 215, 90, 16, 1, 1, 95, 634, 1041, 640, 176, 22, 1, 1, 191, 1996, 4767, 4151, 1631, 315, 29, 1, 1, 383, 6178, 21001, 25221, 13587, 3696, 526, 37, 1, 1, 767, 18916, 90055, 146140, 105042, 38409, 7638, 831, 46, 1

Offset: 1

Author

Andrew Woods, Apr 24 2014

Keywords

• nonn
• easy
• tabl

Examples

			There are 58 ways to partition {1,1,2,3,4,5} into three nonempty parts.
The first few rows are:
  1;
  1,   1;
  1,   2,    1;
  1,   5,    4,     1;
  1,  11,   16,     7,     1;
  1,  23,   58,    41,    11,     1;
  1,  47,  196,   215,    90,    16,    1;
  1,  95,  634,  1041,   640,   176,   22,   1;
  1, 191, 1996,  4767,  4151,  1631,  315,  29,  1;
  1, 383, 6178, 21001, 25221, 13587, 3696, 526, 37, 1;
  ...
		

Crossrefs

The first five columns appear as A000012, A083329, A168583, A168584, A168585.

Row sums give A035098.

Programs

PARI

T(n,k) = stirling(n-1,k,2) + stirling(n-1,k-1,2) + binomial(k,2)*stirling(n-2,k,2); \\ Michel Marcus, Apr 24 2014

Formula

T(n,k) = S(n-1,k) + S(n-1,k-1) + C(k,2)*S(n-2,k), where S refers to Stirling numbers of the second kind (A008277), and C to binomial coefficients (A007318).