|
Search: id:A080934
|
|
|
| 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. |
|
+0
10
|
|
| 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; listen)
|
|
|
OFFSET
|
0,13
|
|
|
COMMENT
|
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
|
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 (kociemba(AT)t-online.de), 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
|
Rows start 1,1,1,1,1,1,...; 0,1,1,1,1,1,...; 0,1,2,2,2,2,...; 0,1,4,5,5,5,...; 0,1,8,13,14,14,...; 0,1,16,34,41,42,...; etc. 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.
|
|
CROSSREFS
|
Cf. A000108, A079214, A080935, A080936. Rows include A000012, A057427, A040000 (offset), columns include (essentially) A000007, A000012, A011782, A001519, A007051, A080937, A024175, A080938, A033191. Main diagonal is A000108.
Cf. A094718 (involutions).
Sequence in context: A143841 A035440 A029878 this_sequence A137560 A131255 A133607
Adjacent sequences: A080931 A080932 A080933 this_sequence A080935 A080936 A080937
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Henry Bottomley (se16(AT)btinternet.com), Feb 25 2003
|
|
|
Search completed in 0.005 seconds
|
