Desarranjament

De Viquipèdia
Dreceres ràpides: navegació, cerca

En matemàtiques combinatòries, un desarranjament és una permutació en la qual cap dels elements del conjunt no apareix en la seva posició original. És a dir, és una bijecció φ des d'un conjunt S a si mateix sense punts fixos: per a tot x en S, φ(x) ≠ x. Els nombres de desarranjaments per a conjunts de mida n, en variar n, s'anomenen "nombres de de Montmort" o "nombres de desarranjament" (i es pot generalitzar a nombres de rencontres); la funció que expressa aquest nombre com a funció del nombre d'elements del conjunt és la funció subfactorial. El primer a estudiar el problema de comptar desarranjaments va ser Pierre Raymond De Montmort el 1708; el va resoldre el 1713, igual que Nicholas Bernoulli a al voltant de la mateixa època.

Exemple[modifica | modifica el codi]

Suposeu que un professor hagi classificat 4 proves per a 4 estudiants. El primer estudiant, estudiant A, posa un "A" en la prova, l'estudiant B un "B", etcètera. Tanmateix, el professor barreja les proves en retornar-les, i ara cap dels estudiants no té la prova correcta. De quantes maneres els podria haver barrejat el professor d'aquesta manera? De 24 permutacions possibles per retornar les proves, hi ha només 9 desarranjaments:

BADC, BCDA, BDAC,
CADB, CDAB, CDBA,
DABC, DCAB, DCBA.

En cada una de les altres permutacions d'aquest conjunt de 4 membres, com a mínim un estudiant aconsegueix la prova correcta.

Una altra versió del problema sorgeix quan es pregunta pel nombre de formes que n cartes, cada una adreçada a una persona diferent, es poden posar dins n sobres amb l'adreça escrita prèviament de manera que cap carta no aparegui al sobre amb l'adreça correcta.

Comptar desarranjaments[modifica | modifica el codi]

Una aproximació a comptar els desarranjaments de n elements és fer servir inducció. Primer, s'observa que si φn és qualsevol desarranjament dels nombres naturals { 1, ..., n}, llavors per a alguns k en { 1, ..., n  − 1 }, φn(n)  = k. Llavors si es fa que (kn) sigui la permutació de { 1, ..., n} que intercanvia k i n, i es fa que φn− 1 sigui la composició ((kn)  oφn); llavors φn−1(n) = n, i o bé:

  • φn  − 1(k)  ≠ k, així φ;n  − 1 és un desarranjament de { 1, ..., n  − 1 }, o
  • φn −1(k) = k, i per a tot x  ≠ k, φn −1(x)  ≠ x.

En l'últim cas, φn − 1 és un desarranjament del conjunt { 1, ..., n − 1 } excloent k; és a dir, la composició φn −2 = ((kn  − 1) o φn − 1 o (kn − 1)) és un desarranjament de { 1, ..., n − 2 }.

Com a exemples d'aquests dos casos, considereu els següents dos desarranjaments de 6 elements en realitzar els canvis descrits damunt:

514623 → (51432)6; i
315624 → (31542) 6 → (3142)56

La lògica citada es pot explicar més intuïtivament de la manera següent. Suposeu que hi hagi n persones numerades 1,2, ..., n. Si hi ha n barrets també numerats 1,2, ..., n. S'ha de trobar el nombre de formes en què ningú no té el barret que té el mateix nombre que ell. Suposant que la primera persona pren el barret i. Hi ha n - 1 maneres de que la primera persona esculli el nombre i. Ara hi ha 2 opcions -

- Person i takes the hat of 1. So Now the problem reduces to n − 2 persons and n − 2 hats.
- La persona i pren el barret de 1. Per tan ara el problema es redueix a n -2 persones i n − 2 barrets.
- La persona i no pren el barret de 1. Aquesta situació es pot simular com renumeran el barret 1 com i. Per tan ara el cas és equivalent a resoldre el problema amb n -1 persones i n -1 barrets.

A partir d'aquí, la relació següent és clara:

d_n = (n - 1) (d_{n-1} + d_{n-2}).\,

Les correspondències descrites més amunt són funcions injectives. El reciproc també és cert; hi ha exactament (n  − 1) maneres de convertir qualsevol desarranjament de n -1 elements en un desarranjament de n elements, i (n − 1) maneres de convertir qualsevol desarranjament de n -2 elements en un desarranjament de n elements. Per exemple, si n = 6 i k = 4, es poden realitzar les conversions següents de desarranjaments de longituds 5 i 4, respectivament

51432 → 514326 → 514623; i
3142 → 31542 → 315426 → 315624

Així, si s'escriu dn com el nombre de desarranjaments de n lletres, i es defineix d0 = 1, d1 = 0; llavors d n satisfà la sucessió:

d_n = (n - 1) (d_{n-1} + d_{n-2})\,

i també

d_n = n d_{n-1} + (-1)^{n} , \quad n\geq 1

Fixeu-vos que aquesta mateixa fórmula de recurrència també funciona per factorials amb valors d'engegada diferents. És a dir 0! = 1, 1! = 1 i

n! = (n - 1) ((n-1)! + (n-2)!)\,

que és útil en demostrar la relació de límit amb e més avall.

També, són conegudes les següents fórmules:[1]

d_n = n! \sum_{i=0}^n \frac{(-1)^i}{i!}
d_n = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor = \left(\text{enter m}\acute{e}\text{s proper a }\frac{n!}{e}\right), \quad n\geq 1
d_n = \left\lfloor(e+e^{-1})n!\right\rfloor-\lfloor en!\rfloor , \quad n\geq 2.

Començant amb n  = 0, els nombres de desarranjaments, dn, són:

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... (successió A000166 a l'OEIS).

Aquests nombres també s'anomenen subfactorials.

Límit quan n tendeix a ∞[modifica | modifica el codi]

Utilitzant aquesta recurrència, es pot mostrar que, en el límit

\lim_{n\to\infty} {d_n \over n!} = {1 \over e} \approx 0.3679\dots.

Aquest és el límit de la probabilitat p n = dn/n! de que una permutació seleccionada aleatoriament sigui un desarranjament. La probabilitat s'acosta a aquest límit bastant de pressa.

Potser un mètode més conegut de desarranjaments de compte fa servir el principi d'inclusió-exclusió.

Generalitzacions[modifica | modifica el codi]

El problema de les trobades demana quantes permutacions d'un conjunt de n elements tenen exactament k punts fixes.

Els desarranjaments són un exemple del camp més ampli de permutacions amb restriccions. Per exemple, el problema de l'aparellament emana si n parelles casades s'asseuen home-dona-home-dona-... al voltant d'una taula circular, de quantes maneres se'ls pot asseure de manera que cap home no s'assegui al costat de la seva muller?

Més formalment, donats els conjunts A i S, i uns conjunts U i V de funcions exhaustives AS, sovint es desitja saber el nombre de parells de funcions (fg) tals que f pertany a U i g pertany a V, i per a tot a de A, f(a) ≠ g(a); en altres paraules, on per a cada f i g, existeix un desarranjament φ de S tal que f(a) = φ(g(a)).

Un altra generalització és el problema següent:

Quants anagrames sense lletres fixes d'una paraula donada hi ha?

Per exemple, perquè una paraula formada per només dues lletres diferents, és a dir n lletres A i m lletres B, la resposta és, naturalment, 1 o 0 depenent de si n = m o no, per a l'única manera de formar un anagrama sense lletres fixes és intercanviar completament A amb B, que és possible si i només si n = m. En el cas general, per a una paraula amb n1 lletres de X1, n2 lletres de X2..., n r lletres de Xr resulta (després d'un ús adequat de la fórmula d'inclusió-exclusió) que la resposta té la forma:

\int_0^\infty P_{n_1} (x) P_{n_2}(x)\cdots P_{n_r}(x) e^{-x}\, dx,

per a una certa successió de polinomis Pn , on Pn té grau n. Però la resposta anterior per al cas r = 2 dóna una relació d'ortogonalitat, d'on els Pn's són els Polinomis de Laguerre (tret del signe que es determina fàcilment).

Referències[modifica | modifica el codi]

  1. Hassani, M. "desarranjaments i Aplicacions." J. Enter Seq. 6, Núm. 03.1.2, 1–;8, 2003
  • de Montmort, P. R. (1708). Essay d'analyse sur les jeux de hazard. Paris: Jacque Quillau. Seconde Edition, Revue & augmentée de plusieurs Lettres. Paris: Jacque Quillau. 1713.

Enllaços externs[modifica | modifica el codi]