Număr catalan

În matematică , numerele catalane formează o succesiune de numere naturale utile în multe calcule combinatorii . Ele poartă numele matematicianului belgian Eugène Charles Catalan .

L ' $n$ ${\ displaystyle n}$ $n$ -al doilea număr de catalană $C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ poate fi definit folosind coeficienți binomiali după cum urmează:

C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!n!}},\quad {\text{ per }}n\geqslant 0.

{\ displaystyle C_ {n} = {\ frac {1} {n + 1}} {2n \ choose n} = {\ frac {(2n)!} {(n + 1)! n!}}, \ quad {\ text {per}} n \ geqslant 0.}

{\ displaystyle C_ {n} = {\ frac {1} {n + 1}} {2n \ choose n} = {\ frac {(2n)!} {(n + 1)! n!}}, \ quad {\ text {for}} n \ geqslant 0.}

Secvența numerelor catalane este înregistrată în OEIS sub abrevierea A000108 ^[1] . Primele 25 de numere de catalană sunt:

1, 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430 , 4862, 16796 (= C ₁₀ ),

58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420 (= C ₂₀ ),

24466267020, 91482563640, 343059613650, 1289904147324 (= C ₂₄ ).

Definiții alternative

Numerele catalane pot fi definite recursiv prin impunere $C_{0}=1$ ${\ displaystyle C_ {0} = 1}$ $C_ {0} = 1$ Și

C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i},\quad {\text{ per }}n\geq 1.

{\ displaystyle C_ {n} = \ sum _ {i = 0} ^ {n-1} C_ {i} C_ {n-1-i}, \ quad {\ text {per}} n \ geq 1.}

{\ displaystyle C_ {n} = \ sum _ {i = 0} ^ {n-1} C_ {i} C_ {n-1-i}, \ quad {\ text {per}} n \ geq 1.}

Această relație de recurență a fost observată pentru prima dată în 1758 de de Segner ^[2] . În special, relația arată că numerele catalane sunt într-adevăr numere întregi.

O expresie alternativă este următoarea:

C_{n}={2n \choose n}-{2n \choose n-1},\quad {\text{ per }}n\geq 1.

{\ displaystyle C_ {n} = {2n \ choose n} - {2n \ choose n-1}, \ quad {\ text {per}} n \ geq 1.}

{\ displaystyle C_ {n} = {2n \ choose n} - {2n \ choose n-1}, \ quad {\ text {per}} n \ geq 1.}

Proprietate

Multe probleme combinatorii au ca soluție numerele catalane. De exemplu:

$C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ este numărul de moduri cu care este un poligon convex $n+2$ ${\ displaystyle n + 2}$ $n + 2$ laturile pot fi împărțite în triunghiuri. De exemplu, pentru $n=4$ ${\ displaystyle n = 4}$ $n = 4$ poligonul este un hexagon și modurile sunt de fapt $C_{4}=14$ ${\ displaystyle C_ {4} = 14}$ $C_ {4} = 14$ :

$C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ este numărul de cuvinte Dyck în lungime $2n$ ${\ displaystyle 2n}$ $2n$ . Un cuvânt Dyck este alcătuit din $n$ ${\ displaystyle n}$ $n$ scrisori $X$ ${\ displaystyle X}$ $X$ Și $n$ ${\ displaystyle n}$ $n$ scrisori $Da$ ${\ displaystyle Y}$ $Da$ , astfel încât fiecare segment inițial să nu mai conțină $Da$ ${\ displaystyle Y}$ $Da$ acea $X$ ${\ displaystyle X}$ $X$ . De exemplu, cuvintele lui Dyck cu $6$ ${\ displaystyle 6}$ $6$ scrisorile sunt de fapt $C_{3}=5$ ${\ displaystyle C_ {3} = 5}$ $C_ {3} = 5$ :

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

$C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ este numărul de moduri în care puteți insera $n$ ${\ displaystyle n}$ $n$ perechi de paranteze într-un produs de $n+1$ ${\ displaystyle n + 1}$ $n + 1$ factori. De exemplu, pentru $n=3$ ${\ displaystyle n = 3}$ $n = 3$ primesti

(((ab)c)d)\quad ((a(bc))d)\quad ((ab)(cd))\quad (a((bc)d))\quad (a(b(cd)))

{\ displaystyle (((ab) c) d) \ quad ((a (bc)) d) \ quad ((ab) (cd)) \ quad (a ((bc) d)) \ quad (a (b (CD)))}

(((ab) c) d) \ quad ((a (bc)) d) \ quad ((ab) (cd)) \ quad (a ((bc) d)) \ quad (a (b (cd) )))

$C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ este numărul de copaci binari plini cu $n$ ${\ displaystyle n}$ $n$ noduri părinte. Cazul este prezentat aici $n=3$ ${\ displaystyle n = 3}$ $n = 3$ :

$C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ este numărul de permutări ale numerelor întregi $1,2,\ldots ,n$ ${\ displaystyle 1,2, \ ldots, n}$ $1,2, \ ldots, n$ poate fi comandat prin stiva ;
$C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ este numărul de căi dintr-o grilă $n\times n$ ${\ displaystyle n \ times n}$ $n \ ori n$ care conectează două vârfuri opuse rămânând întotdeauna sub diagonală. Merg pentru $n=4$ ${\ displaystyle n = 4}$ $n = 4$ sunt de fapt $14$ ${\ displaystyle 14}$ $14$ :

$C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ este numărul posibilelor teselări ale unei scări de $n$ ${\ displaystyle n}$ $n$ pași cu $n$ ${\ displaystyle n}$ $n$ dreptunghiuri. De exemplu, pentru $n=4$ ${\ displaystyle n = 4}$ $n = 4$ primesti

fundal

Numele acestor numere au fost alese în onoarea matematicianului belgian Eugène Charles Catalan (1814-1884) care le studiase elegant în jurul anului 1838 . Succesiunea acestor numere fusese însă identificată deja de matematicianul germano-ungar Jan Andrej Segner (1704-1777) în secolul al XVIII-lea și fusese studiată de Euler . Mai mult, în același timp cu catalană, acesta fusese studiat de matematicianul francez Jacques Binet (1786-1857). Faptul că al nouălea număr de catalană corespunde numărului de cuvinte Dyck cu lungimea 2n a fost găsit de Désiré André în 1887.

Notă

^ (EN) secvența A000108 , on -line Encyclopedia of Integer Sequences , Fundația OEIS.
^ A. de Segner, Enumeratio modorum, quibus Figurae planae rectilineae per diagonale dividuntur in triangula. Novi commentarii academiae scientiarum Petropicolee 7 (1758/59) 203–209

Bibliografie

John Horton Conway , Richard Kenneth Guy , Cartea numerelor , Springer-Verlag, 1996, pp. 96-106.
Richard Peter Stanley (1999): Enumerative Combinatorics , Vol. 2. Cambridge University Press. (pp. 219-229)

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre problema catalană

linkuri externe

(EN) (EN) Eric W. Weisstein, număr catalan în MathWorld Wolfram Research.
( EN ) Numere catalane pe MacTutor

Controlul autorității	Tezaur BNCF 61477 · LCCN (EN) sh2008005833 · GND (DE) 1072323532

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] (EN) secvența A000108 , on -line Encyclopedia of Integer Sequences , Fundația OEIS.

[2] A. de Segner, Enumeratio modorum, quibus Figurae planae rectilineae per diagonale dividuntur in triangula. Novi commentarii academiae scientiarum Petropicolee 7 (1758/59) 203–209

[1]

[2]

V · D · M Teoria numerelor
Cele mai utilizate numere	Natural · Întreg · Par și impar
Principii generale	Principiul inducției · Principiul unei bune ordonări · Relația de echivalență
Secvențe de numere întregi	Factorial · Fibonacci · Număr de catalană · Număr Perrin · Număr de Euler · Secvență Mian-Chowla · Succesiunea lui Thue-Morse
Caracteristicile numerelor prime	Primul număr · lema lui Euclid · Teorema infinitate de numere prime · ciurul Eratostene · teste primality · Teorema fundamentală a aritmeticii · Total acoperire mine · Bézout Identitate · MCD · mcm · algoritmul lui Euclid · Teorema de Prime Numbers
Funcții aritmetice	Funcție multiplicativă · funcție aditivă · convoluție Dirichlet · funcția Euler Euler · funcția Möbius · funcția tau pe pozitiv · funcția sigmoidă · funcția Liouville · funcția Mertens
Aritmetica modulară	Teorema a restului chinez · teorema lui Fermat mici · teorema lui Euler · Criterii de divizibilitate · teorema lui Fermat pe sume de două pătrate · Wilson Teorema · reciprocitatea pătratică
Conjecturi	Conjectura lui Goldbach · Conjectura Polignac · Guess abc · conjectura primelor gemene · Conjectura lui Legendre · Noua conjectură Mersenne · Conjectura Collatz · Ipoteza Riemann
Alte	Problema lui Waring
Principalii teoreticieni	Fibonacci · Fermat · Gauss · Euler · Legendre · Riemann · Dirichlet
Disciplinele conexe	Teoria algebrică a numerelor · Teoria analitică a numerelor · Criptografie · Teoria computațională a numerelor