A236970 The number of partitions of n into at least 3 parts from which we can form every partition of n into 3 parts by summing elements.

0, 0, 1, 2, 2, 3, 5, 6, 7, 13, 16, 19, 29, 38, 49, 72, 84, 108, 155, 195, 234, 331, 410, 501, 672, 824, 1006, 1341, 1621, 1981, 2583, 3111, 3740, 4846, 5819, 6957, 8787, 10582, 12606, 15840, 18762, 22386, 27851, 32934, 38824, 47961, 56633, 66577, 81168, 95612

Offset: 1

Author

Jack W Grahl, Feb 02 2014

Keywords

• nonn

Comments

The corresponding partitions with 2 in the definition instead of 3 are the complete partitions, which are counted by A126796.

The qualifier 'into at least 3 parts' is only relevant for n = 1 or 2. It is included because otherwise the condition would be vacuously true for all partitions of 1 and 2. It seems neater to consider that there are no partitions of 1 and 2 of this form.

Examples

			The valid partitions of 5 are (2,1,1,1) and (1,1,1,1,1). Given any partition of 5 into 3 parts, it contains one part of at least 2. Therefore we can make any partition of 5 into 3 parts by joining (2,1,1,1) into three sums. (3, 1, 1) is not a valid partition, since (2,2,1) is a partition of 5 into 3 parts which cannot be made by summing elements from (3,1,1). Therefore a(5) = 2.
		

Links

• Jack W Grahl, Haskell code for generating this sequence

Crossrefs

Cf. A000041. A126796 is the case for 2 instead of 3, A236971 and A236972 are the cases for 4 and 5.

Programs

Mathematica

ric[p_, {x_,y_}] := If[x==0, If[y > Total[p], False, y==0 || AnyTrue[ Reverse@ Union[p], y>=# && ric[ DeleteCases[p, #, 1, 1], {0, y-#}] &]], If[x >= Total[p], False, AnyTrue[ Reverse@ Union@ p, x>=# && ric[ DeleteCases[p, #, 1, 1], {x-#, y}] &]]]; chk[p_] := AllTrue[ Rest /@ IntegerPartitions[Plus @@ p, {3}], ric[p,#] &]; a[n_] := Length@ Select[ IntegerPartitions[n, {3, Infinity}], chk]; Array[a, 24] (* Giovanni Resta, Jul 18 2018 *)