Os secretos matemáticos do triángulo de Pascal

Velaquí o famoso vídeo de TEDed sobre o triángulo de Pascal con subtítulos en galego. A cousa empezou nos XXI Encontros para a normalización lingüística organizados polo Consello da Cultura Galega. Alí Xusto Rodríguez explicou como funcionaba o proxecto de tradución de vídeos TED.
O proceso de aprendizaxe de uso da plataforma de tradución é simple. Basta con seguir os pasos indicados nesta serie de vídeos.
A ventaxa principal deste tipo de traballo, penso eu, é a simplicidade de todo o proceso. O peor é que para que se publique unha tradución é que hai que agardar a que outro tradutor, nun principio máis experto, che revise o traballo e non sempre vai haber alguén do outro lado da arañeira de internet mirando a ver o que fas. Cumpriría ter un grupo de traballo organizado para sacar adiante tanto as traducións feitas e sen publicar, como as que vaian chegando. Unha dificultade engadida, segundo me pareceu ver, é que na primeira tradución gozas dunha serie de ventaxas que xa non se dan nas seguintes (agás que soltes a xarda). Ademais de facer a tradución, hai que colocar cada secuencia dentro dun intervalo de tempo. A primeira vez podes usar a temporalización doutro idioma. Non poder seguir facéndoo nas seguintes é unha carga de traballo engadida, e non pequena. Con todo, no momento da publiación desta entrada, xa hai unhas 300 traducións ao galego.

Como Euler arranxou un desarranxo

Problema 1.Un grupo de 14 profesores dun claustro escolar organiza unha comida para celebrar a finalización da avaliación. Para armar festa alguén propuxera facer un amigo invible: cada un levaría un pequeno agasallo que se sortearía durante a celebración. Alguén comenta: "é ben seguro que algún vai levar o regalo que el mesmo comprou". Velaquí un problema matemático: cal é a probabilidade de que haxa algúen a quen lle toque o seu propio agasallo?

Sabía que coñecía o problema, só que tiña outro enunciado, aínda que cunha redacción referida a unha realidade doutra época:

Problema 2. O encargado do gardarroupa dun establecemento esqueceuse de etiquetar os sombreiros dos clientes e decide devolvelos ao chou. Cal é a probabilidade de que polo menos unha persoa reciba o seu sombreiro?

Ou incluso este outro, que fai referencia a cando aínda se escribían cartas:

Problema 3. Un encargado debe enviar n cartas a n direccións diferentes. Como é pouco responsable co seu traballo, introduce as cartas nos sobres ao azar. Achar a probabilidade de que introducira algunha carta no sobre correspondente.

A seguinte, e última versión, recibiu o nome do xogo do recontre

Problema 4. Dúas persoas, A e B, cunha baralla completa cada unha, sacan a un tempo cada súa carta. Se extraen a mesma carta gana A. Se  repiten a operación ata esgotar todas as cartas e nunca coinciden, ganará B. Pídese a probabilidade de que gane cada un dos xogadores.

Esta última versión foi proposta por Pierre Rémond de Montmort (1678-1719)  nun ensaio publicado no 1708. Na segunda edición desta obra (1713) resolve algúns casos simples pero queda sen dar unha solución xeral. Un dos que se enfrontaría á cuestión sería Leonhard Euler no seu  Calcul de la probabilité dans le jeu de rencontre (1743). De seguido vou debullar esta resolución porque é un exemplo maxistral de como abordar un problema. En primeiro lugar profundiza sobre el, estuda varios casos ata familiarizarse con el. Cando non pode seguir traballando caso a caso busca unha propiedade que lle permita domesticalo e preparar así o asalto final. Vou seguir os pasos de Euler aínda que o farei usando unha notación distinta. Se o fago así non é por capricho, senón que despois de ler a súa resolución, vin que a entendía mellor facendo uso deste anacronismo. Polo demais, no esencial, reproducirei con toda fidelidade o seu razoamento.
A versión sobre a que traballa Euler é a dun xogo de cartas na que dúas persoas A e B, con cada seu mazo completo de cartas, van sacándoas de unha en unha. Se nalgún momento sacan os dous a mesma carta gañará A. Se, pola contra, ningún par de cartas é coincidente, gañará B. Trátase de calcular a probabilidade de que gañe cada un deles.

No canto de cartas imos falar de números e no canto de considerar únicamente o caso das 52 cartas dunha baralla francesa, trataremos o problema xeral de n cartas.
En primeiro lugar, sen perda de xeneralidade, podemos supoñer que un dos xogadores (consideremos que sexa o xogador A) ten ordenadas todas as súas cartas en orde crecente: 1, 2, 3,....,n. Agora o problema consistirá en contabilizar o número de permutacións nas que ningún elemento coincida con esta dada. Este tipo de reconto é hoxe coñecido como desarranxo.
Fago aquí unha paréntese terminolóxica. Escollín o termo desarranxo por varias razóns. En primeiro lugar xa temos en galego outro termo para referirnos a outro reconto combinatorio: arranxo
(os arranxos de n elementos tomados de m en m consisten en todos os subconxuntos ordenados de m elementos que podemos formar nun conxunto de n elementos, con m ≤ n). En segundo lugar, a denominación en inglés é derangement, en francés dérangement e en portugués, desaranjo. En español só achei que para referirse á contabilización dos desarranxos, que se fai mediante a función subfactorial. Nesta lingua hai quen usa o termo desarreglo.

Volvamos á análise de Euler. Consideremos os primeiros casos.
Se n=1, gaña A
Se n =2, hai dúas posibilidades de extracción: (1,2) gañando A, e (2,1) gañando B.
Se n = 3 Euler fai a seguinte táboa con todas as posibilidades:

Táboa para n=3

Onde coa columna da esquerda indicamos as cartas de A, mentres que as columnas numeradas refírense a todas as posbiles xogadas de B.
Se denominamos $$A_n^k=noxogoconncartasAgañacoacartak$$
 $$A_n=noxogoconncartasAgaña(conalgunhacarta)$$
Podemos contabilizar o número de veces que gaña A e en que extracción. A gañará na primeira extracción nos casos 1 e 2 (ver táboa anterior), gañará na segunda extracción no caso 5 e na terceira extracción no caso 3.
$$P\left(A_3^1\right)=\frac{2}{6}P\left(A_3^2\right)=\frac{1}{6}P\left(A_3^3\right)=\frac{1}{6}$$
$$P\left(A_3\right)=\frac{4}{6}$$ 
Para n=4:

Táboa para n=4

A gaña na primeira extración nos 6 primeiros casos
A gaña na segunda extracción nos casos 17, 18, 21 e 22.
A gaña na terceira extracción nos casos 10, 12 e 21
A gaña na cuarta extracción nos casos 8 e 15
$$P\left(A_4^1\right)=\frac{6}{24}P\left(A_4^2\right)=\frac{4}{24}P\left(A_4^3\right)=\frac{3}{24}P\left(A_4^4\right)=\frac{2}{24}$$
$$P\left(A_4\right)=\frac{15}{24}$$
Para n = 5 teremos un total de 5! = 120 permutacións. Moi difícil de abarcar. Pasemos a profundizar nos casos estudados e intentemos xeneralizar o que xa coñecemos. Por exemplo, con 4 cartas temos 4! ordenacións distintas. Delas danse 6 coincidencias na primeira extracción. Se non rematara o xogo coa primeira coincidencia tamén teriamos 6 coincidencias en cada unha das outras extraccións. Por exemplo na segunda vémola na táboa nos casos 1, 2, 17, 18, 21 e 22. Está claro que en xeral, para n cartas haberá (n-1)! coincidencias en calquera das extraccións . Isto permitiríanos a seguinte notación:
$a_n^k=nºdeéxitosdeAnak-ésimaextracciónconncartas$ 

$a_n^1=(n-1)!$
Deamos un paso máis. Sabemos que na segunda extracción A gaña menos que (n-1)! veces pois hai que restarlle algunha das veces que gañou coa primeira. No caso das 4 cartas, das 6 coincidencias temos que restar dúas: as correspondentes aos casos 1 e 2.
E que pasaría na terceira extracción? Aquí é onde agroma a xenialidade de Euler que desbloquea as dificultades e abre unha vía para abordar  o problema. Euler propón eliminar as cartas coincidentes nesa extracción nos dous mazos e pasa a contabilizar o resultado despois desta simplificación. Sabemos que hai 6 coincidencias na terceira fila (as correspondentes ás columnas 1, 6, 10, 12, 20 e 21). Eliminemos precisamente o 3 destes casos e quédanos:

táboa para n=3 (non é erro, compara coa de máis arriba)

Que son precisamente os 6 casos para n=3. Pero o problema de determinar en cantos casos gaña A na terceira extracción xa o resolvimos máis arriba. Sabemos que das 6 coincidencias da terceira fila debemos restar 2 da primeira e unha da segunda. Quédannos 3 vitorias para A.
En xeral, con n cartas,  para determinar o número de éxitos de A na k-ésima extracción, debemos suprimir as cartas nas que se produce esa k-ésima coincidencia polo que nos quedan n-1 cartas e un total de (n-1)! casos dos que debemos restar aqueles nos que houbo unha coincidencia das k-1 primeiras extraccións. Todo isto podemos expresalo con fórmulas; farémolo para o caso de termos n+1 cartas.
$a_{n+1}^1=n!$

$a_{n+1}^2=n!-a_n^1$   

$a_{n+1}^3=n!-a_n^1-a_n^2=a_{n+1}^2-a_n^2$ ....

$a_{n+1}^{k+1}=n!-a_n^1-a_n^2-....-a_n^k=a_{n+1}^k-a_n^k$
Con estes resultados no peto podemos poñernos a calcular os valores dos primeiros casos:
${Paran=1:a}_1^1=1$ 

${Paran=2:a}_2^1=1!=1a_2^2=a_2^1-a_1^1=1-1=0$ 

${Paran=3:a}_3^1=2!=2a_3^2=a_3^1-a_2^1=2-1=1a_3^3=a_3^2-a_2^2=1-0=1$

$Paran=4:a_4^1=3!=6a_4^2=a_4^1-a_3^1=6-2=4a_4^3=a_4^2-a_3^2=4-1=3$

$a_4^4=a_4^3-a_3^3=3-1=2$

Euler, incansable, continúa e ofrece todos estes valores:

nº de éxitos de A en cada extracción

Chegou o momento de calcular as probabilidades. Agora contamos co coñecemento suficiente para abordar o ataque final ao problema.

$P\left(A_n^k\right)=\frac{a_n^k}{n!}P\left(A_{n-1}^k\right)=\frac{a_n^k}{(n-1)!}$

$P\left(A_n^{k+1}\right)=\frac{a_n^{k+1}}{n!}=\frac{a_n^k-a_{n-1}^k}{n!}=\frac{a_n^k}{n!}-\frac{a_{n-1}^k}{(n-1)!\cdot n}=P\left(A_n^k\right)-\frac{P\left(A_{n-1}^k\right)}{n}[1]$
Agora podemos calcular as probabilidades de que, con n cartas, A gane na k-ésima extracción:

$P\left(A_n^1\right)=\frac{a_n^1}{n!}=\frac{(n-1)!}{n!}=\frac{1}{n}$

$P\left(A_n^2\right)=P\left(A_n^1\right)-\frac{P\left(A_{n-1}^1\right)}{n}=\frac{1}{n}-\frac{1}{n(n-1)}$

$P\left(A_n^3\right)=P\left(A_n^2\right)-\frac{P\left(A_{n-1}^2\right)}{n}=\frac{1}{n}-\frac{1}{n(n-1)}-\frac{1}{n}(\frac{1}{n-1}-\frac{1}{(n-1)(n-2)})=$

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

$P\left(A_n^4\right)=P\left(A_n^3\right)-\frac{P\left(A_{n-1}^3\right)}{n}=$

$=\frac{1}{n}-\frac{2}{n(n-1)}+\frac{1}{n(n-1)(n-2)}-\frac{1}{n}(\frac{1}{n-1}-\frac{2}{(n-1)(n-2)}+\frac{1}{(n-1)(n-2)(n-3)})=$

$=\frac{1}{n}-\frac{3}{n(n-1)}+\frac{3}{n(n-1)(n-2)}-\frac{1}{n(n-1)(n-2)(n-3)}$

$$

$.....$

$P\left(A_n^{k+1}\right)=\left(\begin{array}{c}k\\ 0\end{array}\right)\frac{1}{n}-\left(\begin{array}{c}k\\ 1\end{array}\right)\frac{1}{n(n-1)}+\left(\begin{array}{c}k\\ 2\end{array}\right)\frac{1}{n(n-1)(n-2)}-.......+{(-1)}^k\left(\begin{array}{c}k\\ k\end{array}\right)\frac{1}{n(n-1)...(n-k)}$

$.....$

$P\left(A_n^n\right)=\left(\begin{array}{c}n-1\\ 0\end{array}\right)\frac{1}{n}-\left(\begin{array}{c}n-1\\ 1\end{array}\right)\frac{1}{n(n-1)}+\left(\begin{array}{c}n-1\\ 2\end{array}\right)\frac{1}{n(n-1)(n-2)}-......+{(-1)}^n\left(\begin{array}{c}n-1\\ n-1\end{array}\right)\frac{1}{n!}$

Temos que sumar todos os valores anteriores. Como en cada fila nos aparecen os números combinatorios, unha boa estratexia é colocar os sumandos a semellanza do triángulo de Pascal e despois pasar a sumar as diagonais, tal e como se indica na imaxe:

Euler non fai referencia a Blaise Pascal (16232-1662), posiblemente porque recoñecía de sobra a propiedade que se debe aplicar para sumar cada unha destas diagonais. Aparecera como "terceira consecuencia" nun libro do matemático francés no que explicita 19 resultados sobre o famoso triángulo que leva o seu nome. A obra, O triángulo aritmético, publicárase póstumamente no 1665 aínda que xa estaba impresa no 1654 pois Pascal xa a divulgara entre as amistades. Esa terceira consecuencia é a que agora vén a denominarse en inglés como hockey-stick identity.
Facendo uso desta identidade sumaremos a k-ésima diagonal do anterior triángulo:


$\sum _{i=k}^{n-1}{(-1)}^k\left(\begin{array}{c}k\\ i\end{array}\right)\frac{1}{n(n-1).....(n-k)}={(-1)}^k\frac{1}{n(n-1).....(n-k)}\sum _{i=k}^{n-1}\left(\begin{array}{c}k\\ i\end{array}\right)=$

$={(-1)}^k\frac{1}{n(n-1)....(n-k)}\left(\begin{array}{c}n\\ k+1\end{array}\right)={(-1)}^k\frac{1}{(k+1)!}$
Finalmente poderemos obter o resultado de todas estas sumas, o que nos dá a probabilidade desexada, de que A gane nunha partida con n cartas:

$$P\left(A_n\right)=1-\frac{1}{2!}+\frac{1}{3!}-\frac{1}{4!}+\frac{1}{5!}-....+{(-1)}^{n-1}\frac{1}{n!}$$
Nun último toque fantástico Euler propón pensar que pasaría se o número de cartas fose infinito. 


$$P\left(A_{\mathrm{\infty }}\right)=1-\frac{1}{2!}+\frac{1}{3!}-\frac{1}{4!}+\frac{1}{5!}-....=1-\frac{1}{e}=0,632120558$$

$$P(B_{\mathrm{\infty }})=\frac{1}{e}=0,367879441$$
Leonhard Euler calcula as probabilidades para A e B ata n=15 e conclúe que cando o número de cartas supera as 12, as cifras decimais dadas anteriormente xa non varían. Lembremos que o noso problema orixinal falaba de 14 profesores polo que a resposta está suficientemente calculada.

Para disfrutar de Euler:
The Euler Archive
Euler. El maestro de todos los matemáticos, Dunham, William, Editorial Nivola (2000)