%I A080934
%S A080934 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,
%T A080934 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,
%U A080934 128,1,0,1,1,2,5,14,42,131,365,610,256,1,0,1,1,2,5,14,42,132,417,1094
%N 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.
%C A080934 Number of permutations in S_n avoiding both 132 and 123...k.
%C A080934 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
%C A080934 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
%H A080934 T. Mansour, <a href="http://arXiv.org/abs/math.CO/0302014">[math/0302014] 
               Restricted even permutations and Chebyshev polynomials</a>
%H A080934 T. Mansour and A. Vainshtein, <a href="http://arXiv.org/abs/math.CO/9912052">
               Restricted permutations, continued fractions and Chebyshev polynomials</
               a>
%H A080934 C. Krattenthaler, <a href="http://arXiv.org/abs/math.CO/0002200">Permutations 
               with restricted patterns and Dyck paths</a>
%F A080934 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).
%F A080934 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
%F A080934 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.
%e A080934 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.
%Y A080934 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.
%Y A080934 Cf. A094718 (involutions).
%Y A080934 Sequence in context: A143841 A035440 A029878 this_sequence A137560 A131255 
               A133607
%Y A080934 Adjacent sequences: A080931 A080932 A080933 this_sequence A080935 A080936 
               A080937
%K A080934 nonn,tabl
%O A080934 0,13
%A A080934 Henry Bottomley (se16(AT)btinternet.com), Feb 25 2003