A097692 Triangle read by rows: a(n,k) = number of paths of n upsteps U and n downsteps D that contain k UDUs.

1, 2, 4, 2, 10, 8, 2, 26, 30, 12, 2, 70, 104, 60, 16, 2, 192, 350, 260, 100, 20, 2, 534, 1152, 1050, 520, 150, 24, 2, 1500, 3738, 4032, 2450, 910, 210, 28, 2, 4246, 12000, 14952, 10752, 4900, 1456, 280, 32, 2, 12092, 38214, 54000, 44856, 24192, 8820, 2184, 360, 36, 2

Offset

0,2

Comments

See A091869 for the distribution of the parameter "number of UDUs" on Dyck paths.

References

Aristidis Sapounakis, Panagiotis Tsikouras, Ioannis Tasoulas, Kostas Manes, Strings of Length 3 in Grand-Dyck Paths and the Chung-Feller Property, Electr. J. Combinatorics, 19 (2012), #P2. - From N. J. A. Sloane, Feb 06 2013

Links

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

Formula

G.f.: ((1 + x - x*y)/(1 - 3*x - x*y))^(1/2) = Sum_{n>=0, k>=0} a(n,k) x^n y^k.

Example

Table begins
\ k 0, 1, 2, ...
n
0 | 1
1 | 2
2 | 4, 2
3 | 10, 8, 2
4 | 26, 30, 12, 2
5 | 70, 104, 60, 16, 2
6 |192, 350, 260, 100, 20, 2
7 |534, 1152, 1050, 520, 150, 24, 2
The path UDUDUD contains 2 UDUs and a(2,1) = 2 because each of UDUD, DUDU contains one UDU.

Maple

b:= proc(u, d, t) option remember; `if`(u=0 and d=0, 1,
      expand(`if`(u=0, 0, b(u-1, d, 2)*`if`(t=3, x, 1))
      +`if`(d=0, 0, b(u, d-1, `if`(t=2, 3, 1)))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2, 1)):
seq(T(n), n=0..12);  # Alois P. Heinz, Apr 29 2015

Mathematica

gfForBalancedByNumberUDU=Sqrt[(1 + x - x*y)/(1 - 3*x - x*y)]; Map[CoefficientList[ #, y]&, CoefficientList[Normal[Series[gfForBalancedByNumberUDU, {x, 0, 8}, {y, 0, 8}]], x]]

Crossrefs

Column k=0 is A025565. The row sums are the (even) central binomial coefficients A000984.

Cf. A171651.

Sequence in context: A236959 A366032 A097577 * A118920 A305260 A162982

Adjacent sequences: A097689 A097690 A097691 * A097693 A097694 A097695

Keyword

nonn,tabf

Author

David Callan, Aug 19 2004; corrected Jun 10 2005

Extensions

Keyword tabl changed to tabf by Michel Marcus, Apr 07 2013

Status

approved