login
Number of compositions of n with a run of length > 2.
12

%I #13 May 21 2021 04:16:45

%S 0,0,0,1,1,3,8,18,39,86,188,406,865,1836,3874,8135,17003,35413,73516,

%T 152171,314151,647051,1329936,2728341,5587493,11424941,23327502,

%U 47567628,96879029,197090007,400546603,813258276,1649761070,3343936929,6772740076,13707639491

%N Number of compositions of n with a run of length > 2.

%C A composition of n is a finite sequence of positive integers summing to n.

%C Also compositions contiguously matching the pattern (1,1,1).

%F a(n) = A011782(n) - A128695(n). - _Alois P. Heinz_, Jul 06 2020

%e The a(3) = 1 through a(7) = 18 compositions:

%e (111) (1111) (1112) (222) (1114)

%e (2111) (1113) (1222)

%e (11111) (3111) (2221)

%e (11112) (4111)

%e (11121) (11113)

%e (12111) (11122)

%e (21111) (11131)

%e (111111) (13111)

%e (21112)

%e (22111)

%e (31111)

%e (111112)

%e (111121)

%e (111211)

%e (112111)

%e (121111)

%e (211111)

%e (1111111)

%p b:= proc(n, t) option remember; `if`(n=0, 1, add(`if`(abs(t)<>j,

%p b(n-j, j), `if`(t=-j, 0, b(n-j, -j))), j=1..n))

%p end:

%p a:= n-> ceil(2^(n-1))-b(n, 0):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Jul 06 2020

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{___,x_,x_,x_,___}]&]],{n,0,10}]

%t (* Second program: *)

%t b[n_, t_] := b[n, t] = If[n == 0, 1, Sum[If[Abs[t] != j,

%t b[n - j, j], If[t == -j, 0, b[n - j, -j]]], {j, 1, n}]];

%t a[n_] := Ceiling[2^(n-1)] - b[n, 0];

%t a /@ Range[0, 40] (* _Jean-François Alcover_, May 21 2021, after _Alois P. Heinz_ *)

%Y Compositions contiguously avoiding (1,1) are A003242.

%Y Compositions with some part > 2 are A008466.

%Y Compositions by number of adjacent equal parts are A106356.

%Y Compositions where each part is adjacent to an equal part are A114901.

%Y Compositions contiguously avoiding (1,1,1) are A128695.

%Y Compositions with adjacent parts coprime are A167606.

%Y Compositions contiguously matching (1,1) are A261983.

%Y Compositions with all equal parts contiguous are A274174.

%Y Patterns contiguously matched by compositions are A335457.

%Y Cf. A005251, A011782, A056986, A032020, A131044, A178470, A242882, A335455, A335458.

%K nonn

%O 0,6

%A _Gus Wiseman_, Jul 06 2020

%E a(23)-a(35) from _Alois P. Heinz_, Jul 06 2020