A320264 Number T(n,k) of proper multisets of nonempty words with a total of n letters over k-ary alphabet such that all k letters occur at least once in the multiset; triangle T(n,k), n>=2, 1<=k<=n-1, read by rows.

1, 1, 2, 3, 11, 9, 4, 38, 84, 52, 7, 125, 523, 766, 365, 10, 364, 2676, 7096, 7775, 3006, 16, 1041, 12435, 52955, 100455, 87261, 28357, 22, 2838, 54034, 348696, 1020805, 1497038, 1074766, 301064, 32, 7645, 225417, 2120284, 8995801, 19823964, 23605043, 14423564, 3549177

Offset

2,3

Links

Alois P. Heinz, Rows n = 2..150

Formula

T(n,k) = A257740(n,k) - A319501(n,k).

Example

T(2,1) = 1: {a,a}.
T(3,2) = 2: {a,a,b}, {a,b,b}.
T(4,3) = 9: {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}.
Triangle T(n,k) begins:
  .
  .   .
  .   1,    .
  .   1,    2,     .
  .   3,   11,     9,      .
  .   4,   38,    84,     52,       .
  .   7,  125,   523,    766,     365,       .
  .  10,  364,  2676,   7096,    7775,    3006,       .
  .  16, 1041, 12435,  52955,  100455,   87261,   28357,      .
  .  22, 2838, 54034, 348696, 1020805, 1497038, 1074766, 301064,   .

Maple

h:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(h(n-i*j, i-1, k)*binomial(k^i, j), j=0..n/i)))
    end:
g:= proc(n, k) option remember; `if`(n=0, 1, add(add(
      d*k^d, d=numtheory[divisors](j))*g(n-j, k), j=1..n)/n)
    end:
T:= (n, k)-> add((-1)^i*(g(n, k-i)-h(n$2, k-i))*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=1..n-1), n=2..12);

Mathematica

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}]]];
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[n_, k_] := Sum[(-1)^i*(g[n, k-i]-h[n, n, k-i])*Binomial[k, i], {i, 0, k}];
Table[Table[T[n, k], {k, 1, n - 1}], {n, 2, 12}] // Flatten (* Jean-François Alcover, Feb 13 2021, after Alois P. Heinz *)

Crossrefs

Column k=1 gives A047967.

Row sums give A320265.

T(n+1,n) gives A006152.

Cf. A257740, A319501.

Sequence in context: A086146 A083758 A127494 * A335173 A265563 A265547

Adjacent sequences: A320261 A320262 A320263 * A320265 A320266 A320267

Keyword

nonn,tabl

Author

Alois P. Heinz, Oct 08 2018

Status

approved