Ver el código de «(p,q) barajados»

En [[combinatoria]] y en el estudio del [[barajado]] de [[naipes]], una '''permutación de barajado rápido''' (''riffle shuffle'' en inglés) es una de las [[permutación|permutaciones]] de un conjunto de ''n'' elementos que se pueden obtener separándolos en dos montones y luego intercalándolos (por ejemplo, moviendo las cartas una a una desde la parte inferior de uno u otro de los dos montones a la parte superior de la baraja hasta mezclarla). Comenzando con un conjunto ordenado (una secuencia ascendente), matemáticamente una mezcla rápida se define como una permutación de este conjunto, que contiene la totalidad de las cartas ordenadas en una o en dos secuencias ascendentes.<ref>{{Cite journal|last=Aldous|first=D.|last2=Diaconis|first2=P.|title=Shuffling Cards and Stopping Times|url=https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.pdf}}</ref> Las permutaciones con una sola secuencia ascendente son las permutaciones identidad (es decir, con la baraja totalmente ordenada).

Como un caso especial, un (''p'', ''q'')-'''barajado''', para los números ''p'' y ''q'' con ''p''&nbsp;+&nbsp;''q''&nbsp;=&nbsp;''n'', es un barajado en el que el primer montón del corte tiene ''p'' cartas y el segundo tiene ''q'' cartas.<ref name=Weibel>Weibel, Charles (1994). ''An Introduction to Homological Algebra'', p. 181. Cambridge University Press, Cambridge.</ref>

Analíticamente, los barajados rápidos son las [[permutación|permutaciones]] del conjunto ''σ''{{nowrap|{1, 2, ..., ''p'' + ''q''}}}, tales que {{nowrap|''σ''(1) < ''σ''(2) < ... < ''σ''(''p'')}} y {{nowrap|''σ''(''p'' + 1) < ''σ''(''p'' + 2) < ... < ''σ''(''p'' + ''q'')}}.

==Procedimiento de barajado==
{|class="wikitable col1cen floatright" style="font-size:70%;"
|+Barajado rápido (n=5)
|-
!Caso!!p!!q!!⇒!!1ª!!2ª!!3ª!!4ª!!5ª!!TOTAL
|-
|1 ||bgcolor="yellow"|0||5||⇒|| 1|| 2|| 3|| 4|| 5||bgcolor="lightgreen"|12345
|-
|2 ||bgcolor="yellow"|1||4||⇒||bgcolor="yellow"|1|| 2|| 3|| 4|| 5||bgcolor="pink"|12345
|-
|3 ||bgcolor="yellow"|1||4||⇒|| 2||bgcolor="yellow"|1|| 3|| 4|| 5||21345
|-
|4 ||bgcolor="yellow"|1||4||⇒|| 2|| 3||bgcolor="yellow"|1|| 4|| 5||23145
|-
|5 ||bgcolor="yellow"|1||4||⇒|| 2|| 3|| 4||bgcolor="yellow"|1|| 5||23415
|-
|6 ||bgcolor="yellow"|1||4||⇒|| 2|| 3|| 4|| 5||bgcolor="yellow"|1||23451
|-
|7 ||bgcolor="yellow"|2||3||⇒||bgcolor="yellow"|1||bgcolor="yellow"|2|| 3|| 4|| 5||bgcolor="pink"|12345
|-
|8 ||bgcolor="yellow"|2||3||⇒|| 3||bgcolor="yellow"|1||bgcolor="yellow"|2|| 4|| 5||31245
|-
|9 ||bgcolor="yellow"|2||3||⇒|| 3|| 4||bgcolor="yellow"|1||bgcolor="yellow"|2|| 5||34125
|-
|10||bgcolor="yellow"|2||3||⇒|| 3|| 4|| 5||bgcolor="yellow"|1||bgcolor="yellow"|2||34512
|-
|11||bgcolor="yellow"|2||3||⇒||bgcolor="yellow"|1|| 3||bgcolor="yellow"|2|| 4|| 5||13245
|-
|12||bgcolor="yellow"|2||3||⇒|| 3||bgcolor="yellow"|1|| 4||bgcolor="yellow"|2|| 5||31425
|-
|13||bgcolor="yellow"|2||3||⇒|| 3|| 4||bgcolor="yellow"|1|| 5||bgcolor="yellow"|2||34152
|-
|14||bgcolor="yellow"|2||3||⇒||bgcolor="yellow"|1|| 3|| 4||bgcolor="yellow"|2|| 5||13425
|-
|15||bgcolor="yellow"|2||3||⇒|| 3||bgcolor="yellow"|1|| 4|| 5||bgcolor="yellow"|2||31452
|-
|16||bgcolor="yellow"|2||3||⇒||bgcolor="yellow"|1|| 3|| 4|| 5||bgcolor="yellow"|2||13452
|-
|17||bgcolor="yellow"|3||2||⇒||bgcolor="yellow"|1||bgcolor="yellow"|2||bgcolor="yellow"|3|| 4|| 5||bgcolor="pink"|12345
|-
|18||bgcolor="yellow"|3||2||⇒|| 4||bgcolor="yellow"|1||bgcolor="yellow"|2||bgcolor="yellow"|3|| 5||41235
|-
|19||bgcolor="yellow"|3||2||⇒|| 4|| 5||bgcolor="yellow"|1||bgcolor="yellow"|2||bgcolor="yellow"|3||45123
|-
|20||bgcolor="yellow"|3||2||⇒||bgcolor="yellow"|1|| 4||bgcolor="yellow"|2||bgcolor="yellow"|3|| 5||14235
|-
|21||bgcolor="yellow"|3||2||⇒|| 4||bgcolor="yellow"|1|| 5||bgcolor="yellow"|2||bgcolor="yellow"|3||41523
|-
|22||bgcolor="yellow"|3||2||⇒||bgcolor="yellow"|1|| 4|| 5||bgcolor="yellow"|2||bgcolor="yellow"|3||14523
|-
|23||bgcolor="yellow"|3||2||⇒||bgcolor="yellow"|1||bgcolor="yellow"|2|| 4||bgcolor="yellow"|3|| 5||12435
|-
|24||bgcolor="yellow"|3||2||⇒|| 4||bgcolor="yellow"|1||bgcolor="yellow"|2|| 5||bgcolor="yellow"|3||41253
|-
|25||bgcolor="yellow"|3||2||⇒||bgcolor="yellow"|1|| 4||bgcolor="yellow"|2|| 5||bgcolor="yellow"|3||14253
|-
|26||bgcolor="yellow"|3||2||⇒||bgcolor="yellow"|1||bgcolor="yellow"|2|| 4|| 5||bgcolor="yellow"|3||12453
|-
|27||bgcolor="yellow"|4||1||⇒||bgcolor="yellow"|1||bgcolor="yellow"|2||bgcolor="yellow"|3||bgcolor="yellow"|4|| 5||bgcolor="pink"|12345
|-
|28||bgcolor="yellow"|4||1||⇒|| 5||bgcolor="yellow"|1||bgcolor="yellow"|2||bgcolor="yellow"|3||bgcolor="yellow"|4||51234
|-
|29||bgcolor="yellow"|4||1||⇒||bgcolor="yellow"|1|| 5||bgcolor="yellow"|2||bgcolor="yellow"|3||bgcolor="yellow"|4||15234
|-
|30||bgcolor="yellow"|4||1||⇒||bgcolor="yellow"|1||bgcolor="yellow"|2|| 5||bgcolor="yellow"|3||bgcolor="yellow"|4||12534
|-
|31||bgcolor="yellow"|4||1||⇒||bgcolor="yellow"|1||bgcolor="yellow"|2||bgcolor="yellow"|3|| 5||bgcolor="yellow"|4||12354
|-
|32||bgcolor="yellow"|5||0||⇒||bgcolor="yellow"|1||bgcolor="yellow"|2||bgcolor="yellow"|3||bgcolor="yellow"|4||bgcolor="yellow"|5||bgcolor="pink"|12345
|-
|colspan=10|32 casos - 5 repetidos = 27
|}
La mejor forma de describir el procedimiento de barajado es con ejemplos:

<u>Barajado rápido:</u>

Supóngase una baraja con cinco cartas, y que se desea saber en cuantas formas podrían quedar ordenadas las cinco cartas, sabiendo que se van a barajar con las siguientes reglas:
* Se parte de una baraja con las cartas ordenadas del 1 al 5
* Se divide el mazo de las cinco cartas en dos montones (izquierdo y derecho), que pueden tener entre 0 y 5 cartas.
* Se intercalan los dos montones, con la única condición de que se van eligiendo de arriba abajo las cartas de los dos montones (da igual de qué montón sea la carta elegida cada vez, siempre que sea una de las de arriba), y se van añadiendo a un nuevo montón, situando la nueva carta por debajo de la última carta añadida, hasta completar el mazo.    
En la tabla que se adjunta a la derecha, se han analizado todas las posibilidades para un mazo de 5 cartas. En amarillo, se han marcado las cartas del primer montón (las ''p'' primeras cartas) y sin color de fondo las del segundo montón (las ''q'' cartas restantes). De acuerdo con las reglas de barajado especificadas, se pueden dar 32 casos. Observando caso por caso, se puede comprobar que las cartas del primer montón (las cartas amarillas) siempre están en orden creciente, al igual que las cartas del segundo montón. Sin embargo, si se observa la última columna, se comprueba que hay cinco casos repetidos, por lo que el total de supuestos válidos son 32-5=27.

Como se explica más adelante:
* <math>\text{barajado } (n) = (\sum_{p=0}^{n} \binom{n}{p}) - n</math>, siendo <math> \binom{n}{p} = \frac {n!} {p!\;(n-p)!} </math>
Para el caso de <math>(n)=5</math>, entonces
* <math>\text{barajado } (5) = \binom{5}{0} + \binom{5}{1} + \binom{5}{2} + \binom{5}{3} + \binom{5}{4} + \binom{5}{5} - 5  = 1 + 5 + 10 + 10 + 5 + 1 - 5 =32 - 5 = 27 </math>

<u>Barajado rápido "perfecto":</u>

Supóngase que se tuviera una baraja de ocho cartas, inicialmente ordenadas del 1 al 8:
* {1, 2, 3, 4, 5, 6, 7, 8}
un proceso de barajado rápido implicaría formar dos montones, colocando el primero "a la izquierda" y el segundo "a la derecha". En este caso, se van a coger dos paquetes de cuatro cartas cada uno (p=q=4), aunque se podrían coger cantidades distintas (por ejemplo, p=3 y q=5):
* {1, 2, 3, 4} y {5, 6, 7, 8}
Ahora se procede a ''barajarlos'', intercalando las cartas colocando sucesivamente una de cada montón:
* {1, 5, 2, 6, 3, 7, 4, 8}, con ordenación izquierda-derecha, o bien
* {5, 1, 6, 2, 7, 3, 8, 4}, con ordenación derecha-izquierda
Como se puede apreciar, en ambos casos se obtienen dos secuencias crecientes de cartas (las que ocupan las posiciones impares por un lado, y las que ocupan las posiciones pares por otro).
Aplicando de nuevo el proceso, se tendría:
* {1, 3, 5, 7, 2, 4, 6, 8} o  bien {7, 5, 3, 1, 8, 6, 4, 2}

==Enumeración combinatoria==
Si se desea saber de cuántas maneras distintas puede quedar distribuido el mazo completo, teniendo en cuenta que tanto las cartas del primer montón como las del segundo aparecerán en orden creciente (dado que estaban ordenadas al comenzar a barajar), entonces un (''p'', ''q'')-barajado aleatorio, está completamente determinado por las posibles posiciones distintas que ocupan sus primeros ''p'' elementos, y el número de (''p'', ''q'')-barajados posibles es

: <math>\binom{p+q}{p}.</math>

Sin embargo, el número de barajados distintos no es exactamente la suma de esta fórmula sobre todas las opciones de ''p'' y ''q'' (que sería ''2''<sup>''n''</sup>), porque la [[permutación identidad]] aparece repetida en cada pareja de diferentes valores de ''p'' y ''q'', lo que implica que aparece en total ''n+1'' veces (desde 0 hasta n), por lo que deben eliminarse ''n'' repeticiones. En consecuencia, la fórmula que indica el número total de posibles distribuciones distintas es: 
:<math> 2^n - n </math>
El número de permutaciones de barajado rápido distintas de una baraja de ''n'' cartas, para ''n''&nbsp;=&nbsp;1, 2, 3, ..., es
: 1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ... {{OEIS|id=A000325}}
De manera más general, la fórmula para este número es 2<sup>''n''</sup>&nbsp;&minus;&nbsp;''n''. Así, por ejemplo, hay 4503599627370444 permutaciones de barajado rápido de una baraja de 52 cartas.

El número de permutaciones que son tanto permutaciones de barajado rápido como sus inversas son<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>
para ''n''&nbsp;=&nbsp;1, 2, 3, ..., forman la serie
: 1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ... {{OEIS|id=A050407}}
y para ''n''&nbsp;=&nbsp;52 hay exactamente 23427 barajados aleatorios invertibles. En este caso, invertible significa que aplicando dos veces sucesivas el orden del barajado rápido en cuestión, el mazo de cartas queda completamente ordenado de nuevo.

==Distribución aleatoria==
El [[modelo de Gilbert-Shannon-Reeds]] describe una [[distribución de probabilidad]] aleatoria de barajados rápidos que son una buena aproximación de los barajados rápidos humanos observados.<ref>{{citation
 | last = Diaconis | first = Persi | author-link = 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> En este modelo, la [[permutación identidad]] tiene la probabilidad (''n''&nbsp;+&nbsp;1)/2<sup>''n''</sup> de ser generada, y todas las demás permutaciones de barajado tienen la misma probabilidad 1/2<sup>''n''</sup> de ser generadas. Basándose en su análisis de este modelo, los matemáticos han recomendado que una baraja de 52 cartas reciba siete mezclados para que su distribución sea completamente aleatoria.<ref>{{citation|title=In Shuffling Cards, 7 Is Winning Number|first=Gina|last=Kolata|author-link=Gina Kolata|journal=[[The New York Times]]|url=https://www.nytimes.com/1990/01/09/science/in-shuffling-cards-7-is-winning-number.html|date=1990-01-09}}.</ref>

==Patrones de permutación==
Un [[patrón de permutación|patrón]] en una permutación es una secuencia más pequeña formada a partir de una subsecuencia de algunos valores de ''k'' en la permutación al reducir estos valores al rango de 1 a ''k'' mientras se conserva su orden. Varias familias importantes de permutaciones pueden caracterizarse por un [[conjunto finito]] de patrones prohibidos, y esto también es cierto para las permutaciones de barajado rápido: son exactamente las permutaciones que no tienen 321, 2143 y 2413 como patrones.<ref name="a99"/> Así, por ejemplo, son una subclase de las [[permutación vexilar|permutaciones vexilares]], que tienen 2143 como su único patrón mínimo prohibido.<ref>{{citation|title=Permutation patterns, continued fractions, and a group determined by an ordered set|first=Anders|last=Claesson|series=Ph.D. thesis|publisher=Department of Mathematics, Chalmers University of Technology|year=2004 (10.1.1.103.2001)}}.</ref>

==Mezcla perfecta==
{{AP|Mezcla faro}}
Un "barajado perfecto" es un mezclado en el que la baraja se divide en dos paquetes de igual tamaño, y en el que el entrelazado entre estos dos paquetes alterna estrictamente entre los dos. Hay dos tipos de mezclado perfecto, una [[mezcla faro|mezcla aleatoria perfecta de entrada]] y una [[mezcla faro|mezcla aleatoria perfecta de salida]], que pueden ser realizadas de manera consistente por personas capacitadas. Cuando un mazo se baraja repetidamente usando estas permutaciones, permanece mucho menos aleatorio que con el barajado típico, y volverá a su estado inicial después de solo una pequeña cantidad de barajados rápidos perfectos. En particular, una baraja de 52 naipes volverá a su orden original después de 52 barajados perfectos (cuando una carta del montón derecho queda arriba) o en 8 barajados (cuando una carta del montón izquierdo queda arriba). Este hecho forma la base de varios trucos de magia.<ref>{{citation
 | last1 = Diaconis | first1 = Persi | author1-link = Persi Diaconis
 | last2 = Graham | first2 = R. L. | author2-link = Ronald Graham
 | last3 = Kantor | first3 = William M. |author3-link=William Kantor
 | 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 (10.1.1.77.7769)
 }}.</ref>

==Álgebra==
Se pueden usar barajados rápidos para definir el [[álgebra de barajados]]. Es un tipo de [[álgebra de Hopf]] donde la base es un conjunto de palabras,
y el producto es el producto de barajado denotado por el símbolo sha "ш", la suma de todos los barajados de dos palabras.

En [[álgebra exterior]], el producto exterior de una forma ''p'' y de una forma ''q'' se puede definir como una suma sobre (''p'',''q'') barajados.<ref name=Weibel/>

==Referencias==
{{reflist}}

{{Control de autoridades}}
[[Categoría:Combinatoria]]