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

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

Table of n, a(n) for n=1..50.

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

Formula

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

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 *)

Crossrefs

Cf. A002577, A145515, A018818.

Sequence in context: A207329 A348219 A122977 * A321721 A359102 A003980

Adjacent sequences: A275867 A275868 A275869 * A275871 A275872 A275873

Keyword

nonn

Author

Gus Wiseman, Aug 11 2016

Status

approved