domingo, 22 de novembro de 2026

As clases de combinatoria

 A combinatoria é un deses apéndices da materia que están aí colocados para producir curriculite. En efecto, se un revisa o currículo da Secundaria (eu non o fago porque para min é un arcano incomprensible) comprobará que os propios autores non coñecen nin o máis básico, a terminoloxía da materia (en galego). Vai de seguido captura de pantalla que debería arrubiar a máis de un.


Por se inesperadamente caeu por aquí algún despistado, na nosa lingua, o que no DOG aparece denominado como *variación, denomínase arranxo. Que non sexan públicas as identidades dos que cometen estas atrocidades é unha vergoña social cando a vergoña debería caer precisamente nos autores. Aquí salta, unha vez máis, o enorme dano que o decreto de prohibición de uso do galego no ensino lle fixo, e continúa a facer, á normalización dunha lingua que non ten nin tan sequera o estándar como piar firme ao que agarrarse. Alén disto, pregúntome se algún profesor, algunha vez, explica algo de combinatoria. Eu fágoo sempre que podo. Fágoo por varias razóns. Unha, que me gusta contar cousas, isto é, a combinatoria divírteme. Outra é que lembro moi ben cando ma explicaron a min por primeira vez. Eu ficara abraiado ao escoitar declamar, unha e outra vez, ao meu profesor "un arranxo de $m$ elementos tomados de $n$ en $n$ consiste en, dado un conxunto de $m$ elementos, formar todos os subconxuntos de $n$ elementos e ordenalos de todas as formas posibles". Se lle preguntabas outra vez o que era un arranxo, el volvía a contestar exactamente o mesmo, coas mesmas palabras. E se lle insistías en que non o entendías, el, con moita paciencia repetía: "un arranxo de $m$ elementos tomados de $n$ en $n$ consiste en, dado un conxunto de $m$ elementos, formar todos os subconxuntos de $n$ elementos e ordenalos de todas as formas posibles". Lembro estar na clase e desexar ter eu a claridade de ideas para poder recitar esta definición coa mesma seguridade. Creo que foi por iso polo que sempre quixen ser profesor de matemáticas.
Cando teño a oportunidade de introducir estes temas na aula, fágoo mediante problemas. A miña idea é que identifiquen cada tipo de reconto (arranxos, permutacións e combinacións) cun problema determinado. Creo que así o alumnado pode asimilar máis facilmente que tipo de técnica combinatoria convén aplicar a cada caso. Para concretar, comezo sempre co seguinte problema:
Problema de arranxos. Nunha carreira participan 20 corredores. Danse tres medallas: ouro, prata e bronce. De cantas maneiras podemos dar esas tres medallas aos 20 corredores?

Despois dun tempo no que os alumnos intentan resolvelo e eu intento poñer cara de póker diante de respostas máis ou menos desacertadas, pídolles que actúen con técnicas de resolución de problemas. Como non hai ningún problema semellante que saiban resolver, o mellor é variar o enunciado do problema, simplificándoo. "E se temos 4 corredores? ou 3 corredores?" Nestes casos é posible enumerar todos os casos. Despois: "e se só lle damos premio aos dous primeiros (medallas de ouro e prata)?". Este é un bo momento para introducir os diagramas en árbore para asegurármonos de que facemos un reconto completo. Finalmente, cando chegamos a dar a solución ao problema orixinal, podemos volver a cambiar o enunciado pero agora en sentido contrario. "Que pasa se, no canto de 20 corredores houbese 30, ou 12? E se outorgáramos 5 premios?" O obxectivo final é xeneralizar estes resultados e obter unha fórmula xeral para unha carreira na que participaran $m$ corredores coa promesa de $n$ premios. Daquela xa podemos pasar ao seguinte problema.
Problema de permutacións. De cantas formas podemos colocar 20 libros nun andel?
Aquí a cousa vai máis rápido. "Que pasa de temos 3 libros? E 4? Cal é a diferenza entre colocar 20 libros nun andel e dar 20 premios distintos a 20 corredores? E se temos $n$ libros?" 
Os resultados vistos aquí dan lugar a números enormes. Porén recontos máis modestos poden ser, paradoxalmente, máis dificultosos. Efectivamente, pasemos a considerar unha nova cuestión:
Problema de combinacións. Nunha carreira local participan 20 corredores. Clasificaranse para unha competición de maior nivel os 3 primeiros. De cantas formas podemos escoller eses 3 corredores? Neste caso non importa a orde en que cheguen, pois clasifícanse os 3.
Outra vez, pensar o problema con 4 ou 5 corredores e facer un reconto de todas as posibilidades é bastante factible. Con todo, aquí aproveito para explicarlles a seguinte fórmula $C_{4,3}\cdot P_{3}=A_{4,3}$. Velaquí un fragmento dos apuntes:

Toca outra vez xeneralizar. Chegados a este punto, alén de abordar problemas variados tamén se trata o triángulo de Pascal, as propiedades dos números combinatorios e o desenvolvemento do binomio de Newton. 

Arranxos, combinacións e permutacións con repetición
Hai problemas que explican moi ben que todo o relatado ata aquí non serve para todo tipo de recontos, incluso para recontos moi básicos:
Problemas con repetición. Trátase de estudar os números de (ata) tres cifras. Para iso permitiremos que a primeira, ou as primeiras cifras, poidan ser ceros. Por exemplo, permitirémonos escribir os números $001$ e $013$. Cantos números de (ata) tres cifras hai? Cantos números de (ata) tres cifras teñen todas as súas cifras distintas?
Co criterio de ter un problema que identifique cada tipo de reconto, alén do anterior propóñolle o seguinte:
Problema dos arranxos con repetición. De cantas formas distintas podemos cubrir as 14 filas dun boleto dunha quiniela? Dato: Fanse apostas a 14  partidos de fútbol marcando 1X2
En canto ás permutacións con repetición, tiro pola poesía, e sigo o guión comentado nesta outra entrada

Finalmente, abordar as combinacións con repetición, é todo un reto. 
Problema de combinacións con repetición. Catro amigos van cear a un restaurante. Poden escoller entre tres pratos: arroz, bacallau e coello. Cantas peticións distintas poden facer?
Nada impide facer un reconto de todos os casos. En cada petición pode repetirse calquera prato, ademais está claro que non importa a orde en que fagan a petición. Partimos dun conxunto de tres elementos, {𝐴, 𝐵, 𝐶}. Un caso posible podería consistir en 2 arroces, 1 bacallau e 1 coello (A,A,B,C). Elaborada a lista regálolles unha idea, a de codificar con uns e ceros as posibilidades. Escribiremos tantos uns como arroces, despois un cero para separar, despois tantos uns como bacallaus, outro cero para separar e finalmente tantos uns como coellos. Por exemplo, o caso anterior, (A,A,B,C), codificaríase 110101. Se comeran 3 arroces e un coello (A,A,A,C), teriamos o código 111001. Vemos que en cada codificación hai 4 uns e 2 ceros e, dada calquera secuencia deste tipo, hai unha única comanda asociada. A secuencia 011011 corresponderíase con 0 arroces, 2 bacallaus e 2 coellos. Velaquí todos os casos posibles coas correspondentes codificacións:
1 AAAA 111100
2 AAAB 111010
3 AAAC 111001
4 AABB 110110
5 AABC110101
6 AACC 110011
7 ABBB 101110
8 ABBC 10110
9 ABCC 101011
10 ACCC 100111
11 BBBB 011110
12 BBBC 011101
13 BBCC 011011
14 BCCC010111
15 CCCC 001111

Este sería un exercicio de combinacións con repetición de tres elementos, {A,B,C} tomados en grupos de 4. Acabamos de ver que se poden codificar como todas as posibles permutacións con repetición de 4 uns e 2 ceros: $$CR_{3,4}=PR_{6}^{2,4}=\frac{6!}{2!4!}=\binom{6}{4}=\binom{3+4-1}{4}$$
Agora consideremos o mesmo problema, pero con 6 comensais. Partimos dun conxunto de 3 elementos {A, B, C} que temos que escoller en grupos de 6. Unha posible escolla sería A,A,B,B,B,C, que codificado con ceros e uns quedaría en 11011101, unha lista con 2 ceros e 6 uns. Procedendo da mesma maneira que antes o reconto quedaría así: $$CR_{3,6}=PR_{8}^{2,6}=\frac{8!}{2!6!}=\binom{8}{6}=\binom{3+6-1}{6}$$
Volvamos a variar o problema. Consideremos 6 comensais que escollen entre 5 pratos: arroz, bacallau, coello, dourada e empanada. Partimos dun conxunto de 5 elementos {A, B, C,D, E} que temos que escoller en grupos de 6. Unha posible escolla sería A,A,C,D,E,E que codificado con ceros e uns quedaría en 1100101011, unha lista con 4 ceros e 6 uns. Como hai 5 pratos, e os ceros utilizámolos para separar cada tipo de prato, temos que escribir 5 − 1 = 4 ceros. Procedendo da mesma maneira que nos casos anteriores: $$CR_{5,6}=PR_{10}^{4,6}=\frac{10!}{4!6!}=\binom{10}{6}=\binom{5+6-1}{6}$$
Xa só nos quedaría xeneralizar: $$CR_{m,n}=PR_{m+n-1}^{m-1,n}=\frac{(m+n-1)!}{4(m-1)!n!}=\binom{m+n-1}{n}=\binom{m+n-1}{n}$$
Para finalizar, outra vez práctica con problemas variados de todo tipo. 

Ningún comentario:

Publicar un comentario