|
%I #27 Aug 20 2018 16:19:58
%S 1,1,1,2,4,6,10,19,32,54,98,170,292,520,909,1577,2787,4883,8515,14998,
%T 26299,45984,80863,141844,248381,436406,765649,1341844,2356500,
%U 4134749,7249981,12728630,22335110,39174776,68766785,120670190,211689586,371558266,652014636
%N Number of equivalence classes of Dyck paths of semilength n for the consecutive pattern UDUDD, where U=(1,1) and D=(1,-1).
%C Two Dyck paths of the same length are equivalent with respect to a given pattern if they have equal sets of occurrences of this pattern.
%H Alois P. Heinz, <a href="/A317639/b317639.txt">Table of n, a(n) for n = 0..4096</a>
%H J.-L. Baril, A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/equivdyck.pdf">Equivalence classes of Dyck paths modulo some statistics</a>, 2014.
%H J.-L. Baril, A. Petrossian, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Baril/baril3.html">Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two</a>, J. Int. Seq. 18 (2015) 15.7.1
%H K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, <a href="http://arxiv.org/abs/1510.01952">Equivalence classes of ballot paths modulo strings of length 2 and 3</a>, arXiv:1510.01952 [math.CO], 2015.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>
%p b:= proc(x, y) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
%p `if`(y=0, b(x-2, y)+b(x-6, y+2), b(x-1, y-1))+b(x-5, y+1)))
%p end:
%p a:= n-> b(2*n, 0):
%p seq(a(n), n=0..42);
%t b[x_, y_] := b[x, y] = If[y < 0 || y > x, 0, If[x == 0, 1, If[y == 0, b[x - 2, y] + b[x - 6, y + 2], b[x - 1, y - 1]] + b[x - 5, y + 1]]];
%t a[n_] := b[2n, 0];
%t Table[a[n], {n, 0, 42}] (* _Jean-François Alcover_, Aug 20 2018, from Maple *)
%Y Cf. A000108, A001519, A177528, A244885, A244886, A274114, A274115, A274289.
%K nonn
%O 0,4
%A _Alois P. Heinz_, Aug 02 2018
|
