OFFSET
2,4
COMMENTS
Let T^(n)_m denote the number of partitions of mn that can be obtained by adding together m (not necessarily distinct) partitions of n (see A213086). For T^(n)_2, T^(n)_3, T^(n)_4, T^(n)_5 see A002219 through A002222.
Metropolis and Stein show that T^(n)_m is given by the formula
T^(n)_m = Sum_{k=0..n-g-1} binomial(m+g,g+k) c(n,k), where g = floor((n+1)/2).
LINKS
N. Metropolis and P. R. Stein, An elementary solution to a problem in restricted partitions, J. Combin. Theory, 9 (1970), 365-376.
EXAMPLE
Triangle c(n,k) begins:
n\k
- 0 1 2 3 4 5 ...
---------------------------------
2 1
3 1
4 1 2
5 1 3
6 1 7 8
7 1 10 14
8 1 17 50 36
9 1 24 89 78
10 1 36 207 368 200
11 1 49 340 701 431
12 1 70 685 2190 2756 1188
13 1 93 1075 3935 5564 2658
...
MAPLE
with(combinat):
h:= proc(n, m) option remember;
`if`(m>1, map(x-> map(y-> sort([x[], y[]]), h(n, 1))[],
h(n, m-1)), `if`(m=1, map(x->map(y-> `if`(y>1, y-1, NULL), x),
{partition(n)[]}), {[]}))
end:
T:= proc(n) local i, g, t;
g:= floor((n+1)/2);
subs(solve({seq(nops(h(n, t))=add(c||i *binomial(t+g, g+i),
i=0..n-g-1), t=1..n-g)}, {seq(c||i, i=0..n-g-1)}),
[seq(c||i, i=0..n-g-1)])[]
end:
seq(T(n), n=2..10); # Alois P. Heinz, Jul 11 2012
MATHEMATICA
nmax = 13; mmax = 5;
T[n_, m_] := T[n, m] = Module[{ip, lg, i}, ip = IntegerPartitions[n]; lg = Length[ip]; i[0] = 1; Table[ Join[ Sequence @@ Table[ip[[i[k]]], {k, 1, m}]] // Sort, Evaluate[Sequence @@ Table[{i[k], i[k - 1], lg}, {k, 1, m}]]] // Flatten[#, m - 1] & // Union // Length]; T[_, 0] = 1;
U[n_, m_] := With[{g = Floor[(n + 1)/2]}, If[n == 1, 1, Sum[Binomial[m + g, g + k] c[n, k], {k, 0, n - g - 1}]]];
Do[TT = Table[T[n , m] - U[n , m], {n, 1, nmax}, {m, 0, mm}] // Flatten; c[_, 0] = 1; sol = Solve[Thread[TT == 0]][[1]]; cc = Table[c[n, k], {n, 2, nmax}, {k, 0, Floor[(n - 2)/2]}] /. sol // Flatten; Print[cc], {mm, 2, mmax}];
cc (* Jean-François Alcover, May 25 2016 *)
CROSSREFS
KEYWORD
nonn,tabf,more
AUTHOR
N. J. A. Sloane, Jun 04 2012
EXTENSIONS
12 more terms (rows 12-13) from Alois P. Heinz, Jul 11 2012
STATUS
approved