|
| |
|
|
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.
|
|
12
|
|
|
|
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, 1597, 512, 1, 0
(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
Row n of the array gives Taylor series expansion of F_n(t)/F_{n+1}(t), where F_n(t) are the Fibonacci polynomials defined in A259475 [Kreweras, 1970]. - N. J. A. Sloane, Jul 03 2015
|
|
|
LINKS
|
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41. See page 38.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
|
|
|
FORMULA
|
T(n, k) = Sum_{0<i<n} 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.
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):
# 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
|
|
|
MATHEMATICA
|
A[n_, k_] := A[n, k] = Which[n == 1, 1, k == 1, 0, True, Sum[A[n-j, k]*A[j, k-1], {j, 1, n-1}]]; Table[A[k-n+1, n], {k, 1, 13}, {n, k, 1, -1}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Peter Luschny *)
|
|
|
PROG
|
(PARI)
A(N, K) = {
my(m = matrix(N, K, n, k, n==1));
for (n = 2, N,
for (k = 2, K,
m[n, k] = sum(i = 1, n-1, m[n-i, k] * m[i, k-1])));
return(m);
}
|
|
|
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.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
