Permutacja tasowania karabinu

W matematyce permutacji i badaniu tasowania kart do gry permutacja tasowania karabinu jest jedną z permutacji zestawu elementów, które można uzyskać przez pojedyncze tasowanie karabinu , w którym posortowana talia ${\ Displaystyle n}$ $\ displaystyle n}$ karty są dzielone na dwa pakiety, a następnie te dwa pakiety są przeplatane (np. poprzez przesuwanie kart pojedynczo od spodu jednego lub drugiego pakietu na górę posortowanej talii). Zaczynając od uporządkowanego zestawu (1 rosnąca sekwencja), matematycznie tasowanie karabinów jest definiowane jako permutacja tego zestawu zawierającego 1 lub 2 rosnące sekwencje. Permutacje z 1 rosnącą sekwencją są permutacjami tożsamościowymi.

Jako szczególny przypadek tego, dla liczb i p $, q ) {$ $}$ z $+ q = n}$ ${\ Displaystyle p}$ ( $\ Displaystyle (p$ $karty$ to karabin, w którym pierwszy pakiet ma $,$ drugi pakiet ma karty.

Wyliczanie kombinatoryczne

Ponieważ -shuffle jest całkowicie zdeterminowane przez sposób odwzorowania jego pierwszych $)$ , liczba ( p , q ) {\ Displaystyle (p, q) za ${$ $)} )}$ -tasuje jest

{\ Displaystyle {\ binom {p + q} {p}}.}

Jednak liczba różnych karabinów nie jest do końca sumą tego wzoru dla wszystkich wyborów $^ {n}}$ ${$ \ displaystyle p $}$ $q$ $displaystyle$ ), ponieważ permutację tożsamości można przedstawić na wiele sposobów jako -shuffle dla różnych wartości i ${$ $\ Displaystyle (p, q)$ ${\ displaystyle q}$ . Zamiast tego liczba różnych permutacji tasowania karabinu w talii $kart$ , dla ${\ Displaystyle n = 1,2,3, \ kropek}$ , wynosi n {\ displaystyle

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

Bardziej ogólnie, wzór na tę liczbę to ${\ displaystyle 2 ^ {n} -n}$ ; na przykład istnieje 4503599627370444 permutacji tasowania karabinu w talii 52 kart.

Liczba permutacji, które są zarówno permutacją tasowania karabinu, jak i permutacją odwrotną tasowania karabinu, wynosi

{\ Displaystyle {\ binom {n + 1} {3}} + 1.}

{\ Displaystyle n = 1,2,3, \ kropki}

jest to

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

a dla ${\ displaystyle n = 52}$ jest dokładnie 23427 odwracalnych tasowań.

Dystrybucja losowa

Gilberta – Shannona – Reedsa opisuje losowy rozkład prawdopodobieństwa tasowania karabinów, który dobrze pasuje do obserwowanych tasowań ludzi. W tym modelu permutacja tożsamości ma prawdopodobieństwo wygenerowania ${\ Displaystyle (n + 1) / 2 ^ {n}} , a wszystkie inne permutacje karabinów mają równe prawdopodobieństwo$ ${\ styl wyświetlania 1/2^{n}}$ bycia generowanym. Opierając się na analizie tego modelu, matematycy zalecili, aby talia 52 kart miała siedem karabinów w celu dokładnego losowania.

Wzory permutacji

Wzorzec w permutacji to mniejsza permutacja utworzona z podsekwencji niektórych $w$ permutacji poprzez zmniejszenie tych wartości do zakresu od 1 do k $\ displaystyle k}$ przy zachowaniu ich kolejności. Kilka ważnych rodzin permutacji można scharakteryzować skończonym zbiorem zabronionych wzorców, i dotyczy to również permutacji tasowania karabinu: są to dokładnie permutacje, które nie mają 321, 2143 i 2413 jako wzorców. Tak więc, na przykład, są podklasą permutacji vexillary , które mają 2143 jako jedyny minimalny zabroniony wzorzec.

Idealne przetasowania

Idealne przetasowanie to karabin, w którym talia jest podzielona na dwa pakiety o równej wielkości i w której przeplatanie między tymi dwoma pakietami ściśle się zmienia. Istnieją dwa rodzaje perfekcyjnego tasowania, in shuffle i out shuffle , z których oba mogą być konsekwentnie wykonywane przez niektóre dobrze wyszkolone osoby. Kiedy talia jest wielokrotnie tasowana przy użyciu tych permutacji, pozostaje znacznie mniej losowa niż w przypadku typowych tasowań karabinowych i powróci do stanu początkowego już po niewielkiej liczbie doskonałych tasowań. W szczególności talia 52 kart do gry zostanie przywrócona do pierwotnej kolejności po 52 przetasowaniach lub 8 przetasowaniach. Fakt ten stanowi podstawę kilku magicznych sztuczek.

Algebra

Tasowanie karabinów może być użyte do zdefiniowania algebry tasowania . Jest to algebra Hopfa , w której podstawą jest zbiór słów, a produktem jest iloczyn tasowania oznaczony symbolem sha ш, suma wszystkich tasowań dwóch słów.

W algebrze zewnętrznej iloczyn klina $-formy$ i formy - można zdefiniować $(p, q)}$ sumę po $Displaystyle$ -shuffles .

Zobacz też

Permutacje Gilbreath , permutacje utworzone przez odwrócenie jednej z dwóch paczek kart przed ich przemieszaniem