A292804 Number A(n,k) of sets of nonempty words with a total of n letters over k-ary alphabet; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 5, 2, 0, 1, 4, 12, 16, 2, 0, 1, 5, 22, 55, 42, 3, 0, 1, 6, 35, 132, 225, 116, 4, 0, 1, 7, 51, 260, 729, 927, 310, 5, 0, 1, 8, 70, 452, 1805, 4000, 3729, 816, 6, 0, 1, 9, 92, 721, 3777, 12376, 21488, 14787, 2121, 8, 0

Offset

0,8

Links

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Formula

G.f. of column k: Product_{j>=1} (1+x^j)^(k^j).

A(n,k) = Sum_{i=0..k} C(k,i) * A319501(n,i).

Example

A(2,2) = 5: {aa}, {ab}, {ba}, {bb}, {a,b}.
Square array A(n,k) begins:
  1, 1,   1,     1,      1,      1,       1,       1, ...
  0, 1,   2,     3,      4,      5,       6,       7, ...
  0, 1,   5,    12,     22,     35,      51,      70, ...
  0, 2,  16,    55,    132,    260,     452,     721, ...
  0, 2,  42,   225,    729,   1805,    3777,    7042, ...
  0, 3, 116,   927,   4000,  12376,   31074,   67592, ...
  0, 4, 310,  3729,  21488,  83175,  250735,  636517, ...
  0, 5, 816, 14787, 113760, 550775, 1993176, 5904746, ...

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:
A:= (n, k)-> h(n$2, k):
seq(seq(A(n, d-n), n=0..d), d=0..14);

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}]]];
A[n_, k_] := h[n, n, k];
Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jun 03 2018, from Maple *)

Crossrefs

Columns k=0-10 give: A000007, A000009, A102866, A256142, A292838, A292839, A292840, A292841, A292842, A292843, A292844.

Rows n=0-2 give: A000012, A001477, A000326.

Main diagonal gives A292805.

Cf. A144074, A292795, A319501.

Sequence in context: A286933 A295860 A118345 * A118350 A361950 A183135

Adjacent sequences: A292801 A292802 A292803 * A292805 A292806 A292807

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 23 2017

Status

approved