login
This site is supported by donations to The OEIS Foundation.

 

Logo

The October issue of the Notices of the Amer. Math. Soc. has an article about the OEIS.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A091869 Triangle read by rows: T(n,k)=number of Dyck paths of semilength n having k peaks at even height. 6
1, 1, 1, 2, 2, 1, 4, 6, 3, 1, 9, 16, 12, 4, 1, 21, 45, 40, 20, 5, 1, 51, 126, 135, 80, 30, 6, 1, 127, 357, 441, 315, 140, 42, 7, 1, 323, 1016, 1428, 1176, 630, 224, 56, 8, 1, 835, 2907, 4572, 4284, 2646, 1134, 336, 72, 9, 1, 2188, 8350, 14535, 15240, 10710, 5292, 1890, 480, 90, 10, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

Number of ordered trees with n edges having k leaves at even height. Row sums are the Catalan numbers (A000108). T(n,0)=A001006(n-1) (the Motzkin numbers). sum(k*T(n,k),k=0..n-1) = binom(2n-2,n-2)=A001791(n-1). Mirror image of A091187.

T(n,k)= number of Dyck paths of semilength n and having k dud's (here u=(1,1) and d=(1,-1)). Example: T(4,2)=3 because we have uud(du[d)ud], uu(dud)(dud) and uu(du[d)ud]d (the dud's are shown between parentheses).

T(n,k)= number of Dyck paths of semilength n and containing exactly k double rises whose matching down steps form a doublefall. Example: UUUDUDDD has 2 double rises but only the first has matching Ds - the path's last 2 steps - forming a doublefall. (Travel horizontally east from an up step to encounter its matching down step.) - David Callan, Jul 15 2004

T(n,k)=number of ordered trees on n edges containing k edges of outdegree 1. (The outdegree of an edge is the outdegree of its child vertex. Thus edges of outdegree 1 correspond to non-root vertices of outdegree 1.) T(3,2)=2 because

/\.../\.

|.....|.

each have one edge of outdegree 1. - David Callan, Oct 25 2004

Exponential Riordan array [exp(x)*Bessel_I(1,2x)/x, x]. - Paul Barry, Mar 09 2010

REFERENCES

JL Baril, S Kirgizov, The pure descent statistic on permutations, Preprint, 2016, http://jl.baril.u-bourgogne.fr/Stirling.pdf. See Table 2.

LINKS

Alois P. Heinz, Rows n = 1..200, flattened

David Callan, Bijections for Dyck paths with all peak heights of the same parity, arXiv:1702.06150 [math.CO], 2017.

M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Yidong Sun, The statistic "number of udu's" in Dyck paths, Discrete Math., 287 (2004), 177-186.

Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords.

FORMULA

T(n, k)=binomial(n-1, k)*sum(binomial(n-k, j)*binomial(n-k-j, j-1), j=0..ceil((n-k)/2))/(n-k) for 0<=k<n; T(n, k)=0 for k>=n. G.f.=G=G(t, z) satisfies zG^2-(1+z-tz)G+1+z-tz=0. T(n, k)=M(n-k-1)*binomial(n-1, k), where M(n)=A001006(n) are the Motzkin numbers.

T(n+1, k+1)=n*T(n, k)/(k+1). - David Callan, Dec 09 2004

G.f.: 1/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-... (continued fraction). - Paul Barry, Aug 03 2009

E.g.f.: exp(x+xy)*Bessel_I(1,2x)/x. - Paul Barry, Mar 10 2010

EXAMPLE

T(4,1)=6 because we have u(ud)dudud, udu(ud)dud, ududu(ud)d, uuudd(ud)d, u(ud)uuddd and uuu(ud)ddd (here u=(1,1), d=(1,-1) and the peaks at even height are shown between parentheses).

Triangle begins:

[1],

[1, 1],

[2, 2, 1],

[4, 6, 3, 1],

[9, 16, 12, 4, 1],

[21, 45, 40, 20, 5, 1],

[51, 126, 135, 80, 30, 6, 1],

MAPLE

T := proc(n, k) if k<n then binomial(n-1, k)*sum(binomial(n-k, j)*binomial(n-k-j, j-1), j=0..ceil((n-k)/2))/(n-k) else 0 fi end: seq(seq(T(n, k), k=0..n-1), n=1..11);

# second Maple program:

b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,

      `if`(y>0, b(x-1, y-1, 0)*z^irem(t*y+t, 2), 0)+

      `if`(y<x-1, b(x-1, y+1, 1), 0)))

    end:

T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):

seq(T(n), n=1..16);  # Alois P. Heinz, May 12 2017

MATHEMATICA

(* m = MotzkinNumber *) m[0] = 1; m[n_] := m[n] = m[n - 1] + Sum[m[k]*m[n - 2 - k], {k, 0, n - 2}]; t[n_, n_] = 1; t[n_, k_] := m[n - k]*Binomial[n - 1, k - 1]; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-Fran├žois Alcover, Jul 10 2013 *)

CROSSREFS

Cf. A000108, A001006, A001791, A091187, A243752.

Sequence in context: A068957 A119468 A175136 * A112307 A228336 A111062

Adjacent sequences:  A091866 A091867 A091868 * A091870 A091871 A091872

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Mar 10 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 25 11:05 EDT 2018. Contains 315389 sequences. (Running on oeis4.)