A348382 Number of compositions of n that are not a twin (x,x) but have adjacent equal parts.

0, 0, 0, 1, 3, 9, 17, 41, 88, 185, 387, 810, 1669, 3435, 7039, 14360, 29225, 59347, 120228, 243166, 491085, 990446, 1995409, 4016259, 8076959, 16231746, 32599773, 65437945, 131293191, 263316897, 527912139, 1058061751, 2120039884, 4246934012, 8505864639

Offset

0,5

Comments

A composition with no adjacent equal parts is also called a Carlitz composition, so these are non-twin, non-Carlitz compositions.

Links

Table of n, a(n) for n=0..34.

A. Knopfmacher and H. Prodinger, On Carlitz Compositions, Europ. J. Combinatorics (1998) 19, 579-589.

Wikipedia, Composition (combinatorics)

Formula

For n > 0, a(n) = A261983(n) - A059841(n).

O.g.f.: 1 + x/(1-2x) - x^2/(1-x^2) - 1/(1 - Sum_{k>0} x^k/(1+x^k)).

Example

The a(3) = 1 through a(6) = 17 compositions:
  (111)  (112)   (113)    (114)
         (211)   (122)    (222)
         (1111)  (221)    (411)
                 (311)    (1113)
                 (1112)   (1122)
                 (1121)   (1131)
                 (1211)   (1221)
                 (2111)   (1311)
                 (11111)  (2112)
                          (2211)
                          (3111)
                          (11112)
                          (11121)
                          (11211)
                          (12111)
                          (21111)
                          (111111)

Mathematica

nn=15; CoefficientList[Series[1+x/(1-2x)-x^2/(1-x^2)-1/(1-Sum[x^k/(1+x^k), {k, 1, nn}]), {x, 0, nn}], x]

Crossrefs

Allowing twins gives A261983, complement A003242.

The non-alternating case is A348377, difference A345195.

These compositions are ranked by A348612 \ A007582.

A001250 counts alternating permutations, complement A348615.

A007582 ranks twin compositions.

A011782 counts compositions, strict A032020.

A025047 counts alternating or wiggly compositions, complement A345192.

A051049 counts non-twin compositions, complement A000035(n+1).

A325534 counts separable partitions, ranked by A335433.

A325535 counts inseparable partitions, ranked by A335448.

Cf. A000070, A005649, A059841, A106356, A238279, A333755, A344604, A344614, A344740, A348381.

Sequence in context: A011755 A262466 A128301 * A176148 A206701 A176354

Adjacent sequences: A348379 A348380 A348381 * A348383 A348384 A348385

Keyword

nonn

Author

Gus Wiseman, Nov 05 2021

Status

approved