login
Number of proper multisets of nonempty words with a total of n letters over n-ary alphabet such that if a letter occurs in the multiset all predecessors occur at least once.
2

%I #15 Jun 01 2022 14:45:53

%S 1,3,23,178,1786,20927,282520,4299263,72750927,1353700567,27452623890,

%T 602326265519,14209892886819,358576428141962,9634718410829852,

%U 274567642777650028,8270000441627265937,262464788618069324640,8752908129221863491691,305968679117675345995513

%N Number of proper multisets of nonempty words with a total of n letters over n-ary alphabet such that if a letter occurs in the multiset all predecessors occur at least once.

%H Alois P. Heinz, <a href="/A320265/b320265.txt">Table of n, a(n) for n = 2..300</a>

%F a(n) = Sum_{k=1..n-1} A320264(n,k).

%F a(n) = A257741(n) - A319518(n).

%e a(2) = 1: {a,a}.

%e a(3) = 3: {a,a,a}, {a,a,b}, {a,b,b}.

%e a(4) = 23: {a,a,a,a}, {a,a,aa}, {aa, aa}, {a,a,a,b}, {a,a,b,b}, {a,b,b,b}, {a,a,ab}, {a,a,ba}, {a,a,bb}, {b,b,ab}, {b,b,ba}, {b,b,aa}, {ab,ab}, {ba,ba}, {a,a,b,c}, {a,a,bc}, {a,a,cb}, {b,b,a,c}, {b,b,ac}, {b,b,ca}, {c,c,a,b}, {c,c,ab}, {c,c,ba}.

%p h:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p add(h(n-i*j, i-1, k)*binomial(k^i, j), j=0..n/i)))

%p end:

%p g:= proc(n, k) option remember; `if`(n=0, 1, add(add(

%p d*k^d, d=numtheory[divisors](j))*g(n-j, k), j=1..n)/n)

%p end:

%p a:= n-> add(add((-1)^i*(g(n, k-i)-h(n$2, k-i))*

%p binomial(k, i), i=0..k), k=1..n-1):

%p seq(a(n), n=2..25);

%t h[n_, i_, k_] := h[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[h[n - i*j, i - 1, k]*Binomial[k^i, j], {j, 0, n/i}]]];

%t g[n_, k_] := g[n, k] = If[n == 0, 1, Sum[Sum[d*k^d, {d, Divisors[j]}]*g[n - j, k], {j, 1, n}]/n];

%t T[n_, k_] := Sum[(-1)^i*(g[n, k-i]-h[n, n, k-i])*Binomial[k, i], {i, 0, k}];

%t a[n_] := Sum[T[n, k], {k, 1, n - 1}];

%t Table[a[n], {n, 2, 25}] (* _Jean-François Alcover_, Jun 01 2022, after _Alois P. Heinz_ in A320264 *)

%Y Row sums of A320264.

%Y Cf. A257741, A319518.

%K nonn

%O 2,2

%A _Alois P. Heinz_, Oct 08 2018