login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
35
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
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.
Sequence in context: A193383 A218033 A326500 * A118262 A065484 A255970
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Mar 10 2015
STATUS
approved