A144074 Number A(n,k) of multisets 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, 2, 0, 1, 3, 7, 3, 0, 1, 4, 15, 20, 5, 0, 1, 5, 26, 64, 59, 7, 0, 1, 6, 40, 148, 276, 162, 11, 0, 1, 7, 57, 285, 843, 1137, 449, 15, 0, 1, 8, 77, 488, 2020, 4632, 4648, 1200, 22, 0, 1, 9, 100, 770, 4140, 13876, 25124, 18585, 3194, 30, 0, 1, 10, 126

Offset: 0

Author

Alois P. Heinz, Sep 09 2008

Keywords

• nonn
• tabl

Comments

Column k > 1 is asymptotic to k^n * exp(2*sqrt(n) - 1/2 + c(k)) / (2 * sqrt(Pi) * n^(3/4)), where c(k) = Sum_{m>=2} 1/(m*(k^(m-1)-1)). - Vaclav Kotesovec, Mar 14 2015

Examples

			A(4,1) = 5: {aaaa}, {aaa,a}, {aa,aa}, {aa,a,a}, {a,a,a,a}.
A(2,2) = 7: {aa}, {a,a}, {bb}, {b,b}, {ab}, {ba}, {a,b}.
A(2,3) = 15: {aa}, {a,a}, {bb}, {b,b}, {cc}, {c,c}, {ab}, {ba}, {a,b}, {ac}, {ca}, {a,c}, {bc}, {cb}, {b,c}.
A(3,2) = 20: {aaa}, {a,aa}, {a,a,a}, {bbb}, {b,bb}, {b,b,b}, {aab}, {aba}, {baa}, {a,ab}, {a,ba}, {aa,b}, {a,a,b}, {bba}, {bab}, {abb}, {b,ba}, {b,ab}, {bb,a}, {b,b,a}.
Square array begins:
  1, 1,   1,    1,    1,     1, ...
  0, 1,   2,    3,    4,     5, ...
  0, 2,   7,   15,   26,    40, ...
  0, 3,  20,   64,  148,   285, ...
  0, 5,  59,  276,  843,  2020, ...
  0, 7, 162, 1137, 4632, 13876, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..140, flattened
• Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 27.
• N. J. A. Sloane, Transforms

Crossrefs

Columns k=0-10 give: A000007, A000041, A034899, A144067, A144068, A144069, A144070, A144071, A144072, A144073, A292837.

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

Main diagonal gives A252654.

Cf. A004248, A257740, A256142, A292804.

Programs

Maple

with(numtheory): etr:= proc(p) local b; b:= proc(n) option remember; `if`(n=0, 1, add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n) end end: A:= (n,k)-> etr(j->k^j)(n); seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

a[n_, k_] := SeriesCoefficient[ Product[1/(1-x^j)^(k^j), {j, 1, n}], {x, 0, n}]; a[0, ] = 1; a[?Positive, 0] = 0;
Table[a[n-k, k], {n, 0, 14}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Jan 15 2014 *)
etr[p_] := Module[{b}, b[n_] := b[n] = If[n==0, 1, Sum[Sum[d p[d], {d, Divisors[j]}] b[n-j], {j, 1, n}]/n]; b];
A[n_, k_] := etr[k^#&][n];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 30 2020, after Alois P. Heinz *)

Formula

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

Column k is Euler transform of the powers of k.

T(n,k) = Sum_{i=0..k} C(k,i) * A257740(n,k-i). - Alois P. Heinz, May 08 2015

Extensions

Name changed by Alois P. Heinz, Sep 21 2018