en>Monkbot: /* Bibliography */Fix CS1 deprecated date parameter errors

2014-01-24T07:37:59Z

Bibliography: Fix CS1 deprecated date parameter errors

New page

In the mathematics of [[permutation]]s and the study of [[shuffling]] [[playing card]]s, a '''riffle shuffle permutation''' is one of the [[permutation]]s of a set of ''n'' items that can be obtained by a single [[shuffling|riffle shuffle]], in which a sorted deck of ''n'' cards is cut into two packets and then the two packets are interleaved (e.g. by moving cards one at a time from the bottom of one or the other of the packets to the top of the sorted deck).

As a special case of this, a (''p'',''q'')-'''shuffle''', for numbers ''p'' and ''q'' with ''p'' + ''q'' = ''n'', is a riffle in which the first packet has ''p'' cards and the second packet has ''q'' cards.<ref name=Weibel>Weibel, Charles (1994). ''An Introduction to Homological Algebra'', p. 181. Cambridge University Press, Cambridge.</ref>

==Combinatorial enumeration==
Since a (''p'',''q'')-shuffle is completely determined by how its first ''p'' elements are mapped, the number of (''p'',''q'')-shuffles is
:<math>\binom{p+q}{p}.</math>
The [[wedge product]] of a ''p''-form and a ''q''-form can be defined as a sum over (''p'',''q'')-shuffles.<ref name=Weibel/>

However, the number of distinct riffles is not quite the sum of this formula over all choices of ''p'' and ''q'' adding to ''n'' (which would be ''2''''n''), because the [[identity permutation]] can be represented in multiple ways as a (''p'',''q'')-shuffle for different values of ''p'' and ''q''.
Instead, the number of distinct riffle shuffle permutations of a deck of ''n'' cards, for ''n'' = 1, 2, 3, ..., is
:1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ... {{OEIS|id=A000325}}
More generally, the formula for this number is 2''n'' − ''n''; for instance, there are 4503599627370444 riffle shuffle permutations of a 52-card deck.

The number of permutations that are both a riffle shuffle permutation and the inverse permutation of a riffle shuffle is<ref name="a99">{{citation
| last = Atkinson | first = M. D.
| doi = 10.1016/S0012-365X(98)00162-9
| issue = 1-3
| journal = Discrete Mathematics
| mr = 1663866
| pages = 27–38
| title = Restricted permutations
| volume = 195
| year = 1999}}.</ref>
:<math>\binom{n+1}{3}+1.</math>
For ''n'' = 1, 2, 3, ..., this is
:1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ... {{OEIS|id=A050407}}
and for ''n'' = 52 there are exactly 23427 invertible shuffles.

==Random distribution==
The [[Gilbert–Shannon–Reeds model]] describes a random [[probability distribution]] on riffle shuffles that is a good match for observed human shuffles.<ref>{{citation
| last = Diaconis | first = Persi | authorlink = Persi Diaconis
| isbn = 0-940600-14-5
| location = Hayward, CA
| mr = 964069
| publisher = Institute of Mathematical Statistics
| series = Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11
| title = Group representations in probability and statistics
| year = 1988}}.</ref> In this model, the [[identity permutation]] has probability (''n'' + 1)/2''n'' of being generated, and all other riffle permutations have equal probability 1/2''n'' of being generated. Based on their analysis of this model, mathematicians have recommended that a deck of 52 cards be given seven riffles in order to thoroughly randomize it.<ref>{{citation|title=In Shuffling Cards, 7 Is Winning Number|first=Gina|last=Kolata|authorlink=Gina Kolata|journal=[[New York Times]]|url=http://www.nytimes.com/1990/01/09/science/in-shuffling-cards-7-is-winning-number.html|date=January 9, 1990}}.</ref>

==Permutation patterns==
A [[permutation pattern|pattern]] in a permutation is a smaller permutation formed from a subsequence of some ''k'' values in the permutation by reducing these values to the range from 1 to ''k'' while preserving their order. Several important families of permutations can be characterized by a finite set of forbidden patterns, and this is true also of the riffle shuffle permutations: they are exactly the permutations that do not have 321, 2143, and 2413 as patterns.<ref name="a99"/> Thus, for instance, they are a subclass of the [[vexillary permutation]]s, which have 2143 as their only minimal forbidden pattern.<ref>{{citation|title=Permutation patterns, continued fractions, and a group determined by an ordered set|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.2001&rep=rep1&type=pdf|first=Anders|last=Claesson|series=Ph.D. thesis|publisher=Department of Mathematics, Chalmers University of Technology|year=2004}}.</ref>

==Perfect shuffles==
A ''perfect shuffle'' is a riffle in which the deck is split into two equal-sized packets, and in which the interleaving between these two packets strictly alternates between the two. There are two types of perfect shuffle, an [[in shuffle]] and an [[out shuffle]], both of which can be performed consistently by some well-trained people. When a deck is repeatedly shuffled using these permutations, it remains much less random than with typical riffle shuffles, and it will return to its initial state after only a small number of perfect shuffles. In particular, a deck of 52 playing cards will be returned to its original ordering after 52 in shuffles or 8 out shuffles. This fact forms the basis of several magic tricks.<ref>{{citation
| last1 = Diaconis | first1 = Persi | author1-link = Persi Diaconis
| last2 = Graham | first2 = R. L. | author2-link = Ronald Graham
| last3 = Kantor | first3 = William M.
| doi = 10.1016/0196-8858(83)90009-X
| issue = 2
| journal = Advances in Applied Mathematics
| mr = 700845
| pages = 175–196
| title = The mathematics of perfect shuffles
| volume = 4
| year = 1983}}.</ref>

==See also==
*[[Gilbreath shuffle|Gilbreath permutations]], the permutations formed by reversing one of the two packets of cards before riffling them

==References==
{{reflist}}

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

Kuwahara filter - Revision history

en>Monkbot: /* Bibliography */Fix CS1 deprecated date parameter errors