A261983 Number of compositions of n such that at least two adjacent parts are equal.

0, 0, 1, 1, 4, 9, 18, 41, 89, 185, 388, 810, 1670, 3435, 7040, 14360, 29226, 59347, 120229, 243166, 491086, 990446, 1995410, 4016259, 8076960, 16231746, 32599774, 65437945, 131293192, 263316897, 527912140, 1058061751, 2120039885, 4246934012, 8505864640

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

a(n) ~ 2^(n-1). - Vaclav Kotesovec, Sep 08 2015

a(n) = A011782(n) - A003242(n). - Emeric Deutsch, Jul 03 2020

Example

a(5) = 9: 311, 113, 221, 122, 2111, 1211, 1121, 1112, 11111.
From Gus Wiseman, Jul 07 2020: (Start)
The a(2) = 1 through a(6) = 18 compositions:
  (1,1)  (1,1,1)  (2,2)      (1,1,3)      (3,3)
                  (1,1,2)    (1,2,2)      (1,1,4)
                  (2,1,1)    (2,2,1)      (2,2,2)
                  (1,1,1,1)  (3,1,1)      (4,1,1)
                             (1,1,1,2)    (1,1,1,3)
                             (1,1,2,1)    (1,1,2,2)
                             (1,2,1,1)    (1,1,3,1)
                             (2,1,1,1)    (1,2,2,1)
                             (1,1,1,1,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)
(End)

Maple

b:= proc(n, i) option remember; `if`(n=0, 0, add(
      `if`(i=j, ceil(2^(n-j-1)), b(n-j, j)), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], MatchQ[#, {___, x_, x_, ___}]&]], {n, 0, 10}] (* Gus Wiseman, Jul 06 2020 *)
b[n_, i_] := b[n, i] = If[n == 0, 0, Sum[If[i == j, Ceiling[2^(n-j-1)], b[n-j, j]], {j, 1, n}]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 20 2023, after Alois P. Heinz's Maple code *)

Crossrefs

Column k=1 of A261981.

Cf. A011782, A262046.

The complement A003242 counts anti-runs.

Sum of positive-indexed terms of row n of A106356.

Row sums of A131044.

The (1,1,1) matching case is A335464.

Strict compositions are A032020.

Compositions with adjacent parts coprime are A167606.

Compositions with equal parts contiguous are A274174.

Cf. A114901, A178470, A242882, A244164, A325534, A335448, A335452.

Sequence in context: A083706 A352667 A229072 * A074896 A015713 A049198

Adjacent sequences: A261980 A261981 A261982 * A261984 A261985 A261986

Keyword

nonn

Author

Alois P. Heinz, Sep 07 2015

Status

approved