login
Number of collapsible integer compositions of n.
25

%I #10 Feb 04 2023 14:15:14

%S 0,1,2,2,5,2,12,2,26,9,36,2,206,2,132,40,677,2,1746,2,3398,136,2052,2,

%T 44388,33,8196,730,79166,2,263234,2,458330,2056,131076,160,8804349,2,

%U 524292,8200,13662156,2,36036674,2,48844526,90282,8388612,2,1971667502,129

%N Number of collapsible integer compositions of n.

%C 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.

%H Andrew Howroyd, <a href="/A353860/b353860.txt">Table of n, a(n) for n = 0..1000</a>

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

%e The a(0) = 0 through a(6) = 12 compositions:

%e . (1) (2) (3) (4) (5) (6)

%e (11) (111) (22) (11111) (33)

%e (112) (222)

%e (211) (1113)

%e (1111) (1122)

%e (2112)

%e (2211)

%e (3111)

%e (11112)

%e (11211)

%e (21111)

%e (111111)

%t 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,#]]&]]]];

%t Table[Length[Select[Join@@Permutations/@ IntegerPartitions[n],MemberQ[repcams[#],{n}]&]],{n,0,15}]

%o (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

%Y The version for partitions is A275870, ranked by A300273.

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

%Y A011782 counts compositions.

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

%Y A353853-A353859 pertain to composition run-sum trajectory.

%Y A353932 lists run-sums of standard compositions.

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

%K nonn

%O 0,3

%A _Gus Wiseman_, Jun 04 2022

%E Terms a(16) and beyond from _Andrew Howroyd_, Feb 04 2023