Probabilitats i l’amic invisible: quantes vegades hem de repetir l’assignació?

Abans d’ahir a la feina parlàvem sobre l’amic invisible i la probabilitat que al fer les assignacions a ningú li toqui fer-se un regal a si mateix. És a dir, si un conjunt de persones escriuen el seu nom en un paper, els barregen i en reparteixen aleatòriament un a cada un, quina és la probabilitat que ningú s’hagi quedat amb el paper que té escrit el seu nom?

Resulta que aquesta probabilitat no és res més que la proporció del número de desarranjaments (o derangements, en anglès) respecte el número total de permutacions possibles. Un desarranjament d’un conjunt $S$ és una permutació dels elements d’aquest conjunt en la qual cap dels elements no apareix en la seva posició original. O el que és el mateix, una bijecció $f:S\to S$ sense punts fixos, on $f(x)\neq x$ per qualsevol $x\in S$ .

El número de permutacions possibles d’un conjunt de $n$ elements és el factorial de $n$ : podem escollir el primer element d’entre $n$ elements diferents, el segon d’entre $n-1$ , etc., de manera que el total de combinacions possibles és $n!=n(n-1)(n-2)\ldots 1$ .

Comptar el número de desarranjaments és un xic més complex. Una manera de fer-ho és utilitzar el principi d’inclusió-exclusió. Però com en moltes altres situacions en què hem de “comptar coses”, una bona manera de fer-ho és amb funcions generatrius. Una funció generatriu és “un estenedor on pengem una seqüència de números per mostrar”, o més formalment un sèrie formal de potències, on els coeficients codifiquen la informació d’una seqüència de números $\{d_n\}$ .

Per comptar el número de desarranjaments amb funcions generatrius primer necessitem una relació de recurrència. Considerem que tenim un conjunt de $n+1$ elements, $S_{n+1}=\{1,2,\ldots,n+1\}$ . Aquest conjunt té $d_{n+1}$ desarranjaments. Agafem el desarranjament $\sigma=\{\sigma_1\sigma_2\ldots\sigma_{n+1}\}$ tal que $\sigma_{n+1}=j$ , on $1\leq j\leq n$ . Tenim dos casos possibles:

Si $\sigma_j\neq n+1$ , cada un dels elements $\sigma_i$ , amb $1\leq i\leq n$ , té un element prohibit del conjunt $\{1,2,\ldots,n\}$ (tots tenen prohibit el seu índex), i per tant en aquest cas hi ha $d_n$ desarranjaments possibles.
Si en canvi $\sigma_j=n+1$ , cada un dels $n-1$ elements $\sigma_i$ , amb $i\neq j,n+1$ té un element prohibit del conjunt $\{1,2,\ldots,j-1,j+1,\ldots,n\}$ , i per tant en aquest cas hi ha $d_{n-1}$ desarranjaments possibles.

Finalment, com que hi ha $n$ maneres diferents d’escollir $j$ , podem escriure

$\displaystyle d_{n+1} = n (d_n + d_{n-1})$

per $n\ge3$ . Si $n=1$ , no hi ha cap desarranjament possible ( $d_1=0$ ); si $n=2$ , n’hi ha un ( $d_2=1$ ). Podem definir també $d_0=1$ i així la relació anterior és vàlida també per $n=2$ . Ja tenim doncs la funció de recurrència. Ara utilitzem la funció generatriu exponencial de $d_n$ :

$\displaystyle D(x) = \sum_{n\ge0}\frac{d_n}{n!}x^n$ .

Fixeu-vos que cada terme de la sèrie és la divisió entre el número de desarranjaments i el número de permutacions per un conjunt de mida $n$ , que és just la probabilitat que estem buscant. Multipliquem per $x^n/n!$ a banda i banda de la relació de recurrència, i sumem per $n\ge0$ :

$\displaystyle \sum_{n\ge0}\frac{d_{n+1}}{n!}x^n = \sum_{n\ge0}\frac{n d_n}{n!}x^n + \sum_{n\ge0}\frac{nd_{n-1}}{n!}x^n$ .

El terme de l’esquerra és la derivada de $D(x)$ respecte $x$ . El primer terme de la dreta és $xD^\prime(x)$ , i el segon és directament $xD(x)$ . Per tant, ho podem reescriure com

$\displaystyle D^\prime(x) = xD^\prime(x)+xD(x)$ .

I d’aquí, trobar una expressió tancada per $D(x)$ fent alguna integral (i utilitzant que $D(0)=1$ ):

$\displaystyle \frac{D^\prime(x)}{D(x)} = \frac{x}{1-x}$

$\displaystyle \ln D(x) = \int \frac{x}{1-x}dx = -\ln (1-x) -x$

$\displaystyle D(x) = \frac{e^{-x}}{1-x}$

El terme $n$ -èssim de la sèrie $D(x)$ , que escrivim com $[x^n]D(x)$ , és $d_n/n!$ . Això, com hem vist abans, és la probabilitat que estem buscant: el número de desarranjaments entre el número de permutacions. D’altra banda, $[x^n]e^{-x}=(-1)^n/n!$ , i per tant la probabilitat que busquem és

$\displaystyle \frac{d_n}{n!} = [x^n]\frac{e^{-x}}{1-x} = \sum_{j=0}^n \frac{(-1)^j}{j!}$ .

A $d_n$ també se l’anomena el subfactorial, que s’escriu com $!n$ . Finalment, una última curiositat: si la mida del conjunt, $n$ , tendeix a infinit, el número de desarranjaments entre el número de permutacions (i per tant la probabilitat que el repartiment en l’amic invisible sigui vàlid) tendeix a l’invers del número $e$ :

$\displaystyle \lim_{n\to\infty} \frac{!n}{n!} = \frac{1}{e} \simeq 0.3679$ .

Per tant, és d’esperar que hàgim de repetir 3 vegades les assignacions en l’amic invisible per a que ningú es tingui a ell mateix. Però això és independent de com de gran sigui el grup que hi participa!

El problema de trobar el número de desarranjaments d’un conjunt de $n$ elements va ser plantejat per primer vegada per Pierre de Montmort el 1708, i solucionat per ell mateix el 1713 i independentment per Nicolaus Bernoulli més o menys a la vegada.

Posted on desembre 24, 2011 at 11:40 in ciència i divulgació | RSS feed | Respond | Trackback URL

Etiquetes: amic invisible, ciència, combinatòria, derangement, desarranjament, funció generatriu, matemàtiques, Nicolaus Bernoulli, permutació, Pierre de Montmort

Deixa un comentari Cancel·la les respostes

Enter your comment here...

Fill in your details below or click an icon to log in:

Correu electrònic (necessari) (Address never made public)

Nom (necessari)

Lloc web

You are commenting using your WordPress.com account. ( Log Out / Canvia )

You are commenting using your Twitter account. ( Log Out / Canvia )

You are commenting using your Facebook account. ( Log Out / Canvia )

Cancel·la

Connecting to %s

Q

Categories

Col·leccions

Arxiu