Перестановка с перетасовкой

В математике перестановок и изучении тасования игральных карт перестановка с помощью рифленой перестановки является одной из перестановок набора игральных карт. $n$ предметы, которые можно получить путем одной перетасовки , в которой отсортированная колода $n$ Карты разрезаются на два пакета, а затем эти два пакета чередуются (например, путем перемещения карт по одной от нижней части одного или другого пакета к верху отсортированной колоды). Начиная с упорядоченного набора (1 восходящая последовательность), математически тасование рифлей определяется как перестановка в этом наборе, содержащая 1 или 2 восходящие последовательности. Перестановки с 1 восходящей последовательностью являются тождественными перестановками.

В качестве частного случая этого $(p,q)$-перетасовать , для чисел $p$ и $q$ с $p+q=n$, представляет собой рифлю, в которой первый пакет имеет $p$ карты, а второй пакет имеет $q$ карты.

Комбинаторное перечисление

Поскольку $(p,q)$-shuffle полностью определяется тем, как он впервые $p$ элементы сопоставляются, количество $(p,q)$-тасовка - это

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

Однако количество различных желобков не является полной суммой этой формулы для всех вариантов выбора. $p$ и $q$ добавление к $n$ (что было бы $2^{n}$), поскольку тождественную перестановку можно представить несколькими способами в виде $(p,q)$-перемешать для разных значений $p$ и $q$.Вместо этого количество различных перестановок колоды тасовок $n$ карты, для $n=1,2,3,\dots$, является

1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ... (последовательность A000325 в OEIS )

В более общем смысле формула этого числа такова: $2^{n}-n$; например, существует 4503599627370444 перестановок колоды из 52 карт.

Число перестановок, которые одновременно являются перестановкой тасования ружей и обратной перестановкой тасовки ружьями, равно

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

Для $n=1,2,3,\dots$, Это

1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ... (последовательность A050407 в OEIS )

и для $n=52$ имеется ровно 23427 обратимых тасовок.

распределение

Модель Гилберта-Шеннона-Ридса описывает случайное распределение вероятностей при перетасовке, которое хорошо соответствует наблюдаемым перетасовкам людей. В этой модели тождественная перестановка имеет вероятность $(n+1)/2^{n}$ быть сгенерированы, и все остальные перестановки винтовок имеют равную вероятность $1/2^{n}$ быть сгенерированным. Основываясь на анализе этой модели, математики рекомендовали дать колоде из 52 карт семь карточек, чтобы тщательно рандомизировать ее.

Шаблоны перестановок

Образец в перестановке — это меньшая перестановка , образованная из подпоследовательности некоторой $k$ значений в перестановке, сводя эти значения к диапазону от 1 до $k$ сохраняя при этом свой порядок. Несколько важных семейств перестановок могут быть охарактеризованы конечным набором запрещенных шаблонов, и это верно также и для перестановок с перетасовкой: это именно те перестановки, которые не имеют 321, 2143 и 2413 в качестве шаблонов. Так, например, они являются подклассом вексиллярных перестановок , единственным минимальным запрещенным шаблоном которых является 2143.

Идеальные тасовки

Основная статья: Перетасовка Фаро

Идеальная тасовка — это розыгрыш, в котором колода разделена на две пачки одинакового размера и в которой чередование этих двух пачек строго чередуется между ними. Существует два типа идеального тасования: тасование на входе и тасование на выходе , оба из которых могут последовательно выполняться хорошо тренированными людьми. Когда колоду неоднократно тасуют с использованием этих перестановок, она остается гораздо менее случайной, чем при типичных перетасовках, и возвращается в исходное состояние лишь после небольшого количества идеальных перетасовок. В частности, колода из 52 игральных карт будет возвращена в исходный порядок после 52 перетасовок или 8 перетасовок. Этот факт лежит в основе нескольких фокусов.

Алгебра

Риффл-тасование может использоваться для определения алгебры тасования . Это алгебра Хопфа , в которой базисом является набор слов:и продукт представляет собой продукт тасования, обозначаемый символом ша ш, суммой всех тасований двух слов.

Во внешней алгебре клиновое произведение $p$-форма и $q$-форма может быть определена как сумма по $(p,q)$- шаркает.

См. также

• Перестановки Гилбрета — перестановки, образованные путем переворачивания одной из двух пачек карт перед их перелистыванием.