login
Number of non-alternating compositions of n.
59

%I #19 Jan 31 2024 15:57:05

%S 0,0,1,1,4,9,20,45,99,208,437,906,1862,3803,7732,15659,31629,63747,

%T 128258,257722,517339,1037652,2079984,4167325,8346204,16710572,

%U 33449695,66944254,133959021,268028868,536231903,1072737537,2145905285,4292486690,8586035993,17173742032,34350108745,68704342523,137415168084

%N Number of non-alternating compositions of n.

%C First differs from A261983 at a(6) = 20, A261983(6) = 18.

%C A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).

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

%F a(n) = A011782(n) - A025047(n).

%e The a(2) = 1 through a(6) = 20 compositions:

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

%e (112) (122) (114)

%e (211) (221) (123)

%e (1111) (311) (222)

%e (1112) (321)

%e (1121) (411)

%e (1211) (1113)

%e (2111) (1122)

%e (11111) (1131)

%e (1221)

%e (1311)

%e (2112)

%e (2211)

%e (3111)

%e (11112)

%e (11121)

%e (11211)

%e (12111)

%e (21111)

%e (111111)

%t wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];

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

%Y The complement is counted by A025047 (ascend: A025048, descend: A025049).

%Y Dominates A261983 (non-anti-run compositions), ranked by A348612.

%Y These compositions are ranked by A345168, complement A345167.

%Y The case without twins is A348377.

%Y The version for factorizations is A348613.

%Y A001250 counts alternating permutations, complement A348615.

%Y A003242 counts anti-run compositions.

%Y A011782 counts compositions.

%Y A032020 counts strict compositions.

%Y A106356 counts compositions by number of maximal anti-runs.

%Y A114901 counts compositions where each part is adjacent to an equal part.

%Y A274174 counts compositions with equal parts contiguous.

%Y A325534 counts separable partitions, ranked by A335433.

%Y A325535 counts inseparable partitions, ranked by A335448.

%Y A344604 counts alternating compositions with twins.

%Y A344605 counts alternating patterns with twins.

%Y A344654 counts non-twin partitions with no alternating permutation.

%Y A345162 counts normal partitions with no alternating permutation.

%Y A345164 counts alternating permutations of prime indices.

%Y A345170 counts partitions w/ alternating permutation, ranked by A345172.

%Y A345165 counts partitions w/o alternating permutation, ranked by A345171.

%Y Patterns:

%Y - A128761 avoiding (1,2,3) adjacent.

%Y - A344614 avoiding (1,2,3) and (3,2,1) adjacent.

%Y - A344615 weakly avoiding (1,2,3) adjacent.

%Y Cf. A000070, A008965, A178470, A238279, A333755, A335126, A344606, A344653, A344740, A345163, A345166, A345169, A345173, A348380.

%K nonn

%O 0,5

%A _Gus Wiseman_, Jun 17 2021