Číslo Narayana

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 30. června 2020; kontroly vyžadují 2 úpravy .

Narayanovo  číslo je číslo vyjádřené pomocí binomických koeficientů ( ):

;

taková čísla tvoří Narayana trojúhelník  , nižší trojúhelníková matice přirozených čísel, která se objeví v množství enumerativních combinatorics problémů .

Objevil je kanadský matematik indického původu Tadepalli Narayana (1930-1987) při řešení následující úlohy: zjistěte počet krav a jalovic, které se objevily od jedné krávy za 20 let, za předpokladu, že kráva na začátku každého roku dává se narodí jalovička a ta jalovice porodí stejné potomky na začátku roku až do věku tří let.

Prvních osm řádků čísel Narayana [1] :

k = 1 2 3 4 5 6 7 8 n = 1 | jeden 2 | jedenáct 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

Aplikace a vlastnosti

Příkladem počítacího problému, jehož řešení lze uvést pomocí čísel Narayana, je počet výrazů obsahujících dvojice závorek, které jsou správně spárovány a které obsahují různá vnoření. Například, jak čtyři páry závorek tvoří šest různých sekvencí, které obsahují dvě vnoření (vnořením máme na mysli vzor ): ()

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

Příklad ukazuje, že jediným způsobem, jak získat pouze jeden vzor,  ​​je otevírání závorek a poté uzavírání závorek. Také , protože jedinou možností je sekvence . Obecněji lze ukázat, že Narayanův trojúhelník má následující vlastnost symetrie: ()()()() … ()

.

Součet řádků trojúhelníku Narayana se rovná odpovídajícím katalánským číslům :

,

Narayana čísla tedy také počítají počet cest na dvourozměrné celočíselné mřížce od do, když se pohybují pouze podél severovýchodní a jihovýchodní úhlopříčky, neodchylují se pod osu x , s lokálními maximy. Čísla vyplývající z :

Způsoby
cesta s jedním maximem:
cesty se dvěma maximy:
cesty se třemi maximy:
cesta se čtyřmi maximy:

Součet je 1 + 6 + 6 + 1 = 14, což je katalánské číslo .

Generující funkce čísel Narayana [2] :

.

Poznámky

  1. ↑ OEIS sekvence A001263 _
  2. ↑ Petersen, 2015 , str. 25.

Literatura