В математике перестановок и изучении перетасовки игральных карт , желобок перетасовка перестановки является одним из перестановок множества из п элементов , которые могут быть получены с помощью одной винтовки перетасовки , в котором отсортированная колода п карт поделена на две пакеты, а затем два пакета чередуются (например, перемещая карты по одной из нижней части одного или другого пакета в верхнюю часть отсортированной колоды). Начиная с упорядоченного набора (1 восходящая последовательность), математически перестановка определяется как перестановка в этом наборе, содержащем 1 или 2 восходящие последовательности. [1] Перестановки с 1 восходящей последовательностью являются идентичными перестановками.
В качестве особого случая этого тасования ( p , q ) - тасование для чисел p и q с p + q = n - это тасование, в котором в первом пакете p карт, а во втором пакете q карт. [2]
Комбинаторное перечисление
Поскольку ( p , q ) -перестановка полностью определяется тем, как отображаются ее первые p элементов, количество ( p , q ) -перестановок равно
Однако количество различных перекладин - это не совсем сумма этой формулы по всем вариантам p и q, добавляемым к n (что было бы 2 n ), потому что тождественная перестановка может быть представлена несколькими способами как a ( p , q ) -перестановка для разных значений p и q . Вместо этого количество различных перестановок тасования колоды из n карт для n = 1, 2, 3, ... равно
В более общем случае формула для этого числа: 2 n - n ; например, существует 4503599627370444 перестановок тасования колоды из 52 карт.
Количество перестановок, которые являются как перестановкой случайного воспроизведения, так и обратной перестановкой случайного перемешивания, равно [3]
Для n = 1, 2, 3, ... это
а для n = 52 имеется ровно 23427 обратимых тасовок.
Случайное распределение
Модель Гилберта – Шеннона – Ридса описывает случайное распределение вероятностей при случайном перемешивании, которое хорошо согласуется с наблюдаемыми перемещениями людей. [4] В этой модели тождественная перестановка сгенерирована с вероятностью ( n + 1) / 2 n , а все другие перестановки с перестановкой имеют равную вероятность 1/2 n сгенерирования. Основываясь на своем анализе этой модели, математики рекомендовали дать колоде из 52 карт семь риффов, чтобы тщательно ее рандомизировать. [5]
Шаблоны перестановок
Узор в перестановке является меньшим перестановок формируется из подпоследовательности некоторых K значений в перестановке путем уменьшения этих значений в диапазоне от 1 до K , сохраняя их порядок. Несколько важных семейств перестановок можно охарактеризовать конечным набором запрещенных паттернов, и это верно также для перестановок случайного тасования: это как раз те перестановки, которые не имеют 321, 2143 и 2413 в качестве паттернов. [3] Таким образом, например, они являются подклассом вексиллярных перестановок , единственной минимально запрещенной структурой которых является 2143. [6]
Идеальное перемешивание
Совершенная перетасовка является канавкой , в которой палуба разделена на две равных по размеру пакетов, и в котором чередование между этими двумя пакетами строго чередуется между ними. Существует два типа идеального перемешивания: входящее и исходящее , и оба из них могут последовательно выполняться некоторыми хорошо обученными людьми. Когда колода неоднократно перетасовывается с использованием этих перестановок, она остается гораздо менее случайной, чем при обычном перемешивании колоды, и она вернется в исходное состояние только после небольшого количества идеальных перемешиваний. В частности, колода из 52 игральных карт будет возвращена в исходный порядок после перетасовки 52 или 8 исходных. Этот факт лежит в основе нескольких фокусов. [7]
Алгебра
Перемешивание может использоваться для определения алгебры перемешивания . Это алгебра Хопфа, в которой основа - набор слов, а произведение - произведение перемешивания, обозначенное символом sha ш, суммой всех перемешанных слов двух слов.
Во внешней алгебре произведение p-формы и q-формы может быть определено как сумма по ( p , q ) -разбавкам. [2]
Смотрите также
- Перестановки Gilbreath, перестановки , сформированные путем переворачивания одного из двух пакетов карт перед их разыгрыванием
Рекомендации
- ^ Олдос, D .; Диаконис, П. «Перетасовка карт и время остановки» (PDF) . Цитировать журнал требует
|journal=
( помощь ) - ^ a b Вейбель, Чарльз (1994). Введение в гомологическую алгебру , с. 181. Cambridge University Press, Кембридж.
- ^ а б Аткинсон, Мэриленд (1999), «Ограниченные перестановки», Дискретная математика , 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), Шаблоны перестановок, непрерывные дроби и группа, определяемая упорядоченным набором , Ph.D. кандидатская диссертация, факультет математики, Технологический университет Чалмерса, CiteSeerX 10.1.1.103.2001.
- ^ Диаконис, Перси ; Graham, RL ; Кантор, William M. (1983), "Математика совершенных перетасовки", Прогресс в области прикладной математики , 4 (2): 175-196, CiteSeerX 10.1.1.77.7769 , DOI : 10,1016 / 0196-8858 (83) 90009- X , Руководство администратора 0700845.