Catalanen zenbakiak

Konbinatorian, Catalanen zenbakiak zenbaki arrunten segida osatzen dute. Izena Eugene Charles Catalan(1814-1894) matematikariaren omenez dator.

Catalan n.garren zenbakia formula honen bitartez lortzen da:

$C_{n}={\frac {n}{n+1}}{\binom {2n}{n}},n=0,1,2...$

Catalanen zenbakiak

n	$C_{n}$
0	1
1	1
2	2
3	5
4	14
5	42
6	132
7	429
8	1.430
9	4.862
10	16.796
11	58.786
12	208.012
13	742.900
14	2.674.440
15	9.694.845
16	35.357.670
17	129.644.790
18	477.638.700
19	1.767.263.190
20	6.564.120.420
21	24.466.267.020
22	91.482.563.640
23	343.059.613.650
24	1.289.904.147.324
25	4.861.946.401.452

Oinarrizko propietateak aldatu

Ikus ditzagun Catalnen zenbakien oinarrizko propietateak:

$C_{n}={\binom {2n}{n}}-{\binom {2n}{n+1}}$
$C_{n}\in \mathbb {N} ,\forall n\in \mathbb {N} ^{*}.$ Ondorioz, $n+1|\left({\frac {2n}{n}}\right)$

Catalan zenbakien errepikapen erlazioa:

${\begin{cases}C_{0}=1\\C_{n}=C_{o}C_{n}+C_{1}C_{(}n-2)+...+C_{(}n-1)C_{0},n\geq 1\end{cases}}$

$(C_{n})_{n}\geq 0$ segidaren funtzio sortzailea:

$C(x)=\left({\frac {1-{\sqrt {1-4x}}}{2x}}\right),|x|\leq {\frac {1}{4}}$

Esanahi konbinatorioa aldatu

Esanahi konbinatorio bat , (0,0)-tik (2n,0)-ra dozen ibilbide positieboen multzoa da.

Izan bitez, $M(a,b)$ , $N(c,d)\in \mathbb {Z} \times \mathbb {Z} ,a\leq c$ M-tik N-ra doan gorabehera ibilbidea M-n hasten dena eta N-n amaitzen den lerro jarraitua da.

$g:(x,y)\rightarrow (x+1,y+1)$ Atal gorakorrak eta $b:(x,y)\rightarrow (x+1,y-1)$ atal beherakorrak dituena. (0,0)-tk (2n,0)-ra doan gorabehera ibilbidea Dycken-ibilbidea (ingelesez Dyck path) dela esaten da baldin eta y ≥ 0 erdiplanoaren barruan badago. Gainera, y=0 Areatza soilik (0,0) eta (K,o) puntuetan ukitzen badu, Dyck-en ibilbidea hertsia dela diogu. Dyck-en ibilbideen multzoa $\emptyset _{2}^{*}n$ denotatuko dugu, eta Dyck-en ibilbide hertsien multzoa $\emptyset ^{*}*_{2}n$ .

Bi multzo hauek definituta, hurrengo berdintza lortzen da, Catalanen zenbakien esanahi konbinatorioa defitzen duelarik.

$c(\emptyset _{2}^{*}n)=C_{n},\forall n\geq 0$

Izan bitez, $\emptyset _{2}n$ eta $c({\overline {\emptyset _{2}^{*}n}})$ , (0,0)-tik (2n,0)-ra dozen gorabehera ibilbideen multzoa eta Dyck-enak ez diren gora behera ibilbideen multzoa, hurrenez hurren. Ohartu $c(\emptyset _{2}n)={\binom {2n}{n}}$ . Gainera, $c({\overline {\emptyset _{2}^{*}n}})={\binom {2n}{n+1}}$ ; izan ere itzulpen bat dago(0,0)-tik (2n,0)-ra dozen ibilbide ez-positiboen artisan eta (0,0)-tik (2n,-2)-ra Doan ibilbideen artean. Itzulpena da y=-1 ukitzen duen lehengo alditik aurrera isla hartzea, hau da, hortik aurrera goranzko pausa bmkoitza beheranzko hartzea eta beheranzkoak goranzko hartzea. Azkenik, argi dago (0,0)-tik (2n,-2)-ra don ibilbide kopurua, $\left({\frac {2n}{n+1}}\right)$ dela, $n+1$ aldiz beherantz eta $n-1$ aldiz gorantz egiten baitugu.

Beraz, $c(\emptyset _{2}^{*}n)=c(\emptyset _{2}n)-c({\overline {\emptyset _{2}^{*}n}})={\binom {2n}{n}}-{\binom {2n}{n+1}}=C_{n}$

Beste esanahi konbinatorioa bat poligono konbexuaren triangulazioa izango litzateke.

Poligono konbexuaren triangeluazioa poligonoa triangeluen bidez banatzean datza, non triangeluen barnealdeak binaka bateraezinak baitira eta triangeluen erpinak poligonoaren erpinak baitira(hots, triangeluen alder poligonoaren alder edo diagonalak dira.

Har dezagun n aldeko poligono konbexua eta, jarraian, erpin bakoitzari zenbaki bat esleituko diezaiogun, erlojuaren orratzen kontrako noranzkoan. Izan bedi $T_{n}$ balboa n+2 erpin zenbakituak dituen poligono konbexuaren triangeluazio kopurua.

${\begin{cases}T_{0}=1\\T_{1}=2\\T_{3}=5\\T_{4}=6\\...\\T_{n}=T_{0}T_{(}n-1)+T_{1}T_{(}n-2)+...+T_{(}n-1)T_{0},n\geq 1\end{cases}}$

Edozein $k\in [n]$ baliorako kontsideratzen dugu $A_{k}$ familia, k, n+1 eta n+2 erpineko triangelua duten triangeluazioen multzoa. $T_{n}$ kalkulatu ahal da ${A_{1},A_{2},...,A_{n}}$ triangeluazioen partiketa dela erabiliz. Hortaz, batuketaren erregelagatik, $T_{n}=c(A_{1})+...+c(A_{n})$ dugu. Gainera, biderkaduraren erregela erabiliz $c(A_{k})=T_{(}k-1)T_{n}-k$ ; izan ere, {n+2,1...,k} eta {k,....,n+1} erpinak osaturiko poligono konbexuak triangelizatu behar ditugu independenteki.

Bibliografia aldatu

Maria Merino Maestre, Matematika Diskretua

Kanpo estekak aldatu

Datuak: Q270513
Multimedia: Catalan numbers / Q270513