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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 04 2022
EXTENSIONS
Terms a(16) and beyond from Andrew Howroyd, Feb 04 2023
STATUS
approved