login
Number T(n,k) of n-length words w over a k-ary alphabet {a1, a2, ..., ak} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 1, where #(w,x) counts the letters x in word w; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.
19

%I #40 Jan 19 2022 18:52:44

%S 1,0,1,0,1,2,0,1,3,6,0,1,10,12,24,0,1,15,50,60,120,0,1,41,180,300,360,

%T 720,0,1,63,497,1260,2100,2520,5040,0,1,162,1484,6496,10080,16800,

%U 20160,40320,0,1,255,5154,20916,58464,90720,151200,181440,362880

%N Number T(n,k) of n-length words w over a k-ary alphabet {a1, a2, ..., ak} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 1, where #(w,x) counts the letters x in word w; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

%C T(n,k) is the sum of multinomials M(n; lambda), where lambda ranges over all partitions of n into parts that form a multiset of size k.

%H Alois P. Heinz, <a href="/A226874/b226874.txt">Rows n = 0..140, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Iverson_bracket">Iverson bracket</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients">Multinomial coefficients</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>

%F T(n,k) = A226873(n,k) - [k>0] * A226873(n,k-1).

%e T(4,2) = 10: aaab, aaba, aabb, abaa, abab, abba, baaa, baab, baba, bbaa.

%e T(4,3) = 12: aabc, aacb, abac, abca, acab, acba, baac, baca, bcaa, caab, caba, cbaa.

%e T(5,2) = 15: aaaab, aaaba, aaabb, aabaa, aabab, aabba, abaaa, abaab, ababa, abbaa, baaaa, baaab, baaba, babaa, bbaaa.

%e Triangle T(n,k) begins:

%e 1;

%e 0, 1;

%e 0, 1, 2;

%e 0, 1, 3, 6;

%e 0, 1, 10, 12, 24;

%e 0, 1, 15, 50, 60, 120;

%e 0, 1, 41, 180, 300, 360, 720;

%e 0, 1, 63, 497, 1260, 2100, 2520, 5040;

%e 0, 1, 162, 1484, 6496, 10080, 16800, 20160, 40320;

%e ...

%p b:= proc(n, i, t) option remember;

%p `if`(t=1, 1/n!, add(b(n-j, j, t-1)/j!, j=i..n/t))

%p end:

%p T:= (n, k)-> `if`(n*k=0, `if`(n=k, 1, 0), n!*b(n, 1, k)):

%p seq(seq(T(n, k), k=0..n), n=0..12);

%p # second Maple program:

%p b:= proc(n, i) option remember; expand(

%p `if`(n=0, 1, `if`(i<1, 0, add(x^j*b(n-i*j, i-1)*

%p combinat[multinomial](n, n-i*j, i$j), j=0..n/i))))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2)):

%p seq(T(n), n=0..12);

%t b[n_, i_, t_] := b[n, i, t] = If[t == 1, 1/n!, Sum[b[n - j, j, t - 1]/j!, {j, i, n/t}]]; t[n_, k_] := If[n*k == 0, If[n == k, 1, 0], n!*b[n, 1, k]]; Table[Table[t[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Dec 13 2013, translated from first Maple *)

%o (PARI)

%o T(n)={Vec(serlaplace(prod(k=1, n, 1/(1-y*x^k/k!) + O(x*x^n))))}

%o {my(t=T(10)); for(n=1, #t, for(k=0, n-1, print1(polcoeff(t[n], k), ", ")); print)} \\ _Andrew Howroyd_, Dec 20 2017

%Y Columns k=0-10 give: A000007, A057427, A226881, A226882, A226883, A226884, A226885, A226886, A226887, A226888, A226889.

%Y Main diagonal gives: A000142.

%Y Row sums give: A005651.

%Y T(2n,n) gives A318796.

%Y Cf. A131632, A285824, A292222, A327803.

%K nonn,tabl

%O 0,6

%A _Alois P. Heinz_, Jun 21 2013