(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 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.^[1] 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 + q = n, es un barajado en el que el primer montón del corte tiene p cartas y el segundo tiene q cartas.^[2]

Analíticamente, los barajados rápidos son las permutaciones del conjunto σ{1, 2, ..., p + q}, tales que σ(1) < σ(2) < ... < σ(p) y σ(p + 1) < σ(p + 2) < ... < σ(p + q).

Procedimiento de barajado[editar]

Barajado rápido (n=5)
Caso	p	q	⇒	1ª	2ª	3ª	4ª	5ª	TOTAL
1	0	5	⇒	1	2	3	4	5	12345
2	1	4	⇒	1	2	3	4	5	12345
3	1	4	⇒	2	1	3	4	5	21345
4	1	4	⇒	2	3	1	4	5	23145
5	1	4	⇒	2	3	4	1	5	23415
6	1	4	⇒	2	3	4	5	1	23451
7	2	3	⇒	1	2	3	4	5	12345
8	2	3	⇒	3	1	2	4	5	31245
9	2	3	⇒	3	4	1	2	5	34125
10	2	3	⇒	3	4	5	1	2	34512
11	2	3	⇒	1	3	2	4	5	13245
12	2	3	⇒	3	1	4	2	5	31425
13	2	3	⇒	3	4	1	5	2	34152
14	2	3	⇒	1	3	4	2	5	13425
15	2	3	⇒	3	1	4	5	2	31452
16	2	3	⇒	1	3	4	5	2	13452
17	3	2	⇒	1	2	3	4	5	12345
18	3	2	⇒	4	1	2	3	5	41235
19	3	2	⇒	4	5	1	2	3	45123
20	3	2	⇒	1	4	2	3	5	14235
21	3	2	⇒	4	1	5	2	3	41523
22	3	2	⇒	1	4	5	2	3	14523
23	3	2	⇒	1	2	4	3	5	12435
24	3	2	⇒	4	1	2	5	3	41253
25	3	2	⇒	1	4	2	5	3	14253
26	3	2	⇒	1	2	4	5	3	12453
27	4	1	⇒	1	2	3	4	5	12345
28	4	1	⇒	5	1	2	3	4	51234
29	4	1	⇒	1	5	2	3	4	15234
30	4	1	⇒	1	2	5	3	4	12534
31	4	1	⇒	1	2	3	5	4	12354
32	5	0	⇒	1	2	3	4	5	12345
32 casos - 5 repetidos = 27

La mejor forma de describir el procedimiento de barajado es con ejemplos:

Barajado rápido:

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:

${\text{barajado }}(n)=(\sum _{p=0}^{n}{\binom {n}{p}})-n$ , siendo ${\binom {n}{p}}={\frac {n!}{p!\;(n-p)!}}$

Para el caso de $(n)=5$ , entonces

${\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$

Barajado rápido "perfecto":

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[editar]

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

{\binom {p+q}{p}}.

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ⁿ), 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:

2^{n}-n

El número de permutaciones de barajado rápido distintas de una baraja de n cartas, para n = 1, 2, 3, ..., es

1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ... (sucesión A000325 en OEIS)

De manera más general, la fórmula para este número es 2ⁿ − 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^[3]

{\binom {n+1}{3}}+1.

para n = 1, 2, 3, ..., forman la serie

1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ... (sucesión A050407 en OEIS)

y para n = 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[editar]

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.^[4] En este modelo, la permutación identidad tiene la probabilidad (n + 1)/2ⁿ de ser generada, y todas las demás permutaciones de barajado tienen la misma probabilidad 1/2ⁿ 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.^[5]

Patrones de permutación[editar]

Un 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.^[3] Así, por ejemplo, son una subclase de las permutaciones vexilares, que tienen 2143 como su único patrón mínimo prohibido.^[6]

Mezcla perfecta[editar]

Artículo principal: 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 aleatoria perfecta de entrada y una 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.^[7]

Álgebra[editar]

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.^[2]

Véase también[editar]

Permutaciones de Gilbreath, las permutaciones formadas invirtiendo uno de los dos paquetes de cartas antes de barajarlos.

Referencias[editar]

↑ Aldous, D.; Diaconis, P. Shuffling Cards and Stopping Times.
↑ ^a ^b Weibel, Charles (1994). An Introduction to Homological Algebra, p. 181. Cambridge University Press, Cambridge.
↑ ^a ^b Atkinson, M. D. (1999), «Restricted permutations», Discrete Mathematics 195 (1-3): 27-38, MR 1663866, doi:10.1016/S0012-365X(98)00162-9 ..
↑ Diaconis, Persi (1988), Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Hayward, CA: Institute of Mathematical Statistics, ISBN 0-940600-14-5, MR 964069 ..
↑ Kolata, Gina (9 de enero de 1990), «In Shuffling Cards, 7 Is Winning Number», The New York Times ..
↑ Claesson, Anders (2004 (10.1.1.103.2001)), Permutation patterns, continued fractions, and a group determined by an ordered set, Ph.D. thesis, Department of Mathematics, Chalmers University of Technology ..
↑ Diaconis, Persi; Graham, R. L.; Kantor, William M. (1983 (10.1.1.77.7769)), «The mathematics of perfect shuffles», Advances in Applied Mathematics 4 (2): 175-196, MR 700845, doi:10.1016/0196-8858(83)90009-X ..

Datos: Q13846433

[1] Aldous, D.; Diaconis, P. Shuffling Cards and Stopping Times.

[Weibel-2] Weibel, Charles (1994). An Introduction to Homological Algebra, p. 181. Cambridge University Press, Cambridge.

[a99-3] Atkinson, M. D. (1999), «Restricted permutations», Discrete Mathematics 195 (1-3): 27-38, MR 1663866, doi:10.1016/S0012-365X(98)00162-9 ..

[4] Diaconis, Persi (1988), Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Hayward, CA: Institute of Mathematical Statistics, ISBN 0-940600-14-5, MR 964069 ..

[5] Kolata, Gina (9 de enero de 1990), «In Shuffling Cards, 7 Is Winning Number», The New York Times ..

[6] Claesson, Anders (2004 (10.1.1.103.2001)), Permutation patterns, continued fractions, and a group determined by an ordered set, Ph.D. thesis, Department of Mathematics, Chalmers University of Technology ..

[7] Diaconis, Persi; Graham, R. L.; Kantor, William M. (1983 (10.1.1.77.7769)), «The mathematics of perfect shuffles», Advances in Applied Mathematics 4 (2): 175-196, MR 700845, doi:10.1016/0196-8858(83)90009-X ..

[1]

[2]

[3]

[4]

[5]

[6]

[7]