A114486 -id:A114486 - cp's OEIS frontend

A114487 Number of Dyck paths of semilength n having no UUDD's starting at level 0.

1, 1, 1, 3, 10, 31, 98, 321, 1078, 3686, 12789, 44919, 159407, 570704, 2058817, 7476621, 27310345, 100275628, 369886451, 1370066394, 5093778398, 19002602171, 71109895075, 266855940177, 1004045604976, 3786790901401, 14313706230574, 54215799080454

Offset: 0

Emeric Deutsch, Nov 30 2005

nonn

			a(3) = 3 because we have UDUDUD, UUDUDD and UUUDDD, where U=(1,1), D=(1,-1).

G. C. Greubel, Table of n, a(n) for n = 0..1000
J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
G. Benkart and T. Halverson, Motzkin Algebras, Eur. J. Comb. 36 (2014) 473-502
Dennis E. Davenport, Louis W. Shapiro, and Leon C. Woodson, A bijection between the triangulations of convex polygons and ordered trees, Integers (2020) Vol. 20, Article #A8.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Column 0 of A114486.

G:=2/(1+2*z^2+sqrt(1-4*z)): Gser:=series(G,z=0,33): 1,seq(coeff(Gser,z^n),n=1..30);

CoefficientList[Series[2/(1+2*x^2+Sqrt[1-4*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)

x='x+O('x^50); Vec(2/(1+2*x^2+sqrt(1-4*x))) \\ G. C. Greubel, Mar 17 2017

G.f.: 2/(1+2*z^2+sqrt(1-4*z)).
a(n) ~ 4^(n+3) / (81*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014
a(n) = Sum_{k=0..n/2} (-1)^k*(k+1)/(2*n-3*k+1)*binomial(2*n-3*k+1, n-2*k). - Ira M. Gessel, Jun 16 2018
D-finite with recurrence (n+1)*a(n) +3*(-n+1)*a(n-1) +2*(-2*n+1)*a(n-2) +(n+1)*a(n-3) +2*(-2*n+1)*a(n-4)=0. - R. J. Mathar, Nov 13 2020

A346538 Table read by antidiagonals: T(n,k) is the number of paths in the Z X Z grid joining (0,0) and (n,k) each of whose steps increases the Euclidean distance to the origin and has coordinates with absolute value at most 1.

Original entry on oeis.org

1, 1, 1, 7, 3, 7, 29, 11, 11, 29, 173, 72, 25, 72, 173, 937, 382, 108, 108, 382, 937, 5527, 2295, 803, 241, 803, 2295, 5527, 32309, 13391, 4632, 1152, 1152, 4632, 13391, 32309, 193663, 80677, 29450, 9132, 2545, 9132, 29450, 80677, 193663

Offset: 0

José María Grau Ribas, Jul 23 2021

			Array begins:
     1,     1,     7,    29,    173,    937,   5527, ...
     1,     3,    11,    72,    382,   2295,  13391, ...
     7,    11,    25,   108,    803,   4632,  29450, ...
    29,    72,   108,   241,   1152,   9132,  56043, ...
   173,   382,   803,  1152,   2545,  12829, 106207, ...
   937,  2295,  4632,  9132,  12829,  28203, 147239, ...
  5527, 13391, 29450, 56043, 106207, 147239, 322681, ...
  ...
T(6,4) = T(5,3) + T(5,4) + T(5,5) + T(6,3) = 9132 + 12829 + 28203 + 56043 =106207.
T(7,5) = T(6,4) + T(6,5) + T(6,6) + T(7,4).
T(7,6) = T(6,6) + T(7,5) + T(6,5).
T(0,5) = T(-1,4) + T(0,4) + T(1,4).

Main diagonal gives A346539.
Column (or row) k=0 gives A347814.
Cf. A008288, A001850, A001263, A006318, A001006, A114486.

T:= proc(n, k) option remember; `if`([n, k]=[0$2], 1, add(add(
     `if`(i^2+j^2Alois P. Heinz, Sep 08 2021

rodean[{m_, n_}] := Select[ Complement[ Flatten[Table[{m, n} + {s, t}, {s, -1, 1}, {t, -1, 1}], 1] // Union, {{m, n}}], #[[1]]^2 + #[[2]]^2 < m^2 + n^2 &];
$RecursionLimit = 10^6; Clear[T]; T[{0, 0}] = 1;
T[{m_, n_}] := T[{m, n}] = Sum[T[rodean[{m, n}][[i]]],{i,Length[rodean[{m,n}]]}] ;
Table[T[{k, n - k}], {n, 0, 12}, {k, 0, n}] // Flatten
(* Second program: *)
T[n_, k_] := T[n, k] = If[{n, k} == {0, 0}, 1, Sum[Sum[If[i^2 + j^2 < n^2 + k^2, T[i, j], 0], {j, k - 1, k + 1}], {i, n - 1, n + 1}]];
Table[Table[T[n, d - n], {n, 0, d}], {d, 0, 8}] // Flatten (* Jean-François Alcover, Nov 03 2021, after Alois P. Heinz *)

T(n,k) = T(k,n).

cp's OEIS Frontend

A114487 Number of Dyck paths of semilength n having no UUDD's starting at level 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula