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:

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

Catalanen zenbakiak n ${\displaystyle 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

Ikus ditzagun Catalnen zenbakien oinarrizko propietateak:

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

Catalan zenbakien errepikapen erlazioa:

${\displaystyle {\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}}}$

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

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

Esanahi konbinatorioa

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

Izan bitez, ${\displaystyle M(a,b)}$,${\displaystyle 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.

${\displaystyle g:(x,y)\rightarrow (x+1,y+1)}$ Atal gorakorrak eta ${\displaystyle 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 ${\displaystyle \emptyset _{2}^{*}n}$ denotatuko dugu, eta Dyck-en ibilbide hertsien multzoa ${\displaystyle \emptyset ^{*}*_{2}n}$.

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

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

Izan bitez, ${\displaystyle \emptyset _{2}n}$ eta ${\displaystyle 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 ${\displaystyle c(\emptyset _{2}n)={\binom {2n}{n}}}$. Gainera, ${\displaystyle 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, ${\displaystyle \left({\frac {2n}{n+1}}\right)}$ dela, ${\displaystyle n+1}$ aldiz beherantz eta ${\displaystyle n-1}$ aldiz gorantz egiten baitugu.

Beraz, ${\displaystyle 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 ${\displaystyle T_{n}}$ balboa n+2 erpin zenbakituak dituen poligono konbexuaren triangeluazio kopurua.

${\displaystyle {\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 ${\displaystyle k\in [n]}$ baliorako kontsideratzen dugu ${\displaystyle A_{k}}$ familia, k, n+1 eta n+2 erpineko triangelua duten triangeluazioen multzoa. ${\displaystyle T_{n}}$ kalkulatu ahal da ${\displaystyle {A_{1},A_{2},...,A_{n}}}$ triangeluazioen partiketa dela erabiliz. Hortaz, batuketaren erregelagatik, ${\displaystyle T_{n}=c(A_{1})+...+c(A_{n})}$ dugu. Gainera, biderkaduraren erregela erabiliz ${\displaystyle 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

• Maria Merino Maestre, Matematika Diskretua

Kanpo estekak

• Datuak: Q270513
• Multimedia: Catalan numbers / Q270513