A243882 -id:A243882 - cp's OEIS frontend

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

1, 1, 2, 5, 14, 41, 1, 129, 3, 419, 10, 1395, 35, 4737, 124, 1, 16338, 454, 4, 57086, 1684, 16, 201642, 6305, 65, 718855, 23781, 263, 1, 2583149, 90209, 1077, 5, 9346594, 343809, 4419, 23, 34023934, 1315499, 18132, 105, 124519805, 5050144, 74368, 472, 1

Offset: 0

Alois P. Heinz, Jun 13 2014

UDUUUDDDUD is the only Dyck path of semilength 5 that contains all eight consecutive step patterns of length 3.

			Triangle T(n,k) begins:
:  0 :        1;
:  1 :        1;
:  2 :        2;
:  3 :        5;
:  4 :       14;
:  5 :       41,       1;
:  6 :      129,       3;
:  7 :      419,      10;
:  8 :     1395,      35;
:  9 :     4737,     124,     1;
: 10 :    16338,     454,     4;
: 11 :    57086,    1684,    16;
: 12 :   201642,    6305,    65;
: 13 :   718855,   23781,   263,   1;
: 14 :  2583149,   90209,  1077,   5;
: 15 :  9346594,  343809,  4419,  23;
: 16 : 34023934, 1315499, 18132, 105;

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

Columns k=0-10 give: A243870, A243871, A243872, A243873, A243874, A243875, A243876, A243877, A243878, A243879, A243880.
Row sums give A000108.
T(738,k) = A243752(738,k).
T(n,0) = A243753(n,738).
Cf. A243882.

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, 6, 2, 4, 2, 10, 2][t])+`if`(t=10,
      z, 1)*b(x-1, y-1, [1, 3, 1, 3, 3, 7, 8, 9, 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..20);

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x==0, 1, Expand[b[x-1, y+1, {2, 2, 4, 5, 6, 2, 4, 2, 10, 2}[[t]]] + If[t==10, z, 1]*b[x-1, y-1, {1, 3, 1, 3, 3, 7, 8, 9, 1, 3}[[t]]]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1]]; Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, Mar 31 2015, after Alois P. Heinz *)

A120304 Catalan numbers minus 2.

Original entry on oeis.org

-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

A243820 Number of Dyck paths of semilength n such that all sixteen consecutive step patterns of length 4 occur at least once.

Original entry on oeis.org

38, 587, 4785, 31398, 190050, 1043248, 5324534, 25711105, 119092876, 533680433, 2329450085, 9955122396, 41824314441, 173289259905, 709861015186, 2880803895035, 11601285215222, 46422795985447, 184784743066842, 732324944072523, 2891815190097065, 11385122145001833

Offset: 10

Alois P. Heinz, Jun 11 2014

nonn

			a(10) = 38: 10101100111101000010, 10101101001111000010, 10101111000011010010, 10101111001101000010, 10101111010000110010, 10101111010011000010, 10110011110100001010, 10110011110101000010, 10110100111100001010, 10110101001111000010, 10111100001101001010, 10111100001101010010, 10111100110100001010, 10111100110101000010, 10111101000011001010, 10111101001100001010, 10111101010000110010, 10111101010011000010, 11001011110000110100, 11001011110100001100, 11001101011110000100, 11001101111000010100, 11001111000010110100, 11001111010000101100, 11001111010110000100, 11001111011000010100, 11010010111100001100, 11010011110000101100, 11010110011110000100, 11010111100001001100, 11010111100001100100, 11010111100100001100, 11010111100110000100, 11011001111000010100, 11011110000101001100, 11011110000110010100, 11011110010100001100, 11011110011000010100.  Here 1=Up=(1,1), 0=Down=(1,-1).

Alois P. Heinz, Table of n, a(n) for n = 10..70

Cf. A242257, A243882, A243965, 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-> add(b(2*n-3, l[], {$0..15}), l=[[1, 5], [1, 6], [3, 7]]):
seq(a(n), n=10..20);

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, 8], s  ~Complement~  {2 t + j}], {j, 0, 1}]]]];
a[n_] := Sum[b[2 n - 3, Sequence @@ l, Range[0, 15]], {l, {{1, 5}, {1, 6}, {3, 7}}}];
a /@ Range[10, 31] (* Jean-François Alcover, Apr 28 2020, after Alois P. Heinz *)

A242167 Number of length n binary words that contain 000 and 001 and 010 and 011 and 100 and 101 and 110 and 111 as contiguous subsequences. The 3 letter subsequences are allowed to overlap.

Original entry on oeis.org

16, 80, 298, 934, 2632, 6890, 17118, 40908, 94884, 214956, 477922, 1046544, 2263228, 4843834, 10277132, 21645226, 45303842, 94314954, 195443594, 403391590, 829703588, 1701379556, 3479560910, 7099569872, 14455857024, 29380784736, 59618421994, 120801765892

Offset: 10

Edward Williams and Geoffrey Critzer, May 05 2014

The expected wait time to see all eight 3 bit strings is 89259/3640 (approximately 24.5).

			a(10) = 16 because we have: 0001011100, 0001110100, 0010111000, 0011101000, 0100011101, 0101110001, 0111000101, 0111010001, 1000101110, 1000111010, 1010001110, 1011100010, 1100010111, 1101000111, 1110001011, 1110100011.

Alois P. Heinz, Table of n, a(n) for n = 10..1000
Eric Weisstein's World of Mathematics, Coin Tossing
Index entries for linear recurrences with constant coefficients, signature (10, -41, 89, -114, 99, -58, -30, 120, -121, 109, -97, 20, -20, 37, 33, -17, 20, -66, 9, -9, 21, 21, -3, 0, -11, -2, -1, 1, 2).

Cf. A242206, A242257, A242323, A243882.

(* about 5 minutes of run time required *)
s=Tuples[{T,H},3];
t=Table[Total[Table[Total[z^Flatten[Position[Table[Take[s[[n]], 3-i]===Drop[s[[m]],i],{i,0,2}], True]-1]],{m,1,8}]*{a,b,c,d,e,f,g,h}],{n,1,8}];
sol=Solve[{a==va(z^3+t[[1]]-a),b==vb(z^3+t[[2]]-b),c==vc(z^3+t[[3]]-c), d==vd(z^3+t[[4]]-d),e==ve(z^3+t[[5]]-e), f==vf(z^3+t[[6]]-f),g==vg(z^3+t[[7]]-g),h==vh(z^3+t[[8]]-h)},{a,b,c,d,e,f,g,h}];
S=1/(1-2z-a-b-c-d-e-f-g-h);
vsub={va->ua-1,vb->ub-1,vc->uc-1,vd->ud-1,ve->ue-1,vf->uf-1,vg->ug-1,vh->uh-1};
Fz[ua_,ub_,uc_,ud_,ue_,uf_,ug_,uh_]=Simplify[S/.sol/.vsub];
tn=Table[Total[Map[Apply[Fz,#]&,Select[Tuples[{0,1},8],Count[#,0]==n&]]],{n,1,8}];
Drop[Flatten[CoefficientList[Series[1/(1-2z)-Simplify[tn[[1]] -tn[[2]] +tn[[3]]-tn[[4]]+tn[[5]]-tn[[6]]+tn[[7]]-tn[[8]]],{z,0,40}],z]],10]

G.f.: -2*x^10 *(2*x^23 +5*x^22 +9*x^21 +12*x^20 +14*x^19 -13*x^17 -19*x^16 -41*x^15 -6*x^14 -18*x^13 +33*x^12 +32*x^11 -6*x^10 +91*x^9 -111*x^8 +32*x^7 -8*x^6 -61*x^5 +107*x^4 -95*x^3 +77*x^2 -40*x +8) / ((2*x-1) *(x+1) *(x^2+1) *(x^2+x-1) *(x^3-x^2+2*x-1) *(x^3+x^2-1) *(x^3+x^2+x-1) *(x^4+x-1) *(x^4+x^3-1) *(x^3+x-1) *(x-1)^3). - Alois P. Heinz, May 07 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A120304 Catalan numbers minus 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

MuPAD

PARI

Formula

A243820 Number of Dyck paths of semilength n such that all sixteen consecutive step patterns of length 4 occur at least once.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A242167 Number of length n binary words that contain 000 and 001 and 010 and 011 and 100 and 101 and 110 and 111 as contiguous subsequences. The 3 letter subsequences are allowed to overlap.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula