A219585 Number A(n,k) of k-partite partitions of {n}^k into distinct k-tuples; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 5, 2, 1, 1, 15, 40, 17, 2, 1, 1, 52, 457, 364, 46, 3, 1, 1, 203, 6995, 14595, 2897, 123, 4, 1, 1, 877, 136771, 937776, 407287, 21369, 323, 5, 1, 1, 4140, 3299218, 88507276, 107652681, 10200931, 148257, 809, 6, 1

Offset

0,8

Comments

A(n,k) is the number of factorizations of m^n into distinct factors where m is a product of k distinct primes. A(2,2) = 5: (2*3)^2 = 36 has 5 factorizations into distinct factors: 36, 3*12, 4*9, 2*18, 2*3*6.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..209

Formula

A(n,k) = [(Product_{j=1..k} x_j)^n] 1/2 * Product_{i_1,...,i_k>=0} (1+Product_{j=1..k} x_j^i_j).

Example

A(1,3) = 5: [(1,1,1)], [(1,1,0),(0,0,1)], [(1,0,1),(0,1,0)], [(1,0,0),(0,1,0),(0,0,1)], [(0,1,1),(1,0,0)].
A(3,2) = 17: [(3,3)], [(3,0),(0,3)], [(3,2),(0,1)], [(2,3),(1,0)], [(3,1),(0,2)], [(2,2),(1,1)], [(1,3),(2,0)], [(2,1),(1,2)], [(2,1),(1,1),(0,1)], [(3,0),(0,2),(0,1)], [(2,2),(1,0),(0,1)], [(2,1),(0,2),(1,0)], [(1,2),(2,0),(0,1)], [(1,2),(1,1),(1,0)], [(0,3),(2,0),(1,0)], [(2,0),(1,1),(0,2)], [(2,0),(0,2),(1,0),(0,1)].
Square array A(n,k) begins:
  1,  1,   1,      1,          1,            1,         1, ...
  1,  1,   2,      5,         15,           52,       203, ...
  1,  1,   5,     40,        457,         6995,    136771, ...
  1,  2,  17,    364,      14595,       937776,  88507276, ...
  1,  2,  46,   2897,     407287,    107652681,  ...
  1,  3, 123,  21369,   10200931,  10781201973,  ...
  1,  4, 323, 148257,  233051939,  ...
  1,  5, 809, 970246, 4909342744,  ...

Mathematica

f[n_, k_] := f[n, k] = 1/2 Product[Sum[O[x[j]]^(n+1), {j, 1, k}]+1+ Product[x[j]^i[j], {j, 1, k}], Evaluate[Sequence @@ Table[{i[j], 0, n}, {j, 1, k}]]];
a[0, _] = a[_, 0] = 1; a[n_, k_] := SeriesCoefficient[f[n, k], Sequence @@ Table[{x[j], 0, n}, {j, 1, k}]];
Table[Print[a[n-k, k]]; a[n-k, k], {n, 0, 9}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Dec 11 2013, updated Sep 16 2019 *)

Prog

(PARI)
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); EulerT(v)[n]^k/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))/(1+x))); if(n==0, 1, (-1)^m*sum(j=0, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*q[#q-j])/2)} \\ Andrew Howroyd, Dec 16 2018

Crossrefs

Columns k=0..5 give: A000012, A000009, A219554, A219560, A219561, A219565.

Rows n=0..3 give: A000012, A000110, A094574, A319591.

Cf. A188445, A219727 (partitions of {n}^k into k-tuples), A318286.

Sequence in context: A121395 A275377 A384437 * A292464 A090628 A054387

Adjacent sequences: A219582 A219583 A219584 * A219586 A219587 A219588

Keyword

nonn,tabl

Author

Alois P. Heinz, Nov 23 2012

Status

approved