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

%I #30 Nov 20 2023 11:29:02

%S 0,0,1,1,4,9,18,41,89,185,388,810,1670,3435,7040,14360,29226,59347,

%T 120229,243166,491086,990446,1995410,4016259,8076960,16231746,

%U 32599774,65437945,131293192,263316897,527912140,1058061751,2120039885,4246934012,8505864640

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

%H Alois P. Heinz, <a href="/A261983/b261983.txt">Table of n, a(n) for n = 0..1000</a>

%F a(n) ~ 2^(n-1). - _Vaclav Kotesovec_, Sep 08 2015

%F a(n) = A011782(n) - A003242(n). - _Emeric Deutsch_, Jul 03 2020

%e a(5) = 9: 311, 113, 221, 122, 2111, 1211, 1121, 1112, 11111.

%e From _Gus Wiseman_, Jul 07 2020: (Start)

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

%e (1,1) (1,1,1) (2,2) (1,1,3) (3,3)

%e (1,1,2) (1,2,2) (1,1,4)

%e (2,1,1) (2,2,1) (2,2,2)

%e (1,1,1,1) (3,1,1) (4,1,1)

%e (1,1,1,2) (1,1,1,3)

%e (1,1,2,1) (1,1,2,2)

%e (1,2,1,1) (1,1,3,1)

%e (2,1,1,1) (1,2,2,1)

%e (1,1,1,1,1) (1,3,1,1)

%e (2,1,1,2)

%e (2,2,1,1)

%e (3,1,1,1)

%e (1,1,1,1,2)

%e (1,1,1,2,1)

%e (1,1,2,1,1)

%e (1,2,1,1,1)

%e (2,1,1,1,1)

%e (1,1,1,1,1,1)

%e (End)

%p b:= proc(n, i) option remember; `if`(n=0, 0, add(

%p `if`(i=j, ceil(2^(n-j-1)), b(n-j, j)), j=1..n))

%p end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=0..40);

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{___,x_,x_,___}]&]],{n,0,10}] (* _Gus Wiseman_, Jul 06 2020 *)

%t 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}]];

%t a[n_] := b[n, 0];

%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Nov 20 2023, after _Alois P. Heinz_'s Maple code *)

%Y Column k=1 of A261981.

%Y Cf. A011782, A262046.

%Y The complement A003242 counts anti-runs.

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

%Y Row sums of A131044.

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

%Y Strict compositions are A032020.

%Y Compositions with adjacent parts coprime are A167606.

%Y Compositions with equal parts contiguous are A274174.

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

%K nonn

%O 0,5

%A _Alois P. Heinz_, Sep 07 2015