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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A080934 Square array read by antidiagonals of number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2n steps with all values less than or equal to k. 11
1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 4, 1, 0, 1, 1, 2, 5, 8, 1, 0, 1, 1, 2, 5, 13, 16, 1, 0, 1, 1, 2, 5, 14, 34, 32, 1, 0, 1, 1, 2, 5, 14, 41, 89, 64, 1, 0, 1, 1, 2, 5, 14, 42, 122, 233, 128, 1, 0, 1, 1, 2, 5, 14, 42, 131, 365, 610, 256, 1, 0, 1, 1, 2, 5, 14, 42, 132, 417, 1094 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,13

COMMENTS

Number of permutations in S_n avoiding both 132 and 123...k.

T(n,k) = number of rooted ordered trees on n nodes of depth <= k. Also, T(n,k) = number of {1,-1} sequences of length 2n summing to 0 with all partial sums are >=0 and <= k. Also, T(n,k) = number of closed walks of length 2n on a path of k nodes starting from (and ending at) a node of degree 1. - Mitch Harris, Mar 06 2004

Also T(n,k) = k-th coefficient in expansion of the rational function R(n), where R(1) = 1, R(n+1) = 1/(1-x*R(n)), which means also that lim(n->inf,R(n)) = g.f. of Catalan numbers (A000108) wherever it has real value (see Mansour article). - Clark Kimberling and Ralf Stephan, May 26 2004

LINKS

Alois P. Heinz, Antidiagonals n = 0..140, flattened

N. G. de Bruijn, D. E. Knuth, S. O. Rice, The Average Height of Planted Plane Trees, Graph Theory and Computing, (1972) 15-22.

Aleksandar Ilic and Andreja Ilic, On the number of restricted Dyck paths, Filomat 25:3 (2011), 191-201; DOI: 10.2298/FIL1103191I.

Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243v1 [math.CO], 2012 (page 10, Corollary 3).

T. Mansour, [math/0302014] Restricted even permutations and Chebyshev polynomials

T. Mansour and A. Vainshtein, Restricted permutations, continued fractions and Chebyshev polynomials

C. Krattenthaler, Permutations with restricted patterns and Dyck paths

FORMULA

T(n, k) = sum_i{0<i<k)T(i, k)*T(n-i, k-1) with T(0, k) = 1 and T(n, 0) = 0^n. For 1<=k<=n T(n, k) = A080935(n, k) = T(n, k-1)+A080936(n, k); for k>=n T(n, k) = A000108(n).

T(n, k)=2^(2n+1)/(k+2)*Sum{i=1, k+1, [sin(pi*i/(k+2))*cos(pi*i/ (k+2))^n]^2} for n>=1 - Herbert Kociemba, Apr 28 2004

G.f. of n-th row: B(n)/B(n+1) where B(j)=[(1+sqrt(1-4x))/2]^j-[(1-sqrt(1-4x))/2]^j.

EXAMPLE

T(3,2) = 4 since the paths of length 2*3 (7 points) with all values less than or equal to 2 can take the routes 0101010, 0101210, 0121010 or 0121210, but not 0123210.

From Peter Luschny, Aug 27 2014: (Start)

Trees with n nodes and height <= h:

h\n  1  2  3  4   5   6    7    8     9    10     11

---------------------------------------------------------

[ 1] 1, 0, 0, 0,  0,  0,   0,   0,    0,    0,     0, ...  A063524

[ 2] 1, 1, 1, 1,  1,  1,   1,   1,    1,    1,     1, ...  A000012

[ 3] 1, 1, 2, 4,  8, 16,  32,  64,  128,  256,   512, ...  A011782

[ 4] 1, 1, 2, 5, 13, 34,  89, 233,  610, 1597,  4181, ...  A001519

[ 5] 1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281,  9842, ...  A124302

[ 6] 1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, ...  A080937

[ 7] 1, 1, 2, 5, 14, 42, 132, 428, 1416, 4744, 16016, ...  A024175

[ 8] 1, 1, 2, 5, 14, 42, 132, 429, 1429, 4846, 16645, ...  A080938

[ 9] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16778, ...  A033191

[10] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, ...  A211216

---------------------------------------------------------

The generating functions are listed in A211216. Note that the values up to the main diagonal are the Catalan numbers A000108.

(End)

MAPLE

# As a triangular array:

b:= proc(x, y, k) option remember; `if`(y>min(k, x) or y<0, 0,

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

    end:

A:= (n, k)-> b(2*n, 0, k):

seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Aug 06 2012

# As a square array:

A := proc(n, k) option remember; local j; if n = 1 then 1 elif k = 1 then 0 else add(A(n-j, k)*A(j, k-1), j=1..n-1) fi end:

linalg[matrix](10, 12, (n, k) -> A(k, n)); # Peter Luschny, Aug 27 2014

CROSSREFS

Cf. A000108, A079214, A080935, A080936. Rows include A000012, A057427, A040000 (offset), columns include (essentially) A000007, A000012, A011782, A001519, A007051, A080937, A024175, A080938, A033191, A211216. Main diagonal is A000108.

Cf. A094718 (involutions).

Sequence in context: A238093 A238095 A240608 * A214015 A137560 A201093

Adjacent sequences:  A080931 A080932 A080933 * A080935 A080936 A080937

KEYWORD

nonn,tabl

AUTHOR

Henry Bottomley, Feb 25 2003

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 20 21:27 EDT 2014. Contains 248371 sequences.