A122697 Number of indecomposable partitions of n.

0, 2, 3, 2, 7, 5, 15, 14, 24, 28, 56, 52, 101, 105, 155, 189, 297, 310, 490, 536, 747, 890, 1255, 1380, 1930, 2234, 2928, 3433, 4565, 5133, 6842, 7881, 9975, 11716, 14778, 17006, 21637, 25035, 30882, 35972, 44583, 51200, 63261, 73115, 88459, 103048

Offset: 1

Author

Franklin T. Adams-Watters, Sep 22 2006

Keywords

• nonn

Comments

A partition is indecomposable if it is not [1] and cannot be represented as the product of two smaller partitions, where the product of two partitions is the multiset of all products of parts from the two multiplicands. Another way to define the product of partitions is to regard the partition as a finite sequence b(k) being the number of parts of size k; then the Dirichlet g.f. of b * c is the product of the Dirichlet g.f.s of b and c.

Examples

			The product of [2,2,1] * [2,1,1] is the partition with parts:
4 4 2
2 2 1
2 2 1
which is [4^2,2^5,1^2]. In terms of Dirichlet g.f.s, this is (2*2^s + 1^s) * (2^s + 2*1^s) = (2*4^s + 5*2^s + 2*1^s).
Of the partitions of 6, [6] = [3] * [2], [4,2] = [2] * [2,1], [3^2] = [3] * [1^2], [2^3] = [2] * [1^3], [2^2,1^2] = [2,1] * [1^2] and [1^6] = [1^3] * [1^2]. This leaves [5,1], [4,1^2], [3,2,1], [3,1^3] and [2,1^4] as the 5 indecomposable partitions of 6.
		

Crossrefs

Cf. A000041, A090751.

Formula

The (formal) Dirichlet generating function for A000041 is Product_{n>1} 1/(1-n^{-s})^a(n). (Formal because this g.f. does not converge for any value of s.)