Desarranjament

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 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 al voltant de la mateixa època.

Exemple

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

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 (k, n) sigui la permutació de { 1, ..., n} que intercanvia k i n, i es fa que φ_n− 1 sigui la composició ((k, n) 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} = ((k, n − 1) o φ_{n − 1} o (k, n − 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 que la primera persona esculli el nombre i. Ara hi ha 2 opcions -

- La persona i pren el barret de 1. Per tant, 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 reenumerant el barret 1 com i. Per tant 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 d_n com el nombre de desarranjaments de n lletres, i es defineix d₀ = 1, d₁ = 0; llavors d _n satisfà la successió:

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

i també

$d_{n}=nd_{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:

$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, d_n, 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 ∞

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 = d_n/n! que una permutació seleccionada aleatòriament 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

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 A → S, sovint es desitja saber el nombre de parells de funcions (f, g) 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)).

Una 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 n₁ lletres de X₁, n₂ lletres de X₂..., n _r lletres de X_r 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 P_n , on P_n té grau n. Però la resposta anterior per al cas r = 2 dona una relació d'ortogonalitat, d'on els P_n's són els Polinomis de Laguerre (tret del signe que es determina fàcilment).

Referències

• 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

• Bogart, Kenneth P. and Doyle, Peter G. «Non-sexist solution of the ménage problem», 1985.
• Dickau, Robert M. «desarranjament diagrams». Figures Using Mathematica.
• Hassani, Mehdi. «desarranjaments and Applications». Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003.