Рифл-тасование: перестановки и математика

Упорядочение, полученное в результате одной тасовки

В математике перестановок и при изучении тасования игральных карт перестановка при рифл-тасовании — это перестановка упорядоченного набора из n элементов, которая может быть получена в результате одного рифл-тасования. При этом отсортированная колода из n карт (в порядке возрастания сверху вниз) разрезается на две пачки, а затем эти пачки перемешиваются (например, путём перемещения карт по одной с дна одной или другой пачки на вершину отсортированной колоды). Частным случаем является (p,q)-тасование для чисел p и q, где p+q=n, при котором первая пачка содержит p карт, а вторая — q карт.

Рассматривая перестановку как биективную функцию π из множества {1,2,…,n} в себя, рифл-тасование определяется как содержащее только 1 или 2 максимальных возрастающих последовательности. Это означает, что {1,2,…,n} можно разложить на два непересекающихся подмножества {i₁<⋯

π(i₁)<π(i₂)<⋯<π(iₚ) и π(j₁)<π(j₂)<⋯<π(jᵩ)

Перестановка с единственной максимальной возрастающей последовательностью — это тождественная перестановка.

Обратная перестановка τ=π⁻¹ рифл-тасования называется перестановкой Грассманна и определяется условиями:

τ(1)<…<τ(p) и τ(p+1)<…<τ(p+q)

с одним спуском τ(p)>τ(p+1), или без спусков, если τ — тождественная перестановка. В исчислении Шуберта такие перестановки индексируют многообразия Шуберта в грассманиане.

Перестановка π, которая одновременно является рифл-тасованием и перестановкой Грассманна (то есть и π, и её обратная являются перестановками Грассманна, или эквивалентно, обе являются рифл-тасованиями), называется биграссманновой или обратимой тасовкой.

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

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

C(p+q, p)

Однако количество различных рифл-тасований не совпадает с суммой этой формулы по всем вариантам p и q, дающим в сумме n (что было бы 2ⁿ), поскольку тождественная перестановка может быть представлена несколькими способами как (p,q)-тасование при различных значениях p и q.

Вместо этого количество различных перестановок при рифл-тасовании колоды из n карт для n=1,2,3,… составляет:

1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, …

В общем случае формула для этого числа имеет вид 2ⁿ−n; например, для стандартной колоды из 52 карт существует 4503599627370444 перестановок при рифл-тасовании.

Количество биграссманновых перестановок равно C(n+1, 3)+1.

Для n=1,2,3,… это составляет:

1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, …

а для n=52 существует ровно 23427 биграссманновых тасований.

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

Модель Гилберта–Шеннона–Рида описывает случайное распределение вероятностей на рифл-тасованиях, которое хорошо соответствует наблюдаемому человеческому тасованию. В этой модели тождественная перестановка имеет вероятность (n+1)/2ⁿ быть сгенерированной, а все остальные рифл-перестановки имеют равную вероятность 1/2ⁿ. На основе анализа этой модели математики рекомендуют тасовать колоду из 52 карт семь раз для её полной рандомизации.

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

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

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

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

Алгебра

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

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