A348377 Number of non-alternating compositions of n, excluding twins (x,x).

0, 0, 0, 1, 3, 9, 19, 45, 98, 208, 436, 906, 1861, 3803, 7731, 15659, 31628, 63747, 128257, 257722, 517338, 1037652, 2079983, 4167325, 8346203, 16710572, 33449694, 66944254, 133959020, 268028868, 536231902, 1072737537, 2145905284, 4292486690, 8586035992

Offset

0,5

Comments

First differs from A348382 at a(6) = 19, A348382(6) = 17. The two non-alternating non-twin compositions of 6 that are not an anti-run are (1,2,3) and (3,2,1).

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). Alternating permutations of multisets are a generalization of alternating or up-down permutations of {1..n}.

Links

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

Wikipedia, Alternating permutation

Formula

For n > 0, a(n) = A345192(n) - 1 if n is even; otherwise A345192(n).

Example

The a(3) = 1 through a(6) = 19 compositions:
  (1,1,1)  (1,1,2)    (1,1,3)      (1,1,4)
           (2,1,1)    (1,2,2)      (1,2,3)
           (1,1,1,1)  (2,2,1)      (2,2,2)
                      (3,1,1)      (3,2,1)
                      (1,1,1,2)    (4,1,1)
                      (1,1,2,1)    (1,1,1,3)
                      (1,2,1,1)    (1,1,2,2)
                      (2,1,1,1)    (1,1,3,1)
                      (1,1,1,1,1)  (1,2,2,1)
                                   (1,3,1,1)
                                   (2,1,1,2)
                                   (2,2,1,1)
                                   (3,1,1,1)
                                   (1,1,1,1,2)
                                   (1,1,1,2,1)
                                   (1,1,2,1,1)
                                   (1,2,1,1,1)
                                   (2,1,1,1,1)
                                   (1,1,1,1,1,1)

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], MatchQ[#, {___, x_, y_, z_, ___}/; x<=y<=z||x>=y>=z]&]], {n, 0, 15}]

Crossrefs

The version for patterns is A000670(n) - A344605(n).

Non-twin compositions are counted by A051049.

The complement is counted by A344604.

An unordered version is A344654.

The complement is ranked by A345167 \/ A007582.

These compositions are ranked by A345168 \ A007582.

Including twins gives A345192, complement A025047.

The version for factorizations is A347706, or A348380 with twins.

The non-anti-run case is A348382.

A001250 counts alternating permutations.

A011782 counts compositions, strict A032020.

A106356 counts compositions by number of maximal anti-runs.

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

A261983 counts non-anti-run compositions, complement A003242.

A325535 counts inseparable partitions, ranked by A335448.

A344614 counts compositions avoiding (1,2,3) and (3,2,1) adjacent.

A345165 = partitions with no alternating permutations, ranked by A345171.

A345170 = partitions with an alternating permutation, ranked by A345172.

Cf. A005649, A178470, A238279, A333755, A335126, A344653, A344740, A345166, A345169, A345173, A348379, A348381.

Sequence in context: A146393 A147431 A329145 * A147334 A147463 A095828

Adjacent sequences: A348374 A348375 A348376 * A348378 A348379 A348380

Keyword

nonn

Author

Gus Wiseman, Oct 26 2021

Extensions

a(26) onwards from Andrew Howroyd, Jan 31 2024

Status

approved