A354578 - OEIS

%I #9 Jun 12 2022 22:52:29

%S 1,1,2,0,2,1,1,0,3,1,2,0,1,1,0,0,2,2,3,0,3,1,1,0,2,1,1,0,0,0,0,0,4,1,

%T 4,0,2,2,1,0,4,2,2,0,1,1,0,0,1,2,2,0,2,0,1,0,0,0,0,0,0,0,0,0,2,3,3,0,

%U 5,2,2,0,5,1,3,0,1,1,0,0,3,3,5,0,3,1,1

%N Number of ways to choose a divisor of each part of the n-th composition in standard order such that no adjacent divisors are equal.

%C Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4). Then a(n) is the number of integer compositions whose run-sums constitute the n-th composition in standard order (graded reverse-lexicographic, A066099).

%e The terms 2^(n - 1) through 2^n - 1 sum to 2^n. As a triangle:

%e   1

%e   1

%e   2 0

%e   2 1 1 0

%e   3 1 2 0 1 1 0 0

%e   2 2 3 0 3 1 1 0 2 1 1 0 0 0 0 0

%e The a(n) compositions for selected n:

%e   n=1: n=2:   n=8:       n=32:          n=68:        n=130:

%e ----------------------------------------------------------------------

%e   (1)  (2)    (4)        (6)            (4,3)        (6,2)

%e        (1,1)  (2,2)      (3,3)          (2,2,3)      (3,3,2)

%e               (1,1,1,1)  (2,2,2)        (4,1,1,1)    (6,1,1)

%e                          (1,1,1,1,1,1)  (1,1,1,1,3)  (3,3,1,1)

%e                                         (2,2,1,1,1)  (2,2,2,1,1)

%e                                                      (1,1,1,1,1,1,2)

%t stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t antirunQ[y_]:=Length[Split[y]]==Length[y];

%t Table[Length[Select[Tuples[Divisors/@stc[n]],antirunQ]],{n,0,30}]

%Y First column is 1 followed by A000005.

%Y Row-sums are A011782.

%Y Standard compositions are listed by A066099.

%Y Positions of 0's are A354904.

%Y Positions of first appearances are A354905.

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

%Y A005811 counts runs in binary expansion.

%Y A300273 ranks collapsible partitions, counted by A275870.

%Y A353838 ranks partitions with all distinct run-sums, counted by A353837.

%Y A353851 counts compositions with all equal run-sums, ranked by A353848.

%Y A353840-A353846 pertain to partition run-sum trajectory.

%Y A353852 ranks compositions with all distinct run-sums, counted by A353850.

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

%Y A353860 counts collapsible compositions.

%Y A353863 counts run-sum-complete partitions.

%Y A354584 gives run-sums of prime indices, rows ranked by A353832.

%Y Cf. A029837, A124767, A175413, A238279/A333755, A333381, A353847, A353849.

%K nonn,tabf

%O 0,3

%A _Gus Wiseman_, Jun 11 2022