A275870 Number of collapsible integer partitions of n.

1, 2, 2, 4, 2, 7, 2, 10, 5, 9, 2, 34, 2, 11, 10, 36, 2, 64, 2, 60, 12, 15, 2, 320, 7, 17, 23, 94, 2, 297, 2, 202, 16, 21, 14, 1488, 2, 23, 18, 776, 2, 610, 2, 186, 148, 27, 2, 6978, 9, 319

Offset: 1

Author

Gus Wiseman, Aug 11 2016

Keywords

• nonn

Comments

If a collapse is a joining of some number of equal parts of an integer partition p, we say p is collapsible if by some sequence of collapses it can be reduced to a single part. An example of such a sequence of collapses is (32211111)->(332211)->(33222)->(6222)->(66)->(n) which shows that (32211111) is a collapsible partition of n=twelve.

One can show that if n is a power of a prime, then a partition of n is collapsible iff its parts are all divisors of n; so this sequence shares many terms with A145515 (number of partitions of k^n into powers of k) and A018818 (number of partitions of n into divisors of n).

Links

• Gus Wiseman, The first 16 terms illustrated (together with the partial order induced by the collapsing relation)
• Gus Wiseman, Hasse diagram for the case n=16 with full detail

Crossrefs

Cf. A002577, A145515, A018818.

Programs

Mathematica

repcaps[q_List]:=repcaps[q]=Union[{q},If[UnsameQ@@q,{},Union@@repcaps/@Union[Sort[Append[Drop[q,#],Plus@@Take[q,#]],Greater]&/@Select[Tuples[Range[Length[q]],2],And[Less@@#,SameQ@@Take[q,#]]&]]]];
repenum[n_]:=Length[Select[IntegerPartitions[n],MemberQ[repcaps[#],{n}]&]];
Table[repenum[n],{n,1,32}](* Gus Wiseman, Aug 11 2016 *)

Formula

a(2^n)=A002577(n+1).