A243820 -id:A243820 - cp's OEIS frontend

A120304 Catalan numbers minus 2.

-1, -1, 0, 3, 12, 40, 130, 427, 1428, 4860, 16794, 58784, 208010, 742898, 2674438, 9694843, 35357668, 129644788, 477638698, 1767263188, 6564120418, 24466267018, 91482563638, 343059613648, 1289904147322, 4861946401450, 18367353072150, 69533550916002, 263747951750358

Offset: 0

Alexander Adamchuk, Jul 13 2006

Prime p divides a(p). Prime p divides a(p+1) for p > 2. Prime p divides a((p-1)/2) for p = 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, ... = A002144(n) except 5. Pythagorean primes: primes of form 4n+1. Also A002313(n) except 2, 5. Primes congruent to 1 or 2 modulo 4; or, primes of form x^2+y^2; or, -1 is a square mod p. p^2 divides a(p^2) and a(p^2+1) for all prime p.

For n >= 2, number of Dyck paths of semilength n such that all four consecutive step patterns of length 2 occur at least once; a(3)=3: UDUUDD, UUDDUD, UUDUDD. For each n two paths do not satisfy the condition: U^{n}D^{n} and (UD)^n. - Alois P. Heinz, Jun 13 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2. [The sequence here begins 1, 1, 1, 3, 12, 40, 130, 427, 1428, 4860, ...]

Cf. A000108, A002144, A002313.

Cf. A243882, A243820.

a:= n-> binomial(2*n, n)/(n+1) -2:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 13 2014

Table[(2n)!/n!/(n+1)!-2,{n,0,30}]
CatalanNumber[Range[0,30]]-2 (* Harvey P. Dale, May 03 2019 *)

combinat::dyckWords::count(n)-2 $ n = 0..38; // Zerinvary Lajos, May 08 2008

a(n) = binomial(2*n, n)/(n+1)-2; \\ Altug Alkan, Dec 17 2017

a(n) = A000108(n) - 2.
a(n) = (2n)!/(n!*(n+1)!) - 2.
(n+1)*a(n) + 2*(-3*n+1)*a(n-1) + (9*n-13)*a(n-2) + 2*(-2*n+5)*a(n-3) = 0. - R. J. Mathar, May 30 2014

A242257 Number of binary words of length n that contain all sixteen 4-bit words as (possibly overlapping) contiguous subwords.

Original entry on oeis.org

256, 1344, 5376, 19028, 61808, 188474, 547350, 1522758, 4083256, 10620590, 26912658, 66671138, 161950112, 386663750, 909204980, 2109158718, 4834062186, 10960141396, 24608994426, 54771900982, 120939714274, 265121486866, 577386711942, 1249925021562, 2691031388142

Offset: 19

Alois P. Heinz, May 09 2014

nonn

The expected wait time to see all sixteen 4-bit words is Sum_{n>=0} (1-a(n)/2^n) ~ 58.632877... (with a(n) = 0 for 0 <= n <= 18).

			a(19) = 256: 0000100110101111000, 0000100111101011000, 0000101001101111000, ..., 1111010110010000111, 1111011000010100111, 1111011001010000111.

Alois P. Heinz, Table of n, a(n) for n = 19..2000
Eric Weisstein's World of Mathematics, Coin Tossing
Wikipedia, Deterministic finite automaton

Cf. A001146, A052944, A242167, A242206, A242323, A243820.

b:=
proc(n, l) option remember; local m; m:= min(l[]);
  `if`(m=5, 2^n, `if`(5-m>n, 0,        b(n-1, [   [2, 3, 4, 5, 5][l[1]],
  [1, 1, 1, 1, 5][l[2]],  [2, 3, 4, 4, 5][l[3]],  [1, 1, 1, 5, 5][l[4]],
  [2, 3, 3, 5, 5][l[5]],  [1, 1, 4, 1, 5][l[6]],  [2, 2, 4, 5, 5][l[7]],
  [1, 3, 1, 3, 5][l[8]],  [1, 3, 4, 5, 5][l[9]],  [2, 2, 2, 2, 5][l[10]],
  [2, 3, 3, 2, 5][l[11]], [1, 1, 4, 5, 5][l[12]], [2, 2, 2, 5, 5][l[13]],
  [1, 3, 4, 1, 5][l[14]], [2, 2, 4, 2, 5][l[15]], [1, 3, 1, 5, 5][l[16]]])+
  b(n-1, [                [1, 1, 1, 1, 5][l[1]],  [2, 3, 4, 5, 5][l[2]],
  [1, 1, 1, 5, 5][l[3]],  [2, 3, 4, 4, 5][l[4]],  [1, 1, 4, 1, 5][l[5]],
  [2, 3, 3, 5, 5][l[6]],  [1, 3, 1, 3, 5][l[7]],  [2, 2, 4, 5, 5][l[8]],
  [2, 2, 2, 2, 5][l[9]],  [1, 3, 4, 5, 5][l[10]], [1, 1, 4, 5, 5][l[11]],
  [2, 3, 3, 2, 5][l[12]], [1, 3, 4, 1, 5][l[13]], [2, 2, 2, 5, 5][l[14]],
  [1, 3, 1, 5, 5][l[15]], [2, 2, 4, 2, 5][l[16]]])))
end:
a:= n-> b(n, [1$16]):
seq(a(n), n=19..40);

A243882 Number of Dyck paths of semilength n such that all eight consecutive step patterns of length 3 occur at least once.

Original entry on oeis.org

1, 21, 124, 636, 2749, 11265, 44028, 168673, 636526, 2385703, 8903294, 33177968, 123602040, 460821006, 1720240295, 6432225711, 24095079682, 90435264009, 340097165156, 1281506663877, 4838093967400, 18299480354681, 69340086808691, 263195643048634

Offset: 5

Alois P. Heinz, Jun 13 2014

nonn

			a(5) = 1: 1011100010.
a(6) = 21: 101011100010, 101110001010, 101110100010, 101111000010, 101111000100, 101111001000, 110010111000, 110011101000, 110100111000, 110111000010, 110111000100, 110111001000, 111000101100, 111000110100, 111001011000, 111001101000, 111010001100, 111010011000, 111011000010, 111011000100, 111011001000.
Here 1=Up=(1,1), 0=Down=(1,-1).

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 5..1000 (first 500 terms from Alois P. Heinz)
Vaclav Kotesovec, Recurrence (of order 14)

Cf. A242167, A243820.

b:= proc(x, y, t, s) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, `if`(s={}, 1, 0), `if`(nops(s)>x, 0, add(
      b(x-1, y-1+2*j, irem(2*t+j, 4), s minus {2*t+j}), j=0..1))))
    end:
a:= n-> add(b(2*n-2, l[], {$0..7}), l=[[0, 2], [2, 3]]):
seq(a(n), n=5..35);

b[x_, y_, t_, s_List] := b[x, y, t, s] = If[y<0 || y>x, 0, If[x == 0, If[s == {}, 1, 0], If[Length[s]>x, 0, Sum[b[x-1, y-1 + 2*j, Mod[2*t+j, 4], s ~Complement~ {2*t + j}], {j, 0, 1}]]]]; a[n_] :=  Sum[b[2*n-2, Sequence @@ l, Range[0, 7]], {l, {{0, 2}, {2, 3}}}]; Table[a[n], {n, 5, 35}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)

a(n) ~ 4^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 15 2014

A243966 Number of Dyck paths of semilength n such that all five consecutive patterns of Dyck paths of semilength 3 occur at least once.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 138, 1152, 8166, 52098, 308964, 1733444, 9311300, 48280464, 243112106, 1194286106, 5744306228, 27129749648, 126111332862, 578106334718, 2617667137358, 11723920607410, 51998857149406, 228621028644376, 997286152915772

Offset: 0

Alois P. Heinz, Jun 16 2014

nonn

The five consecutive patterns that occur at least once each are 101010, 101100, 110010, 110100, 111000. Here 1=Up=(1,1), 0=Down=(1,-1).

			a(12) = 12: 101010110010110100111000, 101010110010111000110100, 101100101010110100111000, 101100101010111000110100, 110100101010110010111000, 110100101100101010111000, 110100111000101010110010, 110100111000101100101010, 111000101010110010110100, 111000101100101010110100, 111000110100101010110010, 111000110100101100101010.
Here 1=Up=(1,1), 0=Down=(1,-1).

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

Cf. A014486, A063171, A243820, A243965, A243986.

b:= proc(x, y, l) option remember; local m; m:= min(l[]);
      `if`(y>x or y<0 or 7-m>x, 0, `if`(x=0, 1,
      b(x-1, y+1, [[2, 3, 4, 4, 2, 2, 7][l[1]],
       [2, 3, 3, 5, 3, 2, 7][l[2]], [2, 3, 3, 2, 6, 3,7][l[3]],
       [2, 2, 4, 5, 2, 4, 7][l[4]], [2, 2, 4, 2, 6, 2,7][l[5]]])+
      b(x-1, y-1, [[1, 1, 1, 5, 6, 7, 7][l[1]],
       [1, 1, 4, 1, 6, 7, 7][l[2]], [1, 1, 4, 5, 1, 7, 7][l[3]],
       [1, 3, 1, 3, 6, 7, 7][l[4]], [1, 3, 1, 5, 1, 7, 7][l[5]]])))
    end:
a:= n-> b(2*n, 0, [1$5]):
seq(a(n), n=0..35);

b[x_, y_, l_] := b[x, y, l] = Module[{m = Min[l]},
        If[y>x || y<0 || 7-m>x, 0, If[x == 0, 1,
        b[x-1, y+1, MapIndexed[#1[[l[[#2[[1]] ]] ]]&,
        {{2, 3, 4, 4, 2, 2, 7},
         {2, 3, 3, 5, 3, 2, 7},
         {2, 3, 3, 2, 6, 3, 7},
         {2, 2, 4, 5, 2, 4, 7},
         {2, 2, 4, 2, 6, 2, 7}}]]] +
        b[x-1, y-1, MapIndexed[#1[[l[[#2[[1]] ]] ]]&,
        {{1, 1, 1, 5, 6, 7, 7},
         {1, 1, 4, 1, 6, 7, 7},
         {1, 1, 4, 5, 1, 7, 7},
         {1, 3, 1, 3, 6, 7, 7},
         {1, 3, 1, 5, 1, 7, 7}}]]]];
a[n_] := b[2n, 0, {1, 1, 1, 1, 1}];
a /@ Range[0, 35] (* Jean-François Alcover, Jan 26 2021, after Alois P. Heinz *)

A242450 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive steps UUDDUDUUUUDUDDDDUUDD (with U=(1,1), D=(1,-1)); triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-2)/8)), read by rows.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, 1, 58783, 3, 208002, 10, 742865, 35, 2674314, 126, 9694383, 462, 35355954, 1716, 129638355, 6435, 477614391, 24308, 1, 1767170815, 92372, 3, 6563767715, 352694, 11, 24464914983, 1351996, 41, 91477363496, 5199988

Offset: 0

Alois P. Heinz, Jun 12 2014

UUDDUDUUUUDUDDDDUUDD is a Dyck path that contains all sixteen consecutive step patterns of length 4.

			Triangle T(n,k) begins:
:  0 :           1;
:  1 :           1;
:  2 :           2;
:  3 :           5;
:  4 :          14;
:  5 :          42;
:  6 :         132;
:  7 :         429;
:  8 :        1430;
:  9 :        4862;
: 10 :       16795,       1;
: 11 :       58783,       3;
: 12 :      208002,      10;
: 13 :      742865,      35;
: 14 :     2674314,     126;
: 15 :     9694383,     462;
: 16 :    35355954,    1716;
: 17 :   129638355,    6435;
: 18 :   477614391,   24308,  1;
: 19 :  1767170815,   92372,  3;
: 20 :  6563767715,  352694, 11;
: 21 : 24464914983, 1351996, 41;

Alois P. Heinz, Rows n = 0..500, flattened

Row sums give A000108.
T(834828,k) = A243752(834828,k).
T(n,0) = A243753(n,834828).
Cf. A243820.

b:= proc(x, y, t) option remember; `if`(x=0, 1,
     expand(`if`(y>=x-1, 0, b(x-1, y+1, [2, 3, 3, 2, 6, 3,
       8, 9, 10, 11, 3, 13, 3, 2, 2, 2, 18, 19, 3, 2][t]))+
     `if`(t=20, z, 1)*`if`(y=0, 0, b(x-1, y-1, [1, 1, 4, 5, 1, 7,
       1, 1, 4, 4, 12, 5, 14, 15, 16, 17, 1, 1, 20, 5][t]))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..30);

b[x_, y_, t_] := b[x, y, t] = If[x == 0, 1, Expand[If[y >= x - 1, 0, b[x - 1, y + 1, {2, 3, 3, 2, 6, 3, 8, 9, 10, 11, 3, 13, 3, 2, 2, 2, 18, 19, 3, 2}[[t]]]] + If[t == 20, z, 1]*If[y == 0, 0, b[x - 1, y - 1, {1, 1, 4, 5, 1, 7, 1, 1, 4, 4, 12, 5, 14, 15, 16, 17, 1, 1, 20, 5}[[t]]]]]];
T[n_] := CoefficientList[b[2n, 0, 1], z];
T /@ Range[0, 30] // Flatten (* Jean-François Alcover, Mar 27 2021, after Alois P. Heinz *)

A243965 Number of Dyck paths of semilength n such that both consecutive patterns of Dyck paths of semilength 2 occur at least once.

Original entry on oeis.org

0, 0, 0, 0, 2, 10, 44, 179, 702, 2701, 10278, 38866, 146450, 550817, 2070116, 7779655, 29248932, 110047905, 414446256, 1562538171, 5898049688, 22290789562, 84351810044, 319609669957, 1212552963576, 4606078246284, 17518748817596, 66712192842068, 254346235738120

Offset: 0

Alois P. Heinz, Jun 16 2014

nonn

The consecutive patterns 1010, 1100 are counted. Here 1=Up=(1,1), 0=Down=(1,-1).

			a(4) = 2: 10101100, 11001010.
a(5) = 10: 1010101100, 1010110010, 1010111000, 1011001010, 1100101010, 1100110100, 1101001100, 1101011000, 1110001010, 1110010100.
Here 1=Up=(1,1), 0=Down=(1,-1).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Vaclav Kotesovec, Recurrence (of order 10)

Cf. A014486, A063171, A243820, A243966.

b:= proc(x, y, t, s) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, `if`(s={}, 1, 0), `if`(nops(s)>x, 0, add(
      b(x-1, y-1+2*j, irem(2*t+j, 8), s minus {2*t+j}), j=0..1))))
    end:
a:= n->  b(2*n, 0, 0, {10, 12}):
seq(a(n), n=0..30);

b[x_, y_, t_, s_] := b[x, y, t, s] = If[y<0 || y>x, 0, If[x == 0, If[s == {}, 1, 0], If[Length[s] > x, 0, Sum[b[x - 1, y - 1 + 2 j, Mod[2t + j, 8], s ~Complement~ {2t + j}], {j, 0, 1}]]]];
a[n_] := b[2n, 0, 0, {10, 12}];
a /@ Range[0, 30] (* Jean-François Alcover, Dec 21 2020, after Alois P. Heinz *)

a(n) ~ 4^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 18 2014

A243838 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive steps UDUUDDUUUUDUDDDDUDUD (with U=(1,1), D=(1,-1)); triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/9)), read by rows.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, 1, 58783, 3, 208002, 10, 742865, 35, 2674314, 126, 9694383, 462, 35355954, 1716, 129638355, 6435, 477614390, 24310, 1767170813, 92376, 1, 6563767708, 352708, 4, 24464914958, 1352046, 16, 91477363405, 5200170, 65

Offset: 0

Alois P. Heinz, Jun 11 2014

UDUUDDUUUUDUDDDDUDUD is a Dyck path that contains all sixteen consecutive step patterns of length 4.

			Triangle T(n,k) begins:
:  0 :           1;
:  1 :           1;
:  2 :           2;
:  3 :           5;
:  4 :          14;
:  5 :          42;
:  6 :         132;
:  7 :         429;
:  8 :        1430;
:  9 :        4862;
: 10 :       16795,       1;
: 11 :       58783,       3;
: 12 :      208002,      10;
: 13 :      742865,      35;
: 14 :     2674314,     126;
: 15 :     9694383,     462;
: 16 :    35355954,    1716;
: 17 :   129638355,    6435;
: 18 :   477614390,   24310;
: 19 :  1767170813,   92376,  1;
: 20 :  6563767708,  352708,  4;
: 21 : 24464914958, 1352046, 16;

Alois P. Heinz, Rows n = 0..350, flattened

Row sums give A000108.
T(736522,k) = A243752(736522,k).
T(n,0) = A243753(n,736522).
Cf. A243820.

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, expand(b(x-1, y+1, [2, 2, 4, 5, 2, 4,
       8, 9, 10, 11, 2, 13, 5, 4, 2, 2, 18, 2, 20, 5][t])
      +`if`(t=20, z, 1) *b(x-1, y-1, [1, 3, 1, 3, 6, 7,
       1, 3, 3, 3, 12, 1, 14, 15, 16, 17, 1, 19, 1, 3][t]))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..30);

b[x_, y_, t_] := b[x, y, t] = If[x == 0, 1, Expand[If[y >= x - 1, 0, b[x - 1, y + 1, {2, 2, 4, 5, 2, 4, 8, 9, 10, 11, 2, 13, 5, 4, 2, 2, 18, 2, 20, 5}[[t]]]] + If[t == 20, z, 1]*If[y == 0, 0, b[x - 1, y - 1, {1, 3, 1, 3, 6, 7, 1, 3, 3, 3, 12, 1, 14, 15, 16, 17, 1, 19, 1, 3}[[t]]]]]];
T[n_] := CoefficientList[b[2n, 0, 1], z];
T /@ Range[0, 30] // Flatten (* Jean-François Alcover, Mar 27 2021, after Alois P. Heinz *)

cp's OEIS Frontend

A120304 Catalan numbers minus 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

MuPAD

PARI

Formula

A242257 Number of binary words of length n that contain all sixteen 4-bit words as (possibly overlapping) contiguous subwords.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A243882 Number of Dyck paths of semilength n such that all eight consecutive step patterns of length 3 occur at least once.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A243966 Number of Dyck paths of semilength n such that all five consecutive patterns of Dyck paths of semilength 3 occur at least once.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A242450 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive steps UUDDUDUUUUDUDDDDUUDD (with U=(1,1), D=(1,-1)); triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-2)/8)), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A243965 Number of Dyck paths of semilength n such that both consecutive patterns of Dyck paths of semilength 2 occur at least once.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A243838 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive steps UDUUDDUUUUDUDDDDUDUD (with U=(1,1), D=(1,-1)); triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/9)), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica