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

1, 1, 2, 3, 7, 13, 24, 46, 89, 170, 324, 618, 1183, 2260, 4318, 8249, 15765, 30123, 57556, 109973, 210137, 401525, 767216, 1465963, 2801115, 5352275, 10226930, 19541236, 37338699, 71345449, 136324309, 260483548, 497722578, 951030367

Offset

0,3

Links

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

S. Heubach and T. Mansour, Enumeration of 3-letter patterns in compositions, arXiv:math/0603285 [math.CO], 2006

Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Formula

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

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

For n>=2, a(n) = A091616(n) + A003242(n). - Vaclav Kotesovec, Jul 07 2020

Example

From Gus Wiseman, Jul 06 2020: (Start)
The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)    (3)    (4)      (5)
           (1,1)  (1,2)  (1,3)    (1,4)
                  (2,1)  (2,2)    (2,3)
                         (3,1)    (3,2)
                         (1,1,2)  (4,1)
                         (1,2,1)  (1,1,3)
                         (2,1,1)  (1,2,2)
                                  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,2,1)
                                  (1,2,1,1)
(End)

Maple

b:= proc(n, t) option remember; `if`(n=0, 1, add(`if`(abs(t)<>j,
       b(n-j, j), `if`(t=-j, 0, b(n-j, -j))), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Nov 23 2013

Mathematica

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 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !MatchQ[#, {___, x_, x_, x_, ___}]&]], {n, 13}] (* Gus Wiseman, Jul 06 2020 *)

Crossrefs

Column k=0 of A232435.

Cf. A091616, A232432.

The matching version is A335464.

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

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

Compositions with some part > 2 are A008466

Compositions by number of adjacent equal parts are A106356.

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

Compositions with adjacent parts coprime are A167606.

Compositions with equal parts contiguous are A274174.

Patterns contiguously matched by compositions are A335457.

Patterns contiguously matched by a given partition are A335516.

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

Sequence in context: A075058 A213968 A213967 * A024504 A256494 A344432

Adjacent sequences: A128692 A128693 A128694 * A128696 A128697 A128698

Keyword

nonn

Author

Ralf Stephan, May 08 2007

Status

approved