I would like to contribute an experimental confirmation of the above
result that we have the number $p_n(k)$ of partitions of $k$ into at
most $n$ parts.
This is done by a particularly simple form of Power Group
Enumeration as presented by e.g. Harary and (in a different
publication) Fripertinger. The present case does not involve
generating functions and can in fact be done with Burnside's
lemma. The scenario is that we have two groups permuting the slots and
the elements being placed into these slots. We have $k$ slots and the
symmetric group $S_k$ acting on them. Furthermore $n$ digits go into
the slots and these digits have the symmetric group $S_n$ acting on
them. We can compute the number of configurations by Burnside's lemma
which says to average the number of assignments fixed by the elements
of the power group, which has $n!\times k!$ elements. (The cycle
indices have lower complexity.) But this number
is easy to compute. Suppose we have a permutation $\alpha$ from $S_k$
and a permutation $\beta$ from $S_n.$ If we place the appropriate
number of complete, directed and consecutive copies of a cycle from
$\beta$ on a cycle from $\alpha$ then this assignment is fixed under
the power group action for $(\alpha,\beta)$, and this is possible iff
the length of the cycle from $\beta$ divides the length of the cycle
from $\alpha$. The process yields as many assignments as the length
of the cycle from $\beta.$
This yields the following extremely straightforward Maple program.
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := [];
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
strs :=
proc(k, n)
option remember;
local idx_coord, idx_digits, res, a, b,
flat_a, flat_b, cyc_a, cyc_b, len_a, len_b, p, q;
idx_coord := pet_cycleind_symm(k);
idx_digits := pet_cycleind_symm(n);
res := 0;
for a in idx_coord do
flat_a := pet_flatten_term(a);
for b in idx_digits do
flat_b := pet_flatten_term(b);
p := 1;
for cyc_a in flat_a[2] do
len_a := op(1, cyc_a);
q := 0;
for cyc_b in flat_b[2] do
len_b := op(1, cyc_b);
if len_a mod len_b = 0 then
q := q + len_b;
fi;
od;
p := p*q;
od;
res := res + p*flat_a[1]*flat_b[1];
od;
od;
res;
end;
This is some sample output from the program.
> seq(strs(k, 4), k=1..18);
1, 2, 3, 5, 6, 9, 11, 15, 18, 23, 27, 34, 39, 47, 54, 64, 72, 84
> seq(strs(k, 5), k=1..18);
1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 84, 101, 119, 141
> seq(strs(k, 6), k=1..18);
1, 2, 3, 5, 7, 11, 14, 20, 26, 35, 44, 58, 71, 90, 110, 136, 163, 199
Looking these up in the OEIS we can confirm that we indeed have the
number $p_n(k)$ of partitions into at most $n$ parts. These are the
sequences
OEIS A001400,
OEIS A001401 and
OEIS A001402.
This MSE link points to some sophisticated power group enumeration examples.
Addendum Wed Oct 21 2015. Let me point out that the fact that we
have partitions of $k$ into at most $n$ parts follows by
inspection. The fact that the order does not matter creates multisets
and the digit permutations render multisets with the same shape
indistinguishable from one another, leaving partitions.
Addendum Sat Apr 21 2018. It is quite interesting to see PGE
correctly reproduce the values from the partition function
here. Nonetheless the algorithm admits of a considerable improvement,
namely that there is no need to flatten the permutations because we
can compute the contribution from the cycles of a pair $(\alpha,
\beta)$ by multiplying the number of coverings of a cycle type from
$\alpha$ by the number of instances of the cycle type from $\beta$,
raising the result to the power of the number of instances of the
cycle type from $\alpha.$ This yields the following code, where we
have included a routine to verify the results using the partition
function.
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
strs :=
proc(k, n)
option remember;
local idx_coord, idx_digits, res, term_a, term_b,
v_a, v_b, inst_a, inst_b, len_a, len_b, p, q;
if k = 1 then
idx_coord := [a[1]];
else
idx_coord := pet_cycleind_symm(k);
fi;
if n = 1 then
idx_digits := [a[1]];
else
idx_digits := pet_cycleind_symm(n);
fi;
res := 0;
for term_a in idx_coord do
for term_b in idx_digits do
p := 1;
for v_a in indets(term_a) do
len_a := op(1, v_a);
inst_a := degree(term_a, v_a);
q := 0;
for v_b in indets(term_b) do
len_b := op(1, v_b);
inst_b := degree(term_b, v_b);
if len_a mod len_b = 0 then
q := q + len_b*inst_b;
fi;
od;
p := p*q^inst_a;
od;
res := res +
lcoeff(term_a)*lcoeff(term_b)*p;
od;
od;
res;
end;
part :=
proc(n, k)
option remember;
local res;
if n=0 or k=0 then
return `if`(n=0 and k=0, 1, 0);
fi;
if k=1 then return 1 fi;
res := 0;
if n >= 1 then
res := res + part(n-1, k-1);
fi;
if n >= k then
res := res + part(n-k, k);
fi;
res;
end;
strs_verif := (k, n) -> add(part(k, m), m=1..n);