OFFSET
1,3
COMMENTS
If n is prime, then the number of multinomial coefficients, based on a set of partitions of n at position m, divided by m entirely, less 1 than the number of partitions of numbers for all m.
LINKS
EXAMPLE
n=7;
Set of partitions of n into m=4 parts
[1,1,1,4]
[1,1,2,3]
[1,2,2,2]
number of different parts
[3,1]
[2,1,1]
[1,3]
Multinomial coefficient, divisible by m
4!/(4*(1!*3!))=1
4!/(4*(2!*1!*1!))=2
4!/(4*(1!*3!))=1
Set of partitions of n into m=7 parts
[1,1,1,1,1,1,1]
number of different parts
[7]
Multinomial coefficient, divisible by m
7!/(7*(7!))=1/7
PROG
(Maxima)
/* count number of partitions of n into m parts */
b(n, m):=if n<m then 0 else if m=1 then 1 else b(n-1, m-1)+b(n-m, m);
/* unranking partitions(n, m) , num - numbers partitions of lexicographic order */
array(pa, 100);
gen_partitions(n, m, num, pos):= if n<m then return else
if m=1 then pa[pos]:n else
if num<b(n-1, m-1) then (pa[pos]:1, gen_partitions(n-1, m-1, num, pos+1)) else
if num<b(n-m, m)+b(n-1, m-1) then
(gen_partitions(n-m, m, num-b(n-1, m-1), pos),
for i:0 thru m-1 do pa[i+pos]:pa[i+pos]+1);
FindPo(pa, n, po):=block([k, s] , k:0, po[k]:1, s:pa[0], for i:1 thru n-1 do (if pa[i]=s then po[k]:po[k]+1 else (k:k+1, s:pa[i], po[k]:1)), return (k));
Tep(n, m):=block([d], d:0, for i:0 thru b(n, m)-1 do (gen_partitions(n, m, i, 0), k:FindPo(pa, m, po),
if(denom((m-1)!/prod(po[j]!, j, 0, k))=1) then d:d+1), return(d));
makelist(sum(Tep(n, m), m, 1, n), n, 1, 20);
CROSSREFS
KEYWORD
nonn
AUTHOR
Dmitry Kruchinin, Nov 11 2011
STATUS
approved