Гилбрит перетасовка

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

Описание

Перетасовка Гилбрета состоит из следующих двух шагов: ^[1]

Раздайте любое количество карт сверху колоды, чтобы сформировать вторую стопку карт.
Перемешайте новую стопку с остальной частью колоды.

Он отличается от более часто используемой процедуры разрезания колоды на две стопки и последующего перелистывания стопок тем, что на первом этапе раздачи карт меняется порядок карт в новой стопке, тогда как разрезание колоды сохраняет этот порядок.

Принцип Гилбрета

Несмотря на кажущуюся случайность, тасование Гилбрита сохраняет многие свойства исходной колоды. Например, если в исходной колоде карт чередуются черные и красные карты, то после одного перетасовывания Гилбрета колода по-прежнему будет обладать свойством: если она сгруппирована в последовательные пары карт, в каждой паре будет одна черная карта и одна красная карточка. Аналогично, если тасование Гилбрета используется в колоде карт, где каждая карта имеет ту же масть, что и карта четырьмя позициями ранее, и полученная колода сгруппирована в последовательные наборы из четырех карт, тогда каждый набор будет содержать по одной карте каждой масти. . Это явление известно как принцип Гилбрита и лежит в основе нескольких карточных фокусов . ^[1]

Перестановки Гилбрета

Математически тасование Гилбрита можно описать перестановками Гилбрита , перестановками чисел от 1 до n , которые можно получить путем перетасовки Гилбрита с колодой карт, помеченных этими числами по порядку. Перестановки Гилбрета можно охарактеризовать тем свойством, что каждый префикс содержит последовательный набор чисел. ^[1] Например, перестановка (5,6,4,7,8,3,2,9,1,10) — это перестановка Гилбрита для n = 10, которую можно получить, раздав первые четыре или пять карт и перетасовав их. с остальными. Каждый из его префиксов (5), (5,6), (5,6,4), (5,6,4,7) и т. д. содержит набор чисел, которые (при сортировке) образуют последовательную подпоследовательность числа от 1 до 10. Аналогично, с точки зрения шаблонов перестановок , перестановки Гилбрита — это перестановки, которые избегают двух шаблонов 132 и 312. ^[2]

Тасование Гилбрита можно однозначно определить, указав, какие позиции в полученной перетасованной колоде заняты картами, которые были сданы во вторую стопку, а какие позиции заняты картами, которые не были сданы. Поэтому существуют $2^{n}$ возможные способы выполнения тасования Гилбрита на колоде $n$ карты. Однако каждая перестановка Гилбрита может быть получена в результате двух разных перетасовок Гилбрита, поскольку первая позиция перестановки могла принадлежать любой из двух стопок. Поэтому существуют $2^{n-1}$ различные перестановки Гилбрета. ^[1]^[3]

Циклические перестановки порядка Гилбрита $n$ находятся во взаимно однозначном соответствии с действительными числами $c$ для чего итерация $x\mapsto x^{2}+c$ (начиная с $x=0$ ), лежащий в основе множества Мандельброта, является периодическим с периодом $n$ . В этой переписке перестановка, соответствующая данному значению $c$ описывает числовой порядок итераций для $c$ . ^[1] Число циклических перестановок Гилбрита (а, следовательно, и количество действительных периодических точек множества Мандельброта) для $n=1,2,3,\dots$ , задаётся целочисленной последовательностью

1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, ... (последовательность A000048 в OEIS ).

Окончательный принцип Гилбрита

{\begin{matrix}1\\2\\3\\4\\5\\6\\7\\8\\9\\10\end{matrix}}\to {\begin{matrix}5\\6\\7\\8\\9\\10\end{matrix}}{\begin{matrix}4\\3\\2\\1\end{matrix}}\to {\begin{matrix}4\\5\\6\\3\\7\\2\\8\\9\\1\\10\end{matrix}}

Вот пример, иллюстрирующий теорему. Для колоды из десяти карт мы можем разложить четыре карты в небольшую стопку на столе (одну за другой), а затем перетасовать их, чтобы привести к расположению π, указанному выше.

Теорема, называемая «окончательным принципом Гилбрита», утверждает, что для перестановки $\pi$ из $\{1,2,3,\dots ,n\}$ , следующие четыре свойства эквивалентны: ^[1]

$\pi$ является перестановкой Гилбрета.
Для каждого $j$ , вершина $j$ карты $\pi (1),\dots \pi (j)$ различны по модулю $j$ .
Для каждого $j$ и $k$ с $kj\leq n$ , $j$ карты $\pi {\bigl (}(k-1)j+1{\bigr )},\pi {\bigl (}k-1)j+2{\bigr )},\dots ,\pi (kj)$ различны по модулю $j$ .
Для каждого $j$ , вершина $j$ карты идут подряд $1,2,\dots ,n$ .

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Диаконис, Персия ; Грэм, Рон (2012), «Глава 5: От принципа Гилбрита к множеству Мандельброта» (PDF) , Магическая математика: математические идеи, которые вдохновляют великие фокусы , Princeton University Press, стр. 61–83 .
^ Велла, Антуан (2002), «Избегание шаблонов в перестановках: линейные и циклические порядки» , Электронный журнал комбинаторики , 9 (2): R18, doi : 10.37236/1690 , MR 2028287 . См., в частности, предложение 3.3.
^ Велла (2002) приписывает этот результат количеству перестановок Гилбрета Симион, Родика ; Шмидт, Фрэнк В. (1985), «Ограниченные перестановки», European Journal of Combinatorics , 6 (4): 383–406, doi : 10.1016/s0195-6698(85)80052-4 , MR 0829358 .

[dg-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Диаконис, Персия ; Грэм, Рон (2012), «Глава 5: От принципа Гилбрита к множеству Мандельброта» (PDF) , Магическая математика: математические идеи, которые вдохновляют великие фокусы , Princeton University Press, стр. 61–83 .

[v-2] Велла, Антуан (2002), «Избегание шаблонов в перестановках: линейные и циклические порядки» , Электронный журнал комбинаторики , 9 (2): R18, doi : 10.37236/1690 , MR 2028287 . См., в частности, предложение 3.3.

[3] Велла (2002) приписывает этот результат количеству перестановок Гилбрета Симион, Родика ; Шмидт, Фрэнк В. (1985), «Ограниченные перестановки», European Journal of Combinatorics , 6 (4): 383–406, doi : 10.1016/s0195-6698(85)80052-4 , MR 0829358 .

[1]

[2]

[3]