login
Number of compositions of n with parts in N which avoid the adjacent pattern 111.
20

%I #49 Jul 09 2020 08:04:05

%S 1,1,2,3,7,13,24,46,89,170,324,618,1183,2260,4318,8249,15765,30123,

%T 57556,109973,210137,401525,767216,1465963,2801115,5352275,10226930,

%U 19541236,37338699,71345449,136324309,260483548,497722578,951030367

%N Number of compositions of n with parts in N which avoid the adjacent pattern 111.

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

%H S. Heubach and T. Mansour, <a href="http://arXiv.org/abs/math.CO/0603285">Enumeration of 3-letter patterns in compositions</a>, arXiv:math/0603285 [math.CO], 2006

%H Gus Wiseman, <a href="https://oeis.org/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>

%F G.f.: 1/(1-Sum(i>=1, x^i*(1+x^i)/(1+x^i*(1+x^i)) ) ).

%F a(n) ~ c * d^n, where d is the root of the equation Sum_{k>=1} 1/(d^k + 1/(1 + d^k)) = 1, d=1.9107639262818041675000243699745706859615884029961947632387839..., c=0.4993008137128378086219448701860326113802027003939127932922782... - _Vaclav Kotesovec_, May 01 2014, updated Jul 07 2020

%F For n>=2, a(n) = A091616(n) + A003242(n). - _Vaclav Kotesovec_, Jul 07 2020

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

%e The a(0) = 1 through a(5) = 13 compositions:

%e () (1) (2) (3) (4) (5)

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

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

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

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

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

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

%e (1,3,1)

%e (2,1,2)

%e (2,2,1)

%e (3,1,1)

%e (1,1,2,1)

%e (1,2,1,1)

%e (End)

%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-> b(n, 0):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Nov 23 2013

%t nn=33;CoefficientList[Series[1/(1-Sum[(x^i+x^(2i))/(1+x^i+x^(2i)),{i,1,nn}]),{x,0,nn}],x] (* _Geoffrey Critzer_, Nov 23 2013 *)

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

%Y Column k=0 of A232435.

%Y Cf. A091616, A232432.

%Y The matching version is A335464.

%Y Contiguously (1,1)-avoiding compositions is A003242.

%Y Contiguously (1,1)-matching compositions are A261983.

%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 with adjacent parts coprime are A167606.

%Y Compositions with equal parts contiguous are A274174.

%Y Patterns contiguously matched by compositions are A335457.

%Y Patterns contiguously matched by a given partition are A335516.

%Y Cf. A005251, A032020, A131044, A178470, A242882, A333175, A335455.

%K nonn

%O 0,3

%A _Ralf Stephan_, May 08 2007