Narayana nummer

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 30. juni 2020; checks kræver 2 redigeringer .

Narayana-  tallet er et tal udtrykt i binomiale koefficienter ( ):

;

sådanne tal danner Narayana-trekanten  , en lavere trekantet matrix af naturlige tal, der optræder i en række opremsende kombinatoriske problemer .

De blev opdaget af den canadiske matematiker af indisk oprindelse Tadepalli Narayana (1930-1987), da han løste følgende problem: find antallet af køer og kvier, der dukkede op fra en ko på 20 år, forudsat at koen i begyndelsen af ​​hvert år giver føder en kvie, og kvien føder det samme afkom i begyndelsen af ​​året, når de bliver tre år.

De første otte rækker af Narayana-tal [1] :

k = 1 2 3 4 5 6 7 8 n = 1 | en 2 | elleve 3 | 1 3 1 4 | 1 6 6 1 5 | 1 10 20 10 1 6 | 1 15 50 50 15 1 7 | 1 21 105 175 105 21 1 8 | 1 28 196 490 490 196 28 1

Applikationer og egenskaber

Et eksempel på et tælleproblem, hvis løsning kan gives i form af Narayana-tal, er antallet af udtryk, der indeholder par af parenteser, der er korrekt matchede, og som indeholder forskellige rede. For eksempel, hvordan fire par parenteser danner seks forskellige sekvenser, der indeholder to indlejringer (med indlejringer mener vi et mønster ): ()

()((())) (())(()) (()(())) ((()())) ((())()) ((()))()

Eksemplet viser, at da den eneste måde at få kun ét mønster  på er at åbne parenteser og derefter lukke parenteser. Også da den eneste mulighed er sekvensen . Mere generelt kan det vises, at Narayanas trekant har følgende symmetriegenskab: ()()()() … ()

.

Summen af ​​rækkerne i Narayana trekanten er lig med de tilsvarende catalanske tal :

,

således tæller Narayana-tal også antallet af stier på et todimensionelt heltalsgitter fra til, når de kun bevæger sig langs de nordøstlige og sydøstlige diagonaler, ikke afvigende under x- aksen , med lokale maksima. Tal som følge af :

måder
sti med et maksimum:
stier med to maksima:
stier med tre maksima:
sti med fire maksima:

Summen er 1 + 6 + 6 + 1 = 14, som er det catalanske tal .

Genereringsfunktion af Narayana-tal [2] :

.

Noter

  1. ↑ OEIS -sekvens A001263 _
  2. ↑ Petersen, 2015 , s. 25.

Litteratur