|
%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
|
