A353860 Number of collapsible integer compositions of n.

0, 1, 2, 2, 5, 2, 12, 2, 26, 9, 36, 2, 206, 2, 132, 40, 677, 2, 1746, 2, 3398, 136, 2052, 2, 44388, 33, 8196, 730, 79166, 2, 263234, 2, 458330, 2056, 131076, 160, 8804349, 2, 524292, 8200, 13662156, 2, 36036674, 2, 48844526, 90282, 8388612, 2, 1971667502, 129

Offset

0,3

Comments

If a collapse is a joining of some number of adjacent equal parts of an integer composition, we call a composition collapsible iff by some sequence of collapses it can be reduced to a single part. An example of such a sequence of collapses is (1,1,1,3,2,1,1,2) -> (3,3,2,1,1,2) -> (3,3,2,2,2) -> (6,2,2,2) -> (6,6) -> (12), which shows that (1,1,1,3,2,1,1,2) is a collapsible composition of 12.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Formula

Sum_{d|n} mu(d)*a(n/d)^d = 1 for n > 0. - Andrew Howroyd, Feb 04 2023

Example

The a(0) = 0 through a(6) = 12 compositions:
  .  (1)  (2)   (3)    (4)     (5)      (6)
          (11)  (111)  (22)    (11111)  (33)
                       (112)            (222)
                       (211)            (1113)
                       (1111)           (1122)
                                        (2112)
                                        (2211)
                                        (3111)
                                        (11112)
                                        (11211)
                                        (21111)
                                        (111111)

Mathematica

repcams[q_List]:=repcams[q]=Union[{q}, If[UnsameQ@@q, {}, Union@@repcams/@ Union[Insert[Drop[q, #], Plus@@Take[q, #], First[#]]&/@ Select[Tuples[Range[Length[q]], 2], And[Less@@#, SameQ@@Take[q, #]]&]]]];
Table[Length[Select[Join@@Permutations/@ IntegerPartitions[n], MemberQ[repcams[#], {n}]&]], {n, 0, 15}]

Prog

(PARI) a(n) = if(n==0, 0, 1 - sumdiv(n, d, if(d>1, moebius(d)*a(n/d)^d ))) \\ Andrew Howroyd, Feb 04 2023

Crossrefs

The version for partitions is A275870, ranked by A300273.

A003242 counts anti-run compositions, ranked by A333489, complement A261983.

A011782 counts compositions.

A353847 represents the run-sums of a composition, partitions A353832.

A353853-A353859 pertain to composition run-sum trajectory.

A353932 lists run-sums of standard compositions.

Cf. A237685, A238279, A304442, A318928, A333755, A353844, A353848, A353849, A353850, A353852.

Sequence in context: A211932 A213642 A344753 * A303073 A068058 A192233

Adjacent sequences: A353857 A353858 A353859 * A353861 A353862 A353863

Keyword

nonn

Author

Gus Wiseman, Jun 04 2022

Extensions

Terms a(16) and beyond from Andrew Howroyd, Feb 04 2023

Status

approved