Search: id:A009766
Results 1-1 of 1 results found.
%I A009766
%S A009766 1,1,1,1,2,2,1,3,5,5,1,4,9,14,14,1,5,14,28,42,42,1,6,20,48,90,132,132,
1,
%T A009766 7,27,75,165,297,429,429,1,8,35,110,275,572,1001,1430,1430,1,9,44,154,
%U A009766 429,1001,2002,3432,4862,4862,1,10,54,208,637,1638,3640,7072,11934
%N A009766 Catalan's triangle T(n,k) (read by rows): each term is the sum of the
entries above and to the left, i.e. T(n,k)=sum(T(n-1,j),j=0..k).
%C A009766 There are several versions of a Catalan triangle: see A009766, A008315,
A028364, A033184, A053121, A059365, A062103.
%C A009766 T(n,k) = number of standard tableaux of shape (n,k) (n>0, 0< = k< = n).
Example: T(3,1) = 3 because we have 134/2, 124/3 and 123/4. - Emeric
Deutsch (deutsch(AT)duke.poly.edu), May 18 2004
%C A009766 T(n,k) is the number of full binary trees with n+1 internal nodes and
jump-length k. In the preorder traversal of a full binary tree, any
transition from a node at a deeper level to a node on a strictly
higher level is called a jump; the positive difference of the levels
is called the jump distance; the sum of the jump distances in a given
ordered tree is called the jump-length. - Emeric Deutsch (deutsch(AT)duke.poly.edu),
Jan 18 2007
%C A009766 Comment from Anthony C Robin, Jul 12 2007: The k-th diagonal from the
right (k=1, 2, ...) gives the sequence obtained by asking in how
many ways can we toss a fair coin until we first get k more heads
than tails. The k-th diagonal has formula k(2m+k-1)!/(m!(m+k)!) and
g.f. (C(x))^k where C(x) is the generating function for the Catalan
numbers, (1-sq_root(1-4x))/(2x).
%C A009766 T(n,k) is also the number of order-decreasing and order-preserving full
transformations (of an n-element chain) of waist k (waist (alpha)
= max(Im(alpha))). [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]
%D A009766 E. Barcucci and Verri, Discrete Math., 102 (1992), 229-237.
%D A009766 F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204
(1999) 73-112.
%D A009766 M. Bousquet-Melou and M. Petkovsek, Linear recurrences with constant
coefficients: the multivariate case, Discrete Math., 225 (2000),
51-75.
%D A009766 E. H. M. Brietzke, An identity of Andrews ..., Discrete Math., 308 (2008),
4246-4262.
%D A009766 S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem
for succession rules, Discr. Math., 298 (2005), 142-154.
%D A009766 B. Derrida, E. Domany and D. Mukamel, An exact solution of a one-dimensional
asymmetric exclusion model with open boundaries, J. Stat. Phys. 69,
1992, 667-687; eqs. (20), (21), p. 672. (Y_{N}(K) = A009766(N+1,K-1),
1 <= K <= N+1, N >=0 if alpha = 1 = beta).
%D A009766 E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math.,
241 (2001), 241-265.
%D A009766 H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45,
1961, 199-201.
%D A009766 W. Krandick, Trees and jumps and real roots, J. Computational and Applied
Math., 162, 2004, 51-55.
%D A009766 D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6, Eq. 22.
%D A009766 G. Kreweras, Sur les e'ventails de segments, {\em Cahiers du Bureau Universitaire
de Recherche Op\'{e}rationnelle}, Institut de Statistique, Universit\'{e}
de Paris, #15 (1970), 3-41.
%D A009766 D. Merlini et al., Underdiagonal lattice paths with unrestricted steps,
Discrete Appl. Math., 91 (1999), 197-213.
%D A009766 D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J.
Combin. Theory, A 99 (2002), 307-344 (Table I).
%D A009766 L. W. Shapiro, A Catalan triangle, Discrete Math., 14, 83-90, 1976.
%D A009766 Laradji, A. and Umar, A. On certain finite semigroups of order-decreasing
transformations I, Semigroup Forum 69 (2004), 184-200 [From A. Umar
(aumarh(AT)squ.edu.om), Aug 25 2008]
%D A009766 Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906v1,
Discrete Math., 308 (2008), 4660-4669.
%D A009766 Dominique Foata and Guo-Niu Han, Dimers and new q-tangent numbers, Preprint,
2008.
%D A009766 Dominique Foata and Guo-Niu Han, The dimer polynomial triangle, Preprint,
2008.
%H A009766 T. D. Noe, Rows n=0..100 of triangle, flattened
%H A009766 J. L. Arregui, Tangent
and Bernoulli numbers related to Motzkin and Catalan numbers
by means of numerical triangles.
%H A009766 M. Bousquet-M\'{e}lou, Linear recurrences with constant coefficients:
the multivariate case
%H A009766 Ira Gessel, Super ballot numbers.
%H A009766 F. Hivert, J.-C. Novelli and J.-Y. Thibon, The Algebra of Binary Search Trees, Theoretical
Computer Science, 339 (2005), 129-165.
%H A009766 A. Karttunen,
Some notes on Catalan's Triangle
%H A009766 D. Merlini et al.,
Underdiagonal lattice paths with unrestricted steps, Discrete
Appl. Math., 91 (1999), 197-213.
%H A009766 J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion
%H A009766 R. Parviainen, Permutations,
cycles and the pattern 2-13
%H A009766 A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations.
%H A009766 T. Sillke, Catalan's numbers
%H A009766 R. A. Sulanke,
Guessing, ballot numbers and refining Pascal's triangle
%H A009766 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
%H A009766 Eric Weisstein's World of Mathematics, Nonnegative Partial Sum
%F A009766 a(n, m)= binomial(n+m, n)*(n-m+1)/(n+1), n >= m >= 0.
%F A009766 G.f. for column m: (x^m)*N(2; m-1, x)/(1-x)^(m+1), m >= 0, with the row
polynomials from triangle A062991 and N(2; -1, x) := 1.
%F A009766 G.f.=C(tx)/[1-xC(tx)]=1+(1+t)x+(1+2t+2t^2)x^2+..., where C(x)=[1-sqrt(1-4x)]/
(2x) is the Catalan function. - Emeric Deutsch (deutsch(AT)duke.poly.edu),
May 18 2004
%F A009766 Another version of triangle T(n, k) given by [1, 0, 0, 0, 0, 0, ...]
DELTA [0, 1, 1, 1, 1, 1, 1, ...] = 1; 1, 0; 1, 1, 0; 1, 2, 2, 0;
1, 3, 5, 5, 0; 1, 4, 9, 14, 14, 0; ...where DELTA is the operator
defined in A084938. - Philippe Deleham (kolotoko(AT)wanadoo.fr) Feb
16 2005
%F A009766 T(n,k) = C(n+k-2,n-1)*(n-k+1)/n [From A. Umar (aumarh(AT)squ.edu.om),
Aug 25 2008]
%e A009766 Triangle begins:
%e A009766 1
%e A009766 1,1
%e A009766 1,2,2
%e A009766 1,3,5,5
%e A009766 1,4,9,14,14
%e A009766 1,5,14,28,42,42
%e A009766 1,6,20,48,90,132,132
%e A009766 1,7,27,75,165,297,429,429
%e A009766 1,8,35,110,275,572,1001,1430,1430
%e A009766 1,9,44,154,429,1001,2002,3432,4862,4862
%p A009766 for n from 1 to 12 do seq((n-m)/(m+n)* binomial(m+n,m), m = 0 .. n-1)
od; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 09 2007
%o A009766 (PARI) {T(n, k)= if(k<0|k>n, 0, binomial(n+1+k, k)* (n+1-k)/(n+1+k) )}
/* Michael Somos Oct 17 2006 */
%Y A009766 Cf. A008315, A028364, A059365, A062103, A062745. Diagonals give A000108,
A000245, A002057.
%Y A009766 Sums of the shallow diagonals give A001405, central binomial coefficients:
1=1, 1=1, 1+1=2, 1+2=3, 1+3+2=6, 1+4+5=10, 1+5+9+5=20, ...
%Y A009766 Row sums as well as the sums of the squares of the shallow diagonals
give Catalan numbers (A000108).
%Y A009766 Reflected version of A033184.
%Y A009766 The following are all versions of (essentially) the same Catalan triangle:
A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
%Y A009766 Diagonals give A000108 A000245 A002057 A000344 A003517 A000588 A003518
A003519 A001392, ...
%Y A009766 Sequence in context: A139687 A064581 A064580 this_sequence A059718 A076038
A095788
%Y A009766 Adjacent sequences: A009763 A009764 A009765 this_sequence A009767 A009768
A009769
%K A009766 nonn,tabl,nice
%O A009766 0,5
%A A009766 Wouter L. J. Meeussen (wouter.meeussen(AT)pandora.be).
Search completed in 0.002 seconds