A255903 Number T(n,k) of collections of nonempty multisets with a total of n objects of exactly k colors; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 2, 2, 0, 3, 8, 5, 0, 5, 23, 33, 15, 0, 7, 56, 141, 144, 52, 0, 11, 127, 492, 848, 675, 203, 0, 15, 268, 1518, 3936, 5190, 3396, 877, 0, 22, 547, 4320, 15800, 30710, 32835, 18270, 4140, 0, 30, 1072, 11567, 57420, 154410, 240012, 216006, 104656, 21147

Offset

0,5

Comments

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = 0 for k>n.

In the case of exactly one color (k=1) each multiset of monochrome objects is fully described by its size and a collection of sizes corresponds to an integer partition. In the case of distinct colors for all objects (k=n) every multiset collection is a set partition.

Links

Alois P. Heinz, Rows n = 0..140, flattened

Formula

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A075196(n,k-i).

Sum_{k=0..n} k * T(n,k) = A317178(n).

Example

T(3,1) = 3: {{1},{1},{1}}, {{1},{1,1}}, {{1,1,1}}.
T(3,2) = 8: {{1},{1},{2}}, {{1},{2},{2}}, {{1},{1,2}}, {{1},{2,2}}, {{2},{1,1}}, {{2},{1,2}}, {{1,1,2}}, {{1,2,2}}.
T(3,3) = 5: {{1},{2},{3}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}, {{1,2,3}}.
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  2,   2;
  0,  3,   8,    5;
  0,  5,  23,   33,    15;
  0,  7,  56,  141,   144,    52;
  0, 11, 127,  492,   848,   675,   203;
  0, 15, 268, 1518,  3936,  5190,  3396,   877;
  0, 22, 547, 4320, 15800, 30710, 32835, 18270, 4140;
  ...

Maple

with(numtheory):
A:= proc(n, k) option remember; `if`(n=0, 1, add(A(n-j, k)*
      add(d*binomial(d+k-1, k-1), d=divisors(j)), j=1..n)/n)
    end:
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

A[n_, k_] := A[n, k] = If[n==0, 1, Sum[A[n-j, k]*Sum[d*Binomial[d+k-1, k-1], {d, Divisors[j]}], {j, 1, n}]/n]; T[n_, k_] := Sum[A[n, k-i]*(-1)^i * Binomial[k, i], {i, 0, k}]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 12} ] // Flatten (* Jean-François Alcover, Feb 20 2016, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000007, A000041 (for n>0), A255942, A255943, A255944, A255945, A255946, A255947, A255948, A255949, A255950.

Main and lower diagonals give: A000110, A255951, A255952, A255953, A255954, A255955, A255956, A255957, A255958, A255959, A255960.

Row sums give A255906.

Antidiagonal sums give A258450.

T(2n,n) gives A255907.

Cf. A075196, A317178, A326914, A326962, A327116, A327117.

Sequence in context: A193383 A218033 A326500 * A118262 A065484 A255970

Adjacent sequences: A255900 A255901 A255902 * A255904 A255905 A255906

Keyword

nonn,tabl

Author

Alois P. Heinz, Mar 10 2015

Status

approved