[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Numeros de Catalan (era Problemas em Aberto II)
On Thu, Feb 27, 2003 at 03:04:44PM -0300, Cláudio (Prática) wrote:
> 15.
>
> _ _ _ _ _ _ _ 1 2 ... n _
> _|_| |_|_| |_|_|_|_|_|_|_
> B \_\ /_/ A
> \_|_/
> |_|
> |_|
> |_| C
> |o|
>
> Imagine que o 'desenho' acima é uma linha férrea,
> aonde o segmento B é extensão do segmento A e o
> segmento C se conecta com ambos segmentos.
> Os numeros no segmento A representam n vagões
> _soltos_ e enumerados.
> Os vagoes podem se mover de A -> B, A -> C e C -> B,
> mas nunca de C -> A nem B -> A nem B -> C..
>
> De quantas formas eh possivel reagrupar os vagões no
> segmento B?
>
> (há espaço suficiente para n vagões tanto em A,
> quanto em B e em C)
Estes são os merecidamente famosos números de Catalan,
veja o que a excelente Encyclopaedia of Integer Sequences
(de N.J. A. Sloane) tem a dizer sobre eles.
Prestem atenção ao número de referências;
os links podem ser seguidos indo para
http://www.research.att.com/~njas/sequences/
e procurando por
1,1,2,5,14,42,132,429,1430,4862,16796,58786
[]s, N.
=============================================================================
ID Number: A000108 (Formerly M1459 and N0577)
Sequence: 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,
2674440,9694845,35357670,129644790,477638700,1767263190,
6564120420,24466267020,91482563640,343059613650,
1289904147324
Name: Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).
Also called Segner numbers.
Comments: Schroeder's first problem. A very large number of combinatorial
interpretations are known - see references, esp. Stanley Volume 2.
Ways to insert n pairs of parentheses in a word of n+1 letters. E.g. for
n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d),
(a((bc)d)), (a(b(cd)).
Shifts one place left when convolved with itself.
For n >= 1 a(n) is also the number of rooted bicolored unicelluar maps
of genus 0 on n edges. - Ahmed Fares (ahmedfares@my-deja.com), Aug 15
2001
Inverse Euler transform of sequence is A022553.
References R. Alter, Some remarks and results on Catalan numbers, pp. 109-132 in
Proceedings of the Louisiana Conference on Combinatorics, Graph
Theory and Computer Science. Vol. 2, edited R. C. Mullin et al., 1971.
E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations
avoiding an increasing number of length-increasing forbidden
subsequences, Discrete Mathematics and Theoretical Computer
Science 4, 2000, 31-44.
F. R. Bernhart, Catalan, Motzkin, and Riordan numbers, Discr. Math.,
204 (1999) 73-112.
W. G. Brown, Historical note on a recurrent combinatorial problem,
Amer. Math. Monthly, 72 (1965), 973-977.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 53.
E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math.,
241 (2001), 241-265.
D. Foata and D. Zeilberger, A classic proof of a recurrence for a very
classical sequence, J Comb Thy A 80 380-384 1997.
H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45,
1961, 199-201.
J. R. Gaggins, Constructing the Centroid of a Polygon, Math. Gaz., 61
(1988), 211-212.
M. Gardner, Time Travel and Other Mathematical Bewilderments, Chap.
20 pp 253-266 W. H. Freeman NY 1988.
H. W. Gould, Research bibliography of two special number sequences,
Mathematica Monongaliae, Vol. 12, 1971.
Alain Goupil and Gilles Schaeffer, Factoring N-Cycles and Counting
Maps of Given Genus . Europ. J. Combinatorics (1998) 19 819-834.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY,
1973, p. 67, (3.3.23).
B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol.
1, p. 513, Eq. (7.282).
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J.
Combin. Theory, A99 (2002), 307-344.
A. Panholzer and H. Prodinger, Bijections for ternary trees and
non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4).
R. Read, "Counting Binary Trees" in 'The Mathematical Gardner', D. A.
Klarner Ed. pp 331-334, Wadsworth CA 1989.
J.-L. Remy, Un procede iteratif de denombrement d'arbres binaires et
son application a leur generation aleatoire, RAIRO Inform. Theor. 19
(1985), 179-195.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15
(1870), 361-376.
L. W. Shapiro, A short proof of an identity of Touchard's concerning
Catalan numbers, J. Combin. Theory, A 20 (1976), 375-376.
R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986,
Vol. 2, 1999; see especially Chapter 6.
R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull.
Amer. Math. Soc., 40 (2003), 55-68.
D. Wells, Penguin Dictionary of Curious and Interesting Numbers,
Entry 42 p 121, Penguin Books, 1987.
D. F. Bailey, Counting Arrangements of 1's and -1's, Mathematics
Magazine 69(2) 128-131 1996.
Links: M. Azaola and F. Santos, The number of triangulations of the cyclic polytope C(n,n-4), Discrete Comput. Geom., 27 (2002), 29-48. (C(n) = number of triangulations of cyclic polytope C(n,2).)
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra and Its Applications, vol. 226-228, pp. 57-72, 1995 (Abstract, pdf, ps)
D. Bill, Durango Bill's Enumeration of Binary Trees
H. Bottomley, Catalan Space Invaders
H. Bottomley, Illustration for A000108, A001147, A002694, A067310 and A067311
M. Bousquet-Melou and Gilles Schaeffer, Walks on the slit plane, Probability Theory and Related Fields, Vol. 124, no. 3 (2002), 305-344.
K. S. Brown's Mathpages, The Meanings of Catalan Numbers
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
R. M. Dickau, Catalan numbers
R. M. Dickau, Catalan Numbers (another copy)
I. Galkin, Enumeration of the Binary Trees(Catalan Numbers)
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 48
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 52
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 71
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 76
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 284
A. Karttunen, Illustration of initial terms up to size n=7
W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Colin L. Mallows and Lou Shapiro, Balls on the Lawn, J. Integer Sequences, Vol. 2, 1999, #5.
Toufik Mansour, Counting Peaks at Height k in a Dyck Path, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.1
P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
P. Peart and W.-J. Woan, Dyck Paths With No Peaks at Height k, J. Integer Sequences, 4 (2001), #01.1.3.
K. A. Penson and J.-M. Sixdeniers, Integral Representations of Catalan and Related Numbers, J. Integer Sequences, 4 (2001), #01.2.5.
N. J. A. Sloane, Illustration of initial terms
R. P. Stanley, Hipparchus, Plutarch, Schr"oder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
R. P. Stanley, Exercises on Catalan and Related Numbers
R. P. Stanley, Catalan Addendum
E. W. Weisstein, Link to a section of The World of Mathematics (1).
E. W. Weisstein, Link to a section of The World of Mathematics (2).
E. W. Weisstein, Link to a section of The World of Mathematics (3).
E. W. Weisstein, Link to a section of The World of Mathematics (4).
E. W. Weisstein, Link to a section of The World of Mathematics (5).
E. W. Weisstein, Dyck Path
W.-J. Woan, Hankel Matrices and Lattice Paths, J. Integer Sequences, 4 (2001), #01.1.2.
Index entries for "core" sequences
Index entries for sequences related to rooted trees
Index entries for sequences related to parenthesizing
Index entries for sequences related to necklaces
Formula: G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x). a(n) = Sum_{k=0..n-1}
a(k)a(n-1-k).
G.f. A(x) satisfies A = 1 + x*A^2.
a(n+1) = Sum_{i} binomial(n,2*i)*2^(n-2*i)*a(i) - Touchard.
2(2n-1)a(n-1) = (n+1)a(n).
It is known that a(n) is odd if and only if n=2^k-1, k=1,2,3,... - Emeric
Deutsch, Aug 04 2002.
Using the Stirling approximation in A000142 we get the asymptotic
expansion a(n) ~ 4^n / (sqrt(Pi * n) * (n + 1)). - Dan Fux
(danfux@my-deja.com), Apr 13 2001
Integral representation:
a(n)=int(x^n*sqrt((4-x)/x),x=0..4)/(2*Pi). - Karol A. Penson
(penson@lptl.jussieu.fr), Apr 12 2001
E.g.f.: exp(2x) (I_0(2x)-I_1(2x)), where I_n is Bessel function. -
Karol A. Penson (penson@lptl.jussieu.fr), Oct 07 2001
Maple: A000108:=n->binomial(2*n,n)/(n+1); G000108:= (1 - sqrt(1 -
4*x)) / (2*x);
spec:=[ A, {A=Prod(Z,Sequence(A))}, unlabelled ]: [
seq(combstruct[count](spec, size=n), n=0..42) ];
Math'ca: A000108[ n_ ]:=(2 n)!/n!/(n+1)!
Program: (PARI) a(n)=if(n<0,0,(2*n)!/n!/(n+1)!)
See also: Cf. A000984, A002420, A048990, A024492, A000142, A022553. A row of
A060854.
See A001003, A001190, A001699, A000081 for other ways to count
parentheses.
Enumerates objects encoded by A014486.
Keywords: core,nonn,easy,eigen,nice
Offset: 0
Author(s): njas
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================