Перестановка Riffle shuffle

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

Частным случаем этого является тасование , для чисел и с , представляющее собой перетасовку, в которой первая пачка содержит карты, а вторая пачка содержит карты. ^[2] $(п,д)$ $p$ $д$ $p+q=n$ $p$ $д$

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

Поскольку -перетасовка полностью определяется тем, как отображаются ее первые элементы, количество -перетасовок равно $(п,д)$ $p$ $(п,д)$ ${\binom {p+q}{p}}.$

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

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

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

Число перестановок, которые являются как перестановкой тасования с прокруткой, так и обратной перестановкой тасования с прокруткой, равно ^[3]. Для это ${\binom {n+1}{3}}+1.$ $n=1,2,3,\точки$

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

и существует ровно 23427 обратимых перетасовок. $n=52$

Случайное распределение

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

Модели перестановок

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

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

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

Алгебра

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

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

Смотрите также

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

Ссылки

^ Олдос, Дэвид ; Диаконис, Перси (1986), «Перетасовка карт и остановка времени» (PDF) , The American Mathematical Monthly , 93 (5): 333–348, doi :10.2307/2323590, JSTOR 2323590, MR 0841111
^ ab Weibel, Charles (1994). Введение в гомологическую алгебру , стр. 181. Cambridge University Press, Кембридж.
^ ab Atkinson, MD (1999), «Ограниченные перестановки», Discrete Mathematics , 195 (1–3): 27–38, doi : 10.1016/S0012-365X(98)00162-9 , MR 1663866.
^ Диаконис, Перси (1988), Представления групп в теории вероятностей и статистике , Конспект лекций Института математической статистики — Серия монографий, 11, Хейворд, Калифорния: Институт математической статистики, ISBN 0-940600-14-5, МР 0964069.
↑ Колата, Джина (9 января 1990 г.), «При перетасовке карт выигрышным числом является 7», New York Times.
^ Клаэссон, Андерс (2004), Модели перестановок, непрерывные дроби и группа, определяемая упорядоченным множеством , докторская диссертация, кафедра математики, Технологический университет Чалмерса, CiteSeerX 10.1.1.103.2001 .
^ Диаконис, Перси ; Грэм, РЛ ; Кантор, Уильям М. (1983), «Математика идеальных тасовок», « Достижения в области прикладной математики » , 4 (2): 175–196, CiteSeerX 10.1.1.77.7769 , doi : 10.1016/0196-8858(83)90009- Х, МР 0700845 .