A115729 Number of subpartitions of partitions in Mathematica order.
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
Keywords
Examples
Partition 5 in Mathematica order is [2,1]; it has 5 subpartitions: [], [1], [2], [1^2] and [2,1] itself.
Programs
-
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])
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).
Comments