login
A115729
Number of subpartitions of partitions in Mathematica order.
12
1, 2, 3, 3, 4, 5, 4, 5, 7, 6, 7, 5, 6, 9, 9, 10, 9, 9, 6, 7, 11, 12, 10, 13, 14, 10, 13, 12, 11, 7, 8, 13, 15, 14, 16, 19, 16, 16, 17, 19, 14, 16, 15, 13, 8, 9, 15, 18, 18, 15, 19, 24, 23, 22, 19, 21, 26, 22, 23, 15, 21, 24, 18, 19, 18, 15, 9, 10, 17, 21, 22, 20, 22
OFFSET
0,2
COMMENTS
subpart([n^k]) = C(n+k,k); subpart([n,n-1,n-2,...,1]) = C_n = A000108(n).
FORMULA
For a partition P = [p_1,...,p_n] with the p_i in decreasing order, define b(i,j) to be the number of subpartitions of [p_1,...,p_i] with the i-th part = j (b(i,0) is subpartitions with less than i parts). Then b(1,j)=1 for j<=p_1, b(i+1,j) = Sum_{k=j}^{p_i} b(i,k) for 0<=k<=p_{i+1}; and the total number of subpartitions is sum_{k=1}^{p_n} b(n,k).
EXAMPLE
Partition 5 in Mathematica order is [2,1]; it has 5
subpartitions: [], [1], [2], [1^2] and [2,1] itself.
PROG
(PARI) /* Expects input as vector in decreasing order - e.g. [3, 2, 1, 1] */ subpart2(p)=local(i, j, v, n, k); n=matsize(p)[2]; if(n==0, 1, v=vector(p[1]+1, i, 1); for(i=1, n, k=p[i]; for(j=1, k, v[k+1-j]+=v[k+2-j])); v[1])
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved