A344604 Number of alternating compositions of n, including twins (x,x).

1, 1, 2, 3, 5, 7, 13, 19, 30, 48, 76, 118, 187, 293, 461, 725, 1140, 1789, 2815, 4422, 6950, 10924, 17169, 26979, 42405, 66644, 104738, 164610, 258708, 406588, 639010, 1004287, 1578364, 2480606, 3898600, 6127152, 9629624, 15134213, 23785389, 37381849, 58750469

Offset

0,3

Comments

We define a composition to be alternating including twins (x,x) if there are no adjacent triples (..., x, y, z, ...) where x <= y <= z or x >= y >= z. Except in the case of twins (x,x), all such compositions are anti-runs (A003242). These compositions avoid the weak consecutive patterns (1,2,3) and (3,2,1), the strict version being A344614.

The version without twins (x,x) is A025047 (alternating compositions).

Links

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

Formula

a(n > 0) = A025047(n) + 1 if n is even, otherwise A025047(n). - Gus Wiseman, Nov 03 2021

Example

The a(1) = 1 through a(7) = 19 compositions:
  (1)  (2)   (3)   (4)    (5)    (6)     (7)
       (11)  (12)  (13)   (14)   (15)    (16)
             (21)  (22)   (23)   (24)    (25)
                   (31)   (32)   (33)    (34)
                   (121)  (41)   (42)    (43)
                          (131)  (51)    (52)
                          (212)  (132)   (61)
                                 (141)   (142)
                                 (213)   (151)
                                 (231)   (214)
                                 (312)   (232)
                                 (1212)  (241)
                                 (2121)  (313)
                                         (412)
                                         (1213)
                                         (1312)
                                         (2131)
                                         (3121)
                                         (12121)

Mathematica

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

Crossrefs

A001250 counts alternating permutations.

A005649 counts anti-run patterns.

A025047 counts alternating or wiggly compositions, also A025048, A025049.

A106356 counts compositions by number of maximal anti-runs.

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

A325534 counts separable partitions.

A325535 counts inseparable partitions.

A344605 counts alternating patterns including twins.

A344606 counts alternating permutations of prime factors including twins.

Counting compositions by patterns:

- A011782 no conditions.

- A003242 avoiding (1,1) adjacent.

- A102726 avoiding (1,2,3).

- A106351 avoiding (1,1) adjacent by sum and length.

- A128695 avoiding (1,1,1) adjacent.

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

- A232432 avoiding (1,1,1).

- A335456 all patterns.

- A335457 all patterns adjacent.

- A335514 matching (1,2,3).

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

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

Cf. A000041, A006330, A008965, A238279, A239830, A333213, A238279/A333755, A344612, A344616, A344617, A344618.

Sequence in context: A198273 A066076 A136288 * A175762 A088091 A332088

Adjacent sequences: A344601 A344602 A344603 * A344605 A344606 A344607

Keyword

nonn

Author

Gus Wiseman, May 27 2021

Extensions

a(21)-a(40) from Alois P. Heinz, Nov 04 2021

Status

approved