Schröderovo číslo - Schröder number

v matematika, Schröderovo číslo ${displaystyle S_ {n},}$ také se nazývá a velké Schröderovo číslo nebo velké Schröderovo číslo, popisuje počet příhradové cesty od jihozápadního rohu ${displaystyle (0,0)}$ z ${displaystyle n imes n}$ mřížka do severovýchodního rohu ${displaystyle (n, n),}$ pomocí pouze jednotlivých kroků na sever, ${displaystyle (0,1);}$ severovýchod, ${displaystyle (1,1);}$ nebo na východ, ${displaystyle (1,0),}$ které nestoupají nad SW – NE úhlopříčku.^[1]

Prvních několik Schröderových čísel je

1, 2, 6, 22, 90, 394, 1806, 8558, ... (sekvence A006318 v OEIS ).

kde ${displaystyle S_ {0} = 1}$ a ${displaystyle S_ {1} = 2.}$ Byly pojmenovány po německém matematikovi Ernst Schröder.

Příklady

Následující obrázek ukazuje 6 takových cest skrz a ${displaystyle 2 imes 2}$ mřížka:

Související konstrukce

Schröderova cesta délky ${displaystyle n}$ je příhradová cesta z ${displaystyle (0,0)}$ na ${displaystyle (2n, 0)}$ s kroky na severovýchod, ${displaystyle (1,1);}$ východní, ${displaystyle (2,0);}$ a jihovýchod, ${displaystyle (1, -1),}$ které nespadají pod ${displaystyle x}$ -osa. The ${displaystyle n}$ th Schröderovo číslo je počet Schröderových délkových cest ${displaystyle n}$ .^[2] Následující obrázek ukazuje 6 Schröderových cest délky 2.

Podobně Schröderova čísla počítají počet způsobů, jak rozdělit a obdélník do ${displaystyle n + 1}$ menší obdélníky pomocí ${displaystyle n}$ prořízne ${displaystyle n}$ body dané uvnitř obdélníku v obecné poloze, přičemž každý řez protíná jeden z bodů a rozdělí pouze jeden obdélník na dva. Je to podobné jako v procesu triangulace, ve kterém je tvar rozdělen na nepřekrývající se trojúhelníky místo obdélníků. Následující obrázek ukazuje 6 takových pitev obdélníku do 3 obdélníků pomocí dvou řezů:

Na obrázku níže je 22 disekcí obdélníku do 4 obdélníků pomocí tří řezů:

Schröderovo číslo ${displaystyle S_ {n}}$ také počítá oddělitelné obměny délky ${displaystyle n-1.}$

Související sekvence

Schröderova čísla se někdy nazývají velký nebo velký Schröderova čísla, protože existuje další Schröderova sekvence: the malá Schröderova čísla, také známý jako Čísla Schröder-Hipparchus nebo superkatalánská čísla. Spojení mezi těmito cestami lze vidět několika způsoby:

Zvažte cesty z ${displaystyle (0,0)}$ na ${displaystyle (n, n)}$ s kroky ${displaystyle (1,1),}$ ${displaystyle (2,0),}$ a ${displaystyle (1, -1)}$ které nestoupají nad hlavní úhlopříčku. Existují dva typy cest: ty, které mají pohyby podél hlavní úhlopříčky a ty, které ne. (Velká) Schröderova čísla počítají oba typy cest a malá Schröderova čísla počítají pouze cesty, které se dotýkají pouze úhlopříčky, ale nemají po ní žádné pohyby.^[3]

Stejně jako existují (velké) Schröderovy cesty, malá Schröderova cesta je Schröderova cesta, která nemá žádné vodorovné schody ${displaystyle x}$ -osa.^[4]

Li ${displaystyle S_ {n}}$ je ${displaystyle n}$ číslo Schröder a ${displaystyle s_ {n}}$ je ${displaystyle n}$ tedy malé Schröderovo číslo ${displaystyle S_ {n} = 2 s_ {n}}$ pro ${displaystyle n> 0}$ ${displaystyle (S_ {0} = s_ {0} = 1).}$ ^[4]

Schröderovy cesty jsou podobné Dyckovy cesty ale povolte horizontální krok místo pouze diagonálních kroků. Další podobná cesta je typ cesty, kterou Motzkinova čísla počet; cesty Motzkin umožňují stejné úhlopříčné cesty, ale umožňují pouze jeden vodorovný krok (1,0) a počítají od nich ${displaystyle (0,0)}$ na ${displaystyle (n, 0)}$ .^[5]

Je tam také trojúhelníkové pole spojené s čísly Schröder, která poskytuje a relace opakování^[6] (i když nejen s Schröderovými čísly). Prvních pár výrazů je

1, 1, 2, 1, 4, 6, 1, 6, 16, 22, .... (sekvence A033877 v OEIS ).

Je snazší vidět spojení s čísly Schrödera, když je sekvence v trojúhelníkovém tvaru:

$k$ $n$	0	1	2	3	4	5	6
0	1
1	1	2
2	1	4	6
3	1	6	16	22
4	1	8	30	68	90
5	1	10	48	146	304	394
6	1	12	70	264	714	1412	1806

Pak jsou Schröderova čísla diagonálními položkami, tj. ${displaystyle S_ {n} = T (n, n)}$ kde ${displaystyle T (n, k)}$ je položka v řádku ${displaystyle n}$ a sloupec ${displaystyle k}$ . Vztah opakování daný tímto uspořádáním je

{displaystyle T (n, k) = T (n, k-1) + T (n-1, k-1) + T (n-1, k)}

s ${displaystyle T (1, k) = 1}$ a ${displaystyle T (n, k) = 0}$ pro ${displaystyle k> n}$ .^[6] Dalším zajímavým postřehem je, že součet ${displaystyle n}$ th řádek je ${displaystyle (n + 1)}$ Svatý malé Schröderovo číslo; to je

{displaystyle sum _ {k = 0} ^ {n} T (n, k) = s_ {n + 1}}

.

Vztah opakování

{displaystyle S_ {n} = 3S_ {n-1} + součet _ {k = 1} ^ {n-2} S_ {k} S_ {n-k-1}}

pro

{displaystyle ngeq 2}

s

{displaystyle S_ {0} = 1}

,

{displaystyle S_ {1} = 2}

.^[7]

Generující funkce

The generující funkce ${displaystyle G (x)}$ z ${displaystyle (S_ {n})}$ je

{displaystyle G (x) = {frac {1-x- {sqrt {x ^ {2} -6x + 1}}} {2x}} = součet _ {n = 0} ^ {infty} S_ {n} x ^ {n}}

.^[7]

Použití

Jedno téma kombinatorika je obklady tvary a jedna konkrétní instance tohoto je domino obklady; otázka v tomto případě zní: „Kolik domino (tj. ${displaystyle 1 imes 2}$ nebo ${displaystyle 2 imes 1}$ můžeme uspořádat nějaký tvar tak, aby se žádné z domino nepřekrývalo, celý tvar byl zakryt a žádná z domino nevyčnívala z tvaru? “Tvar, se kterým Schröderova čísla souvisejí, je Aztécký diamant. Níže je pro referenci uveden aztécký diamant řádu 4 s možným domino obkladem.

Ukazuje se, že určující z ${displaystyle (2n-1) imes (2n-1)}$ Hankelova matice Schröderových čísel, tj. čtvercové matice, jejíž ${displaystyle (i, j)}$ th vstup je ${displaystyle S_ {i + j-1},}$ je počet domino obkladů objednávky ${displaystyle n}$ Aztécký diamant, který je ${displaystyle 2 ^ {n (n + 1) / 2}.}$ ^[8] To znamená