Vizualizare sursă pentru „Număr Motzkin”

{{Infocaseta Șiruri de numere întregi
| named_after = Theodore Motzkin
| publication_year = 1948
| author = Theodore Motzkin
| terms_number = [[infinit]]
| formula = v. [[#Proprietăți|Proprietăți]]
| first_terms = 1, [[1 (număr)|1]], [[2 (număr)|2]], [[4 (număr)|4]], [[9 (număr)|9]], [[21 (număr)|21]], [[51 (număr)|51]]
| OEIS = A001006
| OEIS_name = Motzkin
}}
În [[matematică]] un '''număr Motzkin''', {{mvar|n}}, este numărul diferitelor moduri de a trasa [[coardă (geometrie) |coarde]] care nu se intersectează între {{mvar|n}} [[punct (geometrie) |puncte]] pe un [[cerc]]<ref name=OEIS>{{OEIS|A001006}}</ref> (nu este obligatoriu ca din fiecare punct să fie trasată o coardă). Numerele Motzkin sunt numite după [[Theodore Motzkin]] și au diverse aplicații în [[geometrie]], [[combinatorică]] și [[teoria numerelor]].

Numerele Motzkin <math>M_n</math> pentru <math>n = 0, 1, \dots</math> formează șirul:<ref name=OEIS/><ref name=C52>Marius Coman, ''Enciclopedia matematică a claselor de numere întregi'', Columbus, Ohio: Education Publishing, 2013, {{ISBN|978-1-59973-237-4}}, p.&nbsp;52</ref>
: 1, [[1 (număr)|1]], [[2 (număr)|2]], [[4 (număr)|4]], [[9 (număr)|9]], [[21 (număr)|21]], [[51 (număr)|51]], [[127 (număr)|127]], 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ... 

== Exemple ==
Următoarea figură prezintă cele 9 moduri de a trasa coarde care nu se intersectează între 4 puncte pe un cerc ({{math|1=''M''<sub>4</sub> = 9}}):
:[[Fișier:MotzkinChords4.svg]]

Următoarea figură prezintă cele 21 de moduri de a trasa coarde care nu se intersectează între 5 puncte pe un cerc ({{math|1=''M''<sub>5</sub> = 21}}):

:[[Fișier:MotzkinChords5.svg]]

== Proprietăți ==
Numerele Motzkin satisfac următoarele [[relație de recurență |relații de recurență]]:<ref name=C52/>
:<math>M_{n}=M_{n-1}+\sum_{i=0}^{n-2}M_iM_{n-2-i}=\frac{2n+1}{n+2}M_{n-1}+\frac{3n-3}{n+2}M_{n-2}.</math>
unde <math>M_0=M_1=1</math>.

Numerele Motzkin pot fi exprimate prin [[coeficient binomial |coeficienți binomial]] și [[Număr Catalan |numere Catalan]]:
:<math>M_n=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} C_k.</math>

Funcția genertoare <math>m(x) = \sum_{n=0}^\infty M_n x^n</math> a numerelor Motzkin satisface relația:
:<math>x^2 m(x)^2 + (x - 1) m(x) + 1 = 0</math>.

Un '''număr prim Motzkin''' este un număr Motzkin care este și [[număr prim|prim]].<ref name=C52/> {{Asof|2013|October}}. Se cunosc doar patru asemenea numere:<ref name=C52/><ref>{{OEIS|A092832}}</ref>
:2, 127, 15511, 953467954114363 

== Interpretări combinatorice ==
Al {{mvar|n}}-lea număr Motzkin este și numărul de secvențe întregi pozitive de lungime {{math|1 = ''n'' &minus; 1}} în care elementele de început și sfârșit sunt fie 1 sau 2, iar diferența dintre oricare două elemente consecutive este &minus;1, 0 sau 1. Echivalent, al {{mvar|n}}-lea număr Motzkin este numărul de secvențe întregi pozitive de lungime {{math|1 = ''n'' + 1}} în care elementele de început și sfârșit sunt 1, iar diferența dintre oricare două elemente consecutive este &minus;1, 0 sau 1.

Al {{mvar|n}}-lea număr Motzkin dă și numărul de căi din primul cadran (dreapta sus) al unei grile de la coordonatele (0, 0) la coordonatele ({{mvar|n}}, 0) în {{mvar|n}} pași dacă cineva are voie să se deplaseze doar spre dreapta (în sus, în jos sau înainte) la fiecare pas, dar este interzis să tracă sub axa {{mvar|y}}&nbsp;=&nbsp;0.

De exemplu, imaginea următoare arată cele 9 căi valide de la (0, 0) la (4, 0):
:[[Fișier:Motzkin4.svg]]

Există cel puțin paisprezece utilizări diferite ale numerelor Motzkin în diferite ramuri ale matematicii, cum le-a enumerat {{harvtxt|Donaghey|Shapiro|1977}} în studiul numerelor Motzkin. {{harvtxt|Guibert|Pergola|Pinzani|2001}} a arătat că permutările vexilare sunt enumerate prin numere Motzkin.

== Note ==
<references />

== Bibliografie ==
* {{en icon}} {{citation
 | last = Bernhart
 | first = Frank R.
 | title = Catalan, Motzkin, and Riordan numbers 
 | journal = Discrete Mathematics
 | volume = 204
 | year = 1999
 | pages = 73–112
 | doi = 10.1016/S0012-365X(99)00054-0
 | issue = 1-3}}
* {{en icon}} {{citation
 | last1 = Donaghey
 | first1 = R.
 | last2 = Shapiro
 | first2 = L. W.
 | title = Motzkin numbers
 | journal = Journal of Combinatorial Theory | series = Series A
 | volume = 23
 | issue = 3
 | year = 1977
 | pages = 291–301
 | mr = 0505544
 | doi = 10.1016/0097-3165(77)90020-6}}
* {{en icon}} {{Citation | last1=Guibert | first1=O. | last2=Pergola | first2=E. | last3=Pinzani | first3=R. | title=Vexillary involutions are enumerated by Motzkin numbers | doi=10.1007/PL00001297 | year=2001 | journal=Annals of Combinatorics | issn=0218-0006 | volume=5 | issue=2 | pages=153–174 | mr=1904383}}
* {{en icon}} {{citation
 | last = Motzkin
 | first = Theodore
 | title = Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products
 | journal = Bulletin of the American Mathematical Society
 | volume = 54
 | year = 1948
 | pages = 352–360
 | doi = 10.1090/S0002-9904-1948-09002-4
 | issue = 4}}
<!--
== Vezi și ==
* [[Număr Delannoy]]
* [[Număr Narayana]]
* [[Număr Schröder]]
-->
== Vezi și ==
* [[Număr Delannoy]]
* [[Număr Narayana]]
* [[Număr Schröder]]
* [[Număr Schröder–Hiparh]]
* [[Număr Catalan]]

== Legături externe ==
* {{en icon}} {{MathWorld|title=Motzkin Number|urlname=MotzkinNumber}}

[[Categorie:Șiruri de numere întregi|Motzkin]]
[[Categorie:Combinatorică]]