%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