Some more properties of Catalan numbers

Barcucci, Elena; Verri, Maria Cecilia

We want to illustrate some correspondences between Catalan numbers and combinatoric objects, such as plane walks, binary trees and some particular words. By means of under-diagonal walks, we give a combinatorial interpretation of the formula Cn = 1 n+1 2n n defining Catalan numbers. These numbers also enumerate both words in a particular language defined on a four character alphabet and the corresponding walks made up of four different types of steps. We illustrate a bijection between n-long words in this language and binary trees having n + 1 nodes, after which we give a simple proof of Touchard's formula.

trova@unifi

Titolo:	Some more properties of Catalan numbers
Autori di Ateneo:	BARCUCCI, ELENA VERRI, MARIA CECILIA
Autori:	BARCUCCI, ELENA; VERRI, MARIA CECILIA
Anno di registrazione:	1992
Rivista:	DISCRETE MATHEMATICS
Volume:	102
Pagina iniziale:	229
Pagina finale:	237
Abstract:	We want to illustrate some correspondences between Catalan numbers and combinatoric objects, such as plane walks, binary trees and some particular words. By means of under-diagonal walks, we give a combinatorial interpretation of the formula Cn = 1 n+1 2n n defining Catalan numbers. These numbers also enumerate both words in a particular language defined on a four character alphabet and the corresponding walks made up of four different types of steps. We illustrate a bijection between n-long words in this language and binary trees having n + 1 nodes, after which we give a simple proof of Touchard's formula.
Handle:	http://hdl.handle.net/2158/10704
Appare nelle tipologie:	1a - Articolo su rivista

File in questo prodotto:

Non ci sono file associati a questo prodotto.

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/2158/10704

Citazioni

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.