Katalánský trojúhelník - Catalans triangle - Wikipedia

v kombinatorická matematika, Katalánský trojúhelník je číselný trojúhelník jehož záznamy ${ displaystyle C (n, k)}$ uveďte počet řetězců skládajících se z n X a k Y jsou takové, že žádný počáteční segment řetězce nemá více Y než X. Jedná se o zobecnění Katalánská čísla, a je pojmenována po Eugène Charles Catalan. Bailey^[1] ukázat to ${ displaystyle C (n, k)}$ splňují následující vlastnosti:

${ displaystyle C (n, 0) = 1 { text {pro}} n geq 0}$ .
${ displaystyle C (n, 1) = n { text {pro}} n geq 1}$ .
${ displaystyle C (n + 1, k) = C (n + 1, k-1) + C (n, k) { text {pro}} 1$
${ displaystyle C (n + 1, n + 1) = C (n + 1, n) { text {pro}} n geq 1}$ .

Vzorec 3 ukazuje, že položka v trojúhelníku je získána rekurzivně přidáním čísel nalevo a výše v trojúhelníku. Nejstarší výskyt katalánského trojúhelníku spolu s rekurzním vzorcem je na straně 214 pojednání o kalkulu publikovaném v roce 1800^[2] podle Louis François Antoine Arbogast.

Shapiro^[3] zavádí další trojúhelník, který nazývá katalánský trojúhelník, který je odlišný od zde diskutovaného trojúhelníku.

Obecný vzorec

Obecný vzorec pro ${ displaystyle C (n, k)}$ darováno^[1]^[4]

{ displaystyle C (n, k) = { frac {(n + k)! (n-k + 1)} {k! (n + 1)!}},}

kde $n$ a $k$ jsou nezáporná celá čísla a $n!$ označuje faktoriál. Tedy pro $k$ >0, ${ displaystyle C (n, k) = left ({ begin {pole} {c} n + k k end {array}} right) - left ({ begin {pole} {c} n + k k-1 end {pole}} vpravo)}$ .

Úhlopříčka $C (n, n)$ je $n$ -th Katalánské číslo. Součet řádků $n$ -tý řádek je $(n + 1)$ -th Katalánské číslo.

Některé hodnoty jsou dány^[5]

k n	0	1	2	3	4	5	6	7	8
0	1
1	1	1
2	1	2	2
3	1	3	5	5
4	1	4	9	14	14
5	1	5	14	28	42	42
6	1	6	20	48	90	132	132
7	1	7	27	75	165	297	429	429
8	1	8	35	110	275	572	1001	1430	1430

Zobecnění

Katalánské lichoběžníky jsou spočetnou množinou lichoběžníků, které zobecňují katalánský trojúhelník. Katalánský lichoběžník řádu $m = 1, 2, 3, ...$ je číslo lichoběžníku, jehož položky ${ displaystyle C_ {m} (n, k)}$ uveďte počet řetězců skládajících se z $n$ X-s a $k$ Y tak, že v každém počátečním segmentu řetězce počet Y nepřekročí počet X o $m$ nebo více.^[6] Podle definice je katalánský lichoběžník řádu $m = 1$ je katalánský trojúhelník, tj. ${ displaystyle C_ {1} (n, k) = C (n, k)}$ .

Některé hodnoty katalánského lichoběžníku řádu $m = 2$ jsou dány

k n	0	1	2	3	4	5	6	7	8
0	1	1
1	1	2	2
2	1	3	5	5
3	1	4	9	14	14
4	1	5	14	28	42	42
5	1	6	20	48	90	132	132
6	1	7	27	75	165	297	429	429
7	1	8	35	110	275	572	1001	1430	1430

Některé hodnoty katalánského lichoběžníku řádu $m = 3$ jsou dány

k n	0	1	2	3	4	5	6	7	8	9
0	1	1	1
1	1	2	3	3
2	1	3	6	9	9
3	1	4	10	19	28	28
4	1	5	15	34	62	90	90
5	1	6	21	55	117	207	297	297
6	1	7	28	83	200	407	704	1001	1001
7	1	8	36	119	319	726	1430	2431	3432	3432

Každý prvek je opět součtem prvku nahoře a prvku nalevo.

Obecný vzorec pro ${ displaystyle C_ {m} (n, k)}$ darováno

{ displaystyle C_ {m} (n, k) = { začátek {případy} doleva ({ začátek {pole} {c} n + k k konec {pole}} doprava) & , , , 0 leq k n + m-1 end {cases}}}

( $n = 0, 1, 2, ...$ , $k = 0, 1, 2, ...$ , $m = 1, 2, 3, ...$ ).

Důkazy obecného vzorce pro ${ displaystyle C_ {m} (n, k)}$

Důkaz 1

Tento důkaz zahrnuje rozšíření metody Andres Reflection, která byla použita ve druhém důkazu pro Katalánské číslo. Následující ukazuje, jak každá cesta zleva dole ${ displaystyle (0,0)}$ vpravo nahoře ${ displaystyle (k, n)}$ diagramu, který překračuje omezení ${ displaystyle n-k + m-1 = 0}$ lze také promítnout do koncového bodu ${ displaystyle (n + m, k-m)}$ .

Zvažujeme tři případy, abychom určili počet cest ${ displaystyle (0,0)}$ na ${ displaystyle (k, n)}$ které nepřekračují omezení:

(1) kdy ${ displaystyle m> k}$ omezení nelze překročit, takže všechny cesty z ${ displaystyle (0,0)}$ na ${ displaystyle (k, n)}$ jsou platné, tj. ${ displaystyle C_ {m} (n, k) = doleva ({ začátek {pole} {c} n + k k konec {pole}} doprava)}$ .

(2) kdy ${ displaystyle k-m + 1> n}$ je nemožné vytvořit cestu, která nepřekročí omezení, tj. ${ displaystyle C_ {m} (n, k) = 0}$ .

(3) kdy ${ displaystyle m leq k leq n + m-1}$ , pak ${ displaystyle C_ {m} (n, k)}$ je počet „červených“ cest ${ displaystyle left ({ begin {pole} {c} n + k k end {pole}} doprava)}$ minus počet 'žlutých' cest, které překračují omezení, tj. ${ displaystyle left ({ begin {pole} {c} (n + m) + (km) km end {pole}} right) = left ({ begin {pole} {c} n + k km end {pole}} vpravo)}$ .

Tedy počet cest z ${ displaystyle (0,0)}$ na ${ displaystyle (k, n)}$ které nepřekračují omezení ${ displaystyle n-k + m-1 = 0}$ je uvedeno ve vzorci v předchozí části "Zobecnění".

Důkaz 2

Nejprve potvrdíme platnost relace opakování ${ displaystyle C_ {m} (n, k) = C_ {m} (n-1, k) + C_ {m} (n, k-1)}$ rozbitím ${ displaystyle C_ {m} (n, k)}$ do dvou částí, první pro XY kombinace končící na X a druhá pro ty, které končí Y. První skupina tedy má ${ displaystyle C_ {m} (n-1, k)}$ platné kombinace a druhá má ${ displaystyle C_ {m} (n, k-1)}$ . Důkaz 2 je dokončen ověřením, že řešení splňuje relaci opakování a dodržuje počáteční podmínky ${ displaystyle C_ {m} (n, 0)}$ a ${ displaystyle C_ {m} (0, k)}$ .

Viz také

Pascalův trojúhelník

Reference

^ ^A ^b Bailey, D. F. (1996). "Počítání uspořádání 1 a -1". Matematický časopis. 69 (2): 128–131. doi:10.1080 / 0025570X.1996.11996408.
^ Arbogast, L. F. A. (1800). Du Calcul des Derivations. str.214.
^ Shapiro, L. W. (1976). „Katalánský trojúhelník“. Diskrétní matematika. 14 (1): 83–90. doi:10.1016 / 0012-365x (76) 90009-1.
^ Eric W. Weisstein. „Katalánský trojúhelník“. MathWorld - webový zdroj Wolfram. Citováno 28. března 2012.
^ Sloane, N. J. A. (vyd.). „Sequence A009766 (Catalan's triangle)“. The On-line encyklopedie celočíselných sekvencí. Nadace OEIS. Citováno 28. března 2012.
^ Reuveni, Shlomi (2014). „Katalánské lichoběžníky“. Pravděpodobnost v technických a informačních vědách. 28 (3): 4391–4396. doi:10.1017 / S0269964814000047.

[Bailey1996-1] A ^b Bailey, D. F. (1996). "Počítání uspořádání 1 a -1". Matematický časopis. 69 (2): 128–131. doi:10.1080 / 0025570X.1996.11996408.

[arbogast-2] Arbogast, L. F. A. (1800). Du Calcul des Derivations. str.214.

[Shapiro1976-3] Shapiro, L. W. (1976). „Katalánský trojúhelník“. Diskrétní matematika. 14 (1): 83–90. doi:10.1016 / 0012-365x (76) 90009-1.

[4] Eric W. Weisstein. „Katalánský trojúhelník“. MathWorld - webový zdroj Wolfram. Citováno 28. března 2012.

[5] Sloane, N. J. A. (vyd.). „Sequence A009766 (Catalan's triangle)“. The On-line encyklopedie celočíselných sekvencí. Nadace OEIS. Citováno 28. března 2012.

[Reuveni_PEIS_2014-6] Reuveni, Shlomi (2014). „Katalánské lichoběžníky“. Pravděpodobnost v technických a informačních vědách. 28 (3): 4391–4396. doi:10.1017 / S0269964814000047.

[1]

[2]

[3]

[4]

[5]

[6]