A115729 - OEIS

%I #4 Mar 31 2012 13:21:30

%S 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,

%T 7,8,13,15,14,16,19,16,16,17,19,14,16,15,13,8,9,15,18,18,15,19,24,23,

%U 22,19,21,26,22,23,15,21,24,18,19,18,15,9,10,17,21,22,20,22

%N Number of subpartitions of partitions in Mathematica order.

%C subpart([n^k]) = C(n+k,k); subpart([n,n-1,n-2,...,1]) = C_n = A000108(n).

%F 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).

%e Partition 5 in Mathematica order is [2,1]; it has 5

%e subpartitions: [], [1], [2], [1^2] and [2,1] itself.

%o (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])

%Y Cf. A115728, A080577, A000108, A007318.

%K nonn

%O 0,2

%A _Franklin T. Adams-Watters_, Mar 11 2006