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,2

Comments

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

Links

Table of n, a(n) for n=0..72.

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

Cf. A115728, A080577, A000108, A007318.

Sequence in context: A089308 A305579 A321440 * A115728 A188553 A335680

Adjacent sequences: A115726 A115727 A115728 * A115730 A115731 A115732

Keyword

nonn

Author

Franklin T. Adams-Watters, Mar 11 2006

Status

approved