(p,q) barallats
En combinatòria i en l'estudi del barallat de naïps, una permutació de barallat ràpit (riffle shuffle en anglés) és una de les permutació d'un conjunt de n elements que es poden obtindre separant-los en dos montons i després intercalándolos (per eixemple, movent les cartes una a una des de la part inferior d'un o un atre dels dos montons a la part superior de la baralla fins a mesclar-la). Començant en un conjunt ordenat (una seqüència ascendent), matemàticament una mescla ràpida es definix com una permutació d'este conjunt, que conté la totalitat de les cartes ordenades en una o en dos seqüències ascendents.[1] Les permutació en una sola seqüència ascendent són les permutació identitat (és dir, en la baralla totalment ordenada).
Com un cas especial, un (p, q)-barallat, per als números p i q en p + q = n, és un barallat en el que el primer montó del tall té p cartes i el segon té q cartes.[2]
Analíticamente, els barallats ràpits són les permutació del conjunt σ{1, 2, ..., p + q}, tals que σ(1) < σ(2) < ... < σ(p) i σ(p + 1) < σ(p + 2) < ... < σ(p + q).
Procediment de barallat
| Cas | 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 repetits = 27 | |||||||||
La millor forma de descriure el procediment de barallat és en eixemples:
<o>Barallat ràpit:</o>
Suponga's una baralla en cinc cartes, i que es desija saber en quantes formes podrien quedar ordenades les cinc cartes, sabent que es van a barallar en les següents regles:
- Es partix d'una baralla en les cartes ordenades de l'1 al
5 * Es dividix el mall de les cinc cartes en dos montons (esquerre i dret), que poden tindre entre 0 i 5 cartes.
- Es intercalan els dos montons, en l'única condició de que es van elegint de dalt avall les cartes dels dos montons (té igual de quin montó siga la carta elegida cada volta, sempre que siga una de les de dalt), i es van afegint a un nou montó, situant la nova carta per baix de l'última carta afegida, fins a completar el mall.
En la taula que s'adjunta a la dreta, s'han analisat totes les possibilitats per a un mall de 5 cartes. En groc, s'han marcat les cartes del primer montó (les p primeres cartes) i sense color de fondo les del segon montó (les q cartes restants). D'acort en les regles de barallat especificades, es poden donar 32 casos. Observant cas per cas, es pot comprovar que les cartes del primer montó (les cartes grogues) sempre estan en orde creixent, de la mateixa manera que les cartes del segon montó. No obstant, si s'observa l'última columna, es comprova que hi ha cinc casos repetits, per lo que el total de supòsits vàlits són 32-5=27.
Com s'explica més alvance:
- , sent
Per al cas de , llavors
<o>Barallat ràpit "perfecte":</o>
Suponga's que es tinguera una baralla de huit cartes, inicialment ordenades de l'1 al 8:
- {1, 2, 3, 4, 5, 6, 7, 8}
un procés de barallat ràpit implicaria formar dos montons, colocant el primer "a l'esquerra" i el segon "a la dreta". En este cas, es van a agarrar dos paquets de quatre cartes cada u (p=q=4), encara que es podrien agarrar cantitats distintes (per eixemple, p=3 i q=5):
- {1, 2, 3, 4} i {5, 6, 7, 8}
Ara es procedix a barallar-los, intercalando les cartes colocant successivament una de cada montó:
- {1, 5, 2, 6, 3, 7, 4, 8}, en ordenació esquerra-dreta, o be
- {5, 1, 6, 2, 7, 3, 8, 4}, en ordenació dreta-esquerra
Com es pot apreciar, en abdós casos s'obtenen dos seqüències creixents de cartes (les que ocupen les posicions impars per un costat, i les que ocupen les posicions pares per un atre). Aplicant de nou el procés, es tindria:
- {1, 3, 5, 7, 2, 4, 6, 8} o be {7, 5, 3, 1, 8, 6, 4, 2}
Enumeració combinatòria
Si es desija saber de quantes maneres distintes pot quedar distribuït el mall complet, tenint en conte que tant les cartes del primer montó com les del segon apareixeran en orde creixent (ya que estaven ordenades en escomençar a barallar), llavors un (p, q)-barallat aleatori, està completament determinat per les possibles posicions distintes que ocupen les seues primers p elements, i el número de (p, q)-barallats possibles és
No obstant, el número de barallats distints no és exactament la suma d'esta fòrmula sobre totes les opcions de p i q (que seria 2n), perque la permutació identitat apareix repetida en cada parella de diferents valors de p i q, lo que implica que apareix en total n+1 voltes (des de 0 fins a n), per lo que deuen eliminar-se n repeticions. En conseqüència, la fòrmula que indica el número total de possibles distribucions distintes és:
El número de permutació de barallat ràpit distintes d'una baralla de n cartes, per a n = 1, 2, 3, ..., és
- 1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ... [1]
De manera més general, la fòrmula per a este número és 2n − n. Aixina, per eixemple, hi ha 4503599627370444 permutació de barallat ràpit d'una baralla de 52 cartes.
El número de permutació que són tant permutació de barallat ràpit com les seues inverses són[3]
per a n = 1, 2, 3, ..., formen la série
- 1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ... [2]
i per a n = 52 hi ha exactament 23427 barallats aleatoris invertibles. En este cas, invertible significa que aplicant dos voltes successives l'orde del barallat ràpit en qüestió, el mall de cartes queda completament ordenat de nou.
Referències
- ↑ Aldous, D.. “Shuffling Cards and Stopping Claves”.
- ↑ Weibel, Charles (1994). An Introduction to Homological Algebra, p. 181. Cambridge University Press, Cambridge.
- ↑ .
- Este artícul conté una traducció derivada de «(p,q) barajados» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.