Riffle shuffle permutace - Riffle shuffle permutation

V matematice obměny a studium míchání hrací karty, a riffle shuffle permutace je jedním z obměny sady n položky, které lze získat jediným riffle shuffle, ve kterém je seřazená paluba n karty jsou rozřezány na dva balíčky a poté jsou oba balíčky prokládány (např. přesunutím karet po jedné ze spodní části jednoho nebo druhého z balíčků do horní části tříděného balíčku). Počínaje uspořádanou sadou (1 vzestupná sekvence) je matematicky riffle shuffle definována jako permutace této sady obsahující 1 nebo 2 vzestupné sekvence.^[1] Permutace s 1 rostoucí sekvencí jsou permutace identity.

Jako zvláštní případ to je (p,q)-zamíchat, pro čísla p a q s p + q = n, je riffle, ve které má první paket p karty a druhý balíček má q karty.^[2]

Kombinatorický výčet

Protože (p,q) -hodnost je zcela určena tím, jak je první p prvky jsou mapovány, počet (p,q) -shuffles je

${ displaystyle { binom {p + q} {p}}.}$

Počet zřetelných riffů však není zcela součtem tohoto vzorce přes všechny možnosti p a q přidávání do n (což by bylo 2ⁿ), protože permutace identity lze reprezentovat několika způsoby jako (p,q) -shuffle pro různé hodnoty p a qMísto toho počet zřetelných permutací riffle shuffle na palubě n karty, pro n = 1, 2, 3, ..., je

1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ... (sekvence A000325 v OEIS )

Obecněji vzorec pro toto číslo je 2ⁿ − n; například, tam je 4503599627370444 riffle shuffle permutace balíčku 52 karet.

Počet permutací, které jsou jak permutací riffle shuffle, tak inverzní permutací riffle shuffle, je^[3]

${ displaystyle { binom {n + 1} {3}} + 1.}$

Pro n = 1, 2, 3, ..., to je

1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ... (sekvence A050407 v OEIS )

a pro n = 52 existuje přesně 23427 invertibilních shuffles.

Náhodné rozdělení

The Gilbert – Shannon – rákosový model popisuje náhodné rozdělení pravděpodobnosti na riffle shuffles, což je dobrá shoda pro pozorované lidské shuffle.^[4] V tomto modelu je permutace identity má pravděpodobnost (n + 1)/2ⁿ a všechny ostatní permutace rifle mají stejnou pravděpodobnost 1/2ⁿ generování. Na základě své analýzy tohoto modelu matematici doporučili, aby balíček 52 karet dostal sedm riffů, aby byl důkladně randomizován.^[5]

Permutační vzorce

A vzor v permutaci je menší permutace vytvořená z subsekvence některých k hodnoty v permutaci snížením těchto hodnot na rozsah od 1 do k při zachování jejich řádu. Několik důležitých rodin permutací může být charakterizováno konečnou sadou zakázaných vzorů, a to platí i pro permutace riffle shuffle: jsou to přesně ty permutace, které nemají jako vzory 321, 2143 a 2413.^[3] Například jsou tedy podtřídou vexilární permutace, které mají 2143 jako jediný minimální zakázaný vzor.^[6]

Perfektní míchání

A perfektní shuffle je riffle, ve kterém je balíček rozdělen na dva stejně velké pakety a ve kterém se prokládání mezi těmito dvěma pakety striktně střídá. Existují dva typy dokonalého míchání, an v náhodném pořadí a zamíchat, které mohou být důsledně prováděny některými dobře vyškolenými lidmi. Když je balíček opakovaně zamíchán pomocí těchto permutací, zůstává mnohem méně náhodný než u typických míchacích šupin a do původního stavu se vrátí po malém počtu dokonalých zamíchání. Zejména balíček 52 hracích karet bude vrácen do původního pořadí po 52 v náhodných nebo 8 náhodných směnách. Tato skutečnost tvoří základ několika kouzelnických triků.^[7]

Algebra

Riffle shuffles mohou být použity k definování zamíchat algebru. Tohle je Hopfova algebra kde základem je sada slov a produktem je produkt shuffle označený symbolem sha ш, součet všech riffle shuffles dvou slov.

v vnější algebra, klínový produkt a p-forma a q-form lze definovat jako součet za (p,q) - zamíchá.^[2]

Viz také

• Gilbreathovy permutace, permutace vytvořené obrácením jednoho ze dvou balíčků karet před jejich riffováním

Reference