en>Anne Bauval: Undid revision 552851491 by Anne Bauval (talk) Sorry, misuse of template : what I meant is that it is a quasi-orphan

2013-04-30T07:44:18Z

Undid revision 552851491 by Anne Bauval (talk) Sorry, misuse of template : what I meant is that it is a quasi-orphan

New page

A '''Gilbreath shuffle''' is a way to [[shuffle]] a deck of cards, named after mathematician [[Norman L. Gilbreath]] (also known for [[Gilbreath's conjecture]]).
'''Gilbreath's principle''' describes the properties of a deck that are preserved by this type of shuffle, and a '''Gilbreath permutation''' is a [[permutation]] that can be formed by a Gilbreath shuffle.<ref name="dg">{{citation|title=Magical Mathematics: the mathematical ideas that animate great magic tricks|first1=Persi|last1=Diaconis|author1-link=Persi Diaconis|first2=Ron|last2=Graham|author2-link=Ronald Graham (mathematician)|publisher=Princeton University Press|year=2012|chapter=Chapter 5: From the Gilbreath Principle to the Mandelbrot Set|pages=61–83}}.</ref>

==Description==
A Gilbreath shuffle consists of the following two steps:<ref name="dg"/>
*Deal off any number of the cards from the top of the deck onto a new pile of cards.
*Riffle the new pile with the remainder of the deck.
It differs from the more commonly used procedure of cutting a deck into two piles and then riffling the piles, in that the first step of dealing off cards reverses the order of the cards in the new pile, whereas cutting the deck would preserve this order.

==Gilbreath's principle==
Although seemingly highly random, Gilbreath shuffles preserve many properties of the initial deck. For instance, if the initial deck of cards alternates between black and red cards, then after a single Gilbreath shuffle the deck will still have the property that, if it is grouped into consecutive pairs of cards, each pair will have one black card and one red card. Similarly, if a deck of cards is initially arranged so that every card has the same suit as the card four positions earlier, it is given a Gilbreath shuffle, and the resulting deck is grouped into consecutive sets of four cards, then each set will have one card of each suit. This phenomenon is known as '''Gilbreath's principle''' and is the basis for several [[Card manipulation|card tricks]].<ref name="dg"/>

==Gilbreath permutations==
Mathematically, Gilbreath shuffles can be described by '''Gilbreath permutations''', [[permutation]]s of the numbers from 1 to ''n'' that can be obtained by a Gilbreath shuffle with a deck of cards labeled with these numbers in order. Gilbreath permutations can be characterized by the property that every [[Prefix (computer science)|prefix]] contains a consecutive set of numbers.<ref name="dg"/> For instance, the permutation (5,6,4,7,8,3,2,9,1,10) is a Gilbreath permutation for ''n'' = 10 that can be obtained by dealing off the first four or five cards and riffling them with the rest. Each of its prefixes (5), (5,6), (5,6,4), (5,6,4,7), etc. contain a set of numbers that (when sorted) form a consecutive subsequence of the numbers from 1 to 10. Equivalently, in terms of [[permutation pattern]]s, the Gilbreath permutations are the permutations that avoid the two patterns 132 and 312.<ref name="v">{{citation
| last = Vella | first = Antoine
| issue = 2
| journal = Electronic Journal of Combinatorics
| mr = 2028287
| page = R18
| title = Pattern avoidance in permutations: linear and cyclic orders
| url = http://www.combinatorics.org/Volume_9/Abstracts/v9i2r18.html
| volume = 9
| year = 2002}}. See in particular Proposition 3.3.</ref>

A Gilbreath shuffle may be uniquely determined by specifying which of the positions in the resulting shuffled deck are occupied by cards that were dealt off into the second pile, and which positions are occupied by cards that were not dealt off. Therefore, there are 2<sup>''n''</sup> possible ways of performing a Gilbreath shuffle on a deck of ''n'' cards. However, each Gilbreath permutation may be obtained from two different Gilbreath shuffles (the first position of the permutation may have come from either of the two piles) so there are 2<sup>''n'' − 1</sup> distinct Gilbreath permutations.<ref name="dg"/><ref>{{harvtxt|Vella|2002}} credits this result on the number of Gilbreath permutations to {{citation
| last1 = Simion | first1 = Rodica | author1-link = Rodica Simion
| last2 = Schmidt | first2 = Frank W.
| issue = 4
| journal = European Journal of Combinatorics
| mr = 829358
| pages = 383–406
| title = Restricted permutations
| volume = 6
| year = 1985}}.</ref>

The [[cyclic permutation|cyclic]] Gilbreath permutations of order ''n'' are in one-to-one correspondence with the [[real number]]s ''c'' for which the iteration <math>x\mapsto x^2+c</math> (starting from <math>x=0</math>) underlying the [[Mandelbrot set]] is periodic with period ''n''. In this correspondence, the permutation that corresponds to a given value ''c'' describes the numerical sorted order of the iterates for ''c''.<ref name="dg"/> The number of cyclic Gilbreath permutations (and therefore also the number of real periodic points of the Mandelbrot set), for ''n'' = 1, 2, 3, ..., is given by the [[integer sequence]]
:1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, ... {{OEIS|id=A000048}}.

==References==
{{reflist}}

[[Category:Card shuffling]]
[[Category:Permutation patterns]]

Noncommutative torus - Revision history

en>Anne Bauval: Undid revision 552851491 by Anne Bauval (talk) Sorry, misuse of template : what I meant is that it is a quasi-orphan