Matematica Discreta

Una (muy breve) introduccion a la Combinatoria.

El objetivo principal de la Combinatoria es determinar el numero de objetos pertenecien-tes a un conjunto dado y que verifican cierta condicion o propiedad. Este es el problemade conteo. Otro aspecto tambien importante asociado al problema de conteo es el pro-blema de enumeracion en el cual no interesa tanto saber el numero de objetos sinola obtencion explıcita de dichos objetos. Ambos problemas estan ıntimamente relaciona-dos y la resolucion de uno de ellos normalmente conlleva la resolucion del otro. En todaformula de tipo combinatorio subyace una algoritmo y recıprocamente en todo algoritmocombinatorio subyace una formula de conteo.

Emplearemos una notacion basada principalmente en conjuntos. Practicamente en todaslas propiedades asumiremos que los conjuntos que aparecen tiene cardinal finito. Como esusual, denotamos por |X| el cardinal o numero de elementos del conjunto X.

1. Principios basicos.

Recordemos que dos conjuntos A y B se dice que son disjuntos si no tienen ningunelemento en comun, es decir, si A ∩B = ∅.

Proposicion 1. (El Principio de la suma)Si A y B son dos conjuntos disjuntos, entonces |A ∪B| = |A|+ |B|.

Ejemplo 2. Si un municipio consta de dos nucleos de poblacion, habiendo en el primeroun total de 200 habitantes y en el segundo un total de 300 habitantes, entonces el numerode habitantes de dicho municipio es 200 + 300 = 500.

El Principio de la Suma puede presentarse de manera mas general como sigue.

Proposicion 3. Si A1, A2, . . . , An son conjuntos disjuntos dos a dos (es decir, Ai∩Aj = ∅para i 6= j ), entonces |A1 ∪ A2 ∪ · · · ∪ An| = |A1|+ |A2|+ · · ·+ |An|.

Recordemos que para dos conjuntos cualesquiera A y B, el producto cartesiano de Ay B, denotado por A × B, es el conjunto de todos los pares ordenados formados por unelemento de A y otro de B, es decir, A×B = {(a, b) | a ∈ A, b ∈ B}.

Proposicion 4. (El Principio del producto)Para dos conjuntos cualesquiera A y B se verifica que |A×B| = |A| · |B|.

Ejemplo 5. Supongamos que un viajante puede ir desde un paıs P1 hasta un paıs P2 enautobus, en tren o en avion, y puede ir desde P2 hasta un tercer paıs P3 en barco o enavion. Entonces el numero de posibilidades para hacer el viaje desde P1 hasta P3 pasandopor P2 es de 3 · 2 = 6.

El Principio del Producto puede presentarse de manera mas general como sigue.1

2

Proposicion 6. Para conjuntos cualesquiera A1, A2, . . . , An se verifica que

|A1 × A2 × · · · × An| = |A1| · |A2| · · · · · |An|.

Ejemplo 7. Supongamos que el menu ofrecido por un restaurante consta de un primerplato a elegir de entre 4 posibilidades, un segundo plato a elegir de entre 3 posibilidadesy postre a elegir de entre 5 posibilidades. Entonces el numero de menus posibles ofrecidospor el restaurante es 4 · 3 · 5 = 60.

Ejemplo 8. Sea un conjunto Σ = {a, b, c} al que llamaremos alfabeto. Una palabra sobreΣ es una secuencia (ordenada) finita de letras pertenecientes a Σ. Por ejemplo abbc y babcson dos palabras distintas sobre Σ. Admitimos ademas la existencia de una palabra especialsobre Σ a la que llamaremos la secuencia vacıa y que no contiene ninguna letra.

1. Por el Principio del Producto el numero de palabras sobre Σ de longitud n ≥ 0 esigual a 3n. Observese que cuando n = 0 se obtiene 30 = 1 que se refiere a la palabravacıa.

2. Por el Principio de la Suma, el numero de palabras sobre Σ de longitud menor oigual que n es 1 + 31 + 32 + · · · + 3n. Recordando que para a 6= 1 se verifica que1 + a1 + a2 + · · ·+ an = an+1−1

a−1, el numero de palabras sobre Σ de longitud menor

o igual que n es igual a 3n+1−12

.3. El numero de palabras de longitud n sobre Σ y que no empiezan por la letra b es

igual a 2 · 3n−1.

Dado un numero real x, definimos la parte entera de x como el mayor numero entero zverificando que z ≥ x. Designamos la parte entera de x por bxc.

Para dos numeros enteros a y b, siendo b 6= 0, se cumple que babc es igual al cociente de

dividir a entre b.Observese que si b y n numeros enteros, con n ≥ 0 y b 6= 0, el numero de elementos del

conjunto {1, . . . , n} que son multiplos de b es igual al cociente de dividir n entre b, es decir,bn

bc.

Ejemplo 9. ¿Cuantos numeros enteros menores o iguales que 1000 son multiplos de 7?La respuesta es b1000

7c = 142.

Ejemplo 10. ¿Cuantos numeros enteros x verificando que 600 < x ≤ 1000 son multiplosde 7?La respuesta es b1000

7c − b500

7c = 142− 85 = 57.

En general, si A y B son dos conjuntos cualesquiera, se verifica que

|A ∪B| = |A|+ |B| − |A ∩B|.

Ejemplo 11. ¿Cuantos numeros enteros positivos x ≤ 1000 son multiplos de 5 o de 7?Sean

X = {x ∈ Z | 1 ≤ x ≤ 1000},A = {x ∈ X | x es multiplo de 5}

3

y

B = {x ∈ X | x es multiplo de 7}.Observese que x ∈ A∩B si y solo si x es multiplo del mınimo comun multiplo de 5 y 7, esdecir, es multiplo de 35. Por consiguiente |A∪B| = |A|+ |B| − |A∩B| = b1000

5c+ b1000

7c−

b100035c = 200 + 142− 28 = 314.

De manera mas general, si A1, A2, . . . , An son subconjuntos de un conjunto X, se puededemostrar que

|A1 ∪ A2 ∪ · · · ∪ An| =∑

|Ai| −∑i6=j

|Ai ∩ Aj|+ · · ·+ (−1)n+1|A1 ∩ A2 ∩ · · · ∩ An|.

Basta tener en cuenta el caso para n = 2 y aplicar induccion sobre n.Notese que en la formula enterior, los signos aparecen de forma alternada. Ası por ejemplo

para A1, A2 y A3, tenemos

|A1 ∪A2 ∪A3| = (|A1|+ |A2|+ |A3|)− (|A1 ∩A2|+ |A1 ∩A3|+ |A2 ∩A3|) + |A1 ∩A2 ∩A3|.

Dicha formula se conoce con el nombre de Principio de Inclusion-Exclusion.Otra tecnica de conteo elemental consiste en definir una aplicacion biyectiva entre un

conjunto A cuyo cardinal queremos determinar y un conjunto B de cardinal conocido.

Ejemplo 12. Dado un conjunto X = {x1, . . . , xn}, vamos a probar que el numero desubconjuntos de X es igual a 2n. Como es usual, denotamos por P(X) el conjunto de laspartes de X, es decir, aquel cuyos elementos son todos y cada uno de los subconjuntos deX. Llamamos B = {0, 1} y suponemos ademas que los elementos de X estan ordenadosde la forma siguiente: x1 < · · · < xn. Defimos la aplicacion f : P(X) → Bn, comof(A) = (a1, . . . , an), siendo cada

ai =

{1 si xi ∈ A,0 en caso contrario.

Observese que f(∅) = (0, 0, . . . , 0) y f(X) = (1, 1, . . . , 1). Se puede justificar facilmente quef es una aplicacion biyectiva. Ya que por el Principio del Producto |Bn| = 2n, deducimosque |P(X)| = 2n.

Cerramos esta seccion sobre principos basicos mencionando la tecnica basada en plantearrelaciones de recurrencia. Hay problemas cuya solucion puede expresarse facilmentemediante una relacion de recurrencia. Vimos en el Tema 1 como el problema de calcularel menor numero de movimientos an para resolver el juego de las torres de Hanoi conn arandelas se resolvıa facilmente mediante una relacion de recurrencia. Concretamenteobtuvimos que a0 = 0 y ∀n ≥ 1, an = 2an−1 + 1. Veamos otro ejemplo.

Ejemplo 13. ¿Cuantas secuencias binarias, es decir, formadas por sımbolos 0 y 1, delongitud 20 existen de modo que en cada una de ellas no aparezcan dos (o mas) cerosconsecutivos?Sea Xn el conjunto de tales secuencias de longitud n. Podemos descomponer Xn como la

4

union disjunta de dos conjuntos An y Bn. El conjunto An esta formado por aquellas secuen-cias pertenecientes a Xn que empiezan por 1 mientras que Bn esta formado por aquellassecuencias pertenecientes a Xn que empiezan por 0. Si x1x2 . . . xn es una secuencia perte-neciente a An, es decir, x1 = 1, entonces x2 . . . xn es una secuencia arbitraria pertenecientea Xn−1. Esto nos dice que |An| = |Xn−1|. Si por el contrario x1x2 . . . xn es una secuenciaperteneciente a Bn, es decir, x1 = 0, entonces necesariamente x2 = 1 y x3 . . . xn es una se-cuencia arbitraria perteneciente a Xn−2, con lo cual |Bn| = |Xn−2|. Si llamamos fn = |Xn|,por el Principio de la Suma obtenemos que fn = |An|+|Bn| = |Xn−1|+|Xn−2| = fn−1+fn−2.Por tanto fn verifica una relacion de recurrencia lineal de orden dos, para la cual necesita-mos dos condiciones iniciales. Es inmediato que f1 = 2 y f2 = 3. Utilizando los resultadosanteriores obtenemos que f20 = 17711.

Una vez que tenemos una expresion recurrente nos podemos plantear obtener una ex-presion no recurrente equivalente. Este problema en general no tiene solucion.

2. Selecciones de elementos

Dado un conjunto A = {a1, . . . , an} vamos a estudiar el numero de formas de elegir oseleccionar r elementos de A atendiendo a dos criterios:

Que haya o no repeticion, es decir, que un elemento de A puede ser o no elegidomas de una vez.Que se tenga en cuenta o no el orden en el que se van eligiendo los elementos de A.

Detacamos que lo que nos interesa es el numero de resultados posibles tras el procesode eleccion. De este modo obtenemos cuatro casos o situaciones distintas segun haya o norepeticion y se tenga en cuenta o no el orden de eleccion.

2.1. Selecciones sin repeticion teniendo en cuenta el orden.

Cada seleccion de r elementos de A sin repeticion y teniendo en cuenta el orden deeleccion se denomina tradicionalmente una variacion ordinaria o sin repeticion de nelementos tomados de r en r. Se suele emplear el sımbolo V r

n para denotar el numero devariaciones ordinarias de n elementos tomados de r en r.

Nosotros tambien emplearemos el termino de r-permutacion de n elementos para refe-rirnos a las variaciones ordinarias de n elementos tomados de r en r, y usaremos el sımboloP (n, r) para indicar su numero. Debido a que no hay repeticion, ha de verificarse que0 ≤ r ≤ n.

Determinemos el valor exacto de P (n, r). Imaginemos un casillero que hemos de com-pletar con elementos de A sin que haya repeticion:

1 2 . . . r. . .

La primera casilla podemos rellenarla de n formas posibles, con cualquier elemento de A.Una vez hecho esto, nos quedan n − 1 elementos disponibles con cualquiera de los cuales

5

podemos rellenar la segunda casilla, y ası hasta la casilla numero r para la cual quedann− (r + 1) elementos posibles. Por el Principio del Producto resulta

P (n, r) = n(n− 1)(n− 2) · · · (n− r + 1),

valor que se suele escribir de la forma siguiente:

P (n, r) =n!

(n− r)!.

Observese que P (n, 0) = n!(n−0)!

= n!n!

= 1, valor que representa la secuencia vacıa.

Cada n-permutacion de A se denomina simplemente una permutacion del conjuntoA. Ya que P (n, n) = n!

(n−n)!= n!

0!= n!

1= n!, obtenemos que el numero de permutaciones de

A es igual a n!.

Ejemplo 14. Partiendo de un alfabeto A = {a, b, c, d, e, f, g}, ¿cuantas palabras de tresletras pueden formarse de modo que no se repita ninguna letra?Las condiciones del enunciado indican que se trata de variaciones ordinarias de siete ele-mentos tomados de tres en tres, cuyo numero viene dado por P (7, 3) = 7 · 6 · 5 = 210.

El numero de permutaciones del conjunto A es igual a P (7, 7) = 7! = 5040.

Ejemplo 15. ¿De cuantas formas pueden ocupar cuatro personas cuatro puestos de tra-bajo?Se trata de permutaciones de un conjunto de cuatro elementos cuyo numero viene dadopor 4! = 24.

El argumento dado mas arriba sobre rellenado de casillas muestra tambien la siguientepropiedad.

Proposicion 16. El numero de aplicaciones inyectivas que se pueden definir del con-junto {1, 2, . . . , r} en el conjunto A = {a1, . . . , an} es igual al numero de variacionesordinarias de n elementos tomados de r en r.

2.2. Selecciones sin repeticion y sin tener en cuenta el orden.

Una seleccion de r elementos de A sin repeticion y sin tener en cuenta el orden de eleccionse denomina una r-combinacion de A. Dar una r-combinacion de A es equivalente a darun subconjunto de A de cardinal r. Denotaremos el numero de r-combinaciones de A comoC(n, r).

Todas las r-permutaciones de A pueden ser obtenidas generando previamente todas lasr-combinaciones de A y ordenando (es decir, permutando) sus objetos de todas las formas

posibles. Esto implica queP (n, r) = C(n, r) · P (r, r),

de donde

C(n, r) =P (n, r)

P (r, r)=

n!

r!(n− r)!.

6

El numero C(n, r) se denomina numero combinatorio o coeficiente binomial y sedenota por

(nr

). A partir de la formula anterior obtenemos(

n

r

)=

n(n− 1)(n− 2) · · · (n− r + 1)

r!.

Se les llama coeficientes binomiales porque son los coeficientes que aparecen en la formuladel binomio de Newton. Como es sabido, si x e y son elementos de un anillo tales quex · y = y · x y n ∈ N, entonces

(x + y)n =n∑

k=0

(n

k

)· xk · yn−k.

Proposicion 17. (Propiedad de simetrıa para los numeros combinatorios)(n

r

)=

(n

n− r

).

Esta propiedad se puede demostrar facilmente usando la formula anterior, o bien obser-vando que la aplicacion f : P(A) → P(A) definida por f(B) = B transforma biyectiva-mente el conjunto de las r-combinaciones de A en el conjunto de las (n− r)-combinacionesde A.

Aplicando la formula anterior obtenemos que(

n0

)= 1, lo cual nos dice que existe una

unica 0-combinacion de A, es decir, un unico subconjunto con 0 elementos que como sabe-mos es el conjunto vacıo. Tambien

(n1

)= n. Por la propiedad de simetrıa obtenemos que(

nn

)= 1 y

(n

n−1

)= n.

Los numeros combinatorios verifican un sin fın de propiedades de las cuales destacamoslas siguientes:

1.(

n0

)+

(n1

)+ · · ·+

(nn

)= 2n.

Esta propiedad se puede deducir a partir de la formula del binomio de Newtonhaciendo x = y = 1. Otra forma de deducir la misma formula es teniendo en cuentael Ejemplo 12.

2.(

nr

)=

(n−1

r

)+

(n−1r−1

)siempre que 1 ≤ r < n.

Fijado x ∈ A, el conjunto de todas las r-combinaciones de A se obtiene como launion de dos conjuntos disjuntos: el conjunto de las r-combinaciones de A \ {x} yel conjunto de las r-combinaciones de A las cuales siempre contienen al elementox. Observamos que hay tantas r-combinaciones de A cada una de ellas conteniendoal elemento x como (r− 1)-combinaciones de A \ {x}. Aplicando el Principio de laSuma resulta la recurrencia anterior.

Ejemplo 18. ¿Cuantos numeros naturales se escriben en binario con diez dıgitos de loscuales siete son iguales a 1 y el resto son 0?

7

Dichos numeros son de la forma (1a8a7a6a5a4a3a2a1a0)2. Seis de los dıgitos a8, a7, a6, a5, a4,a3, a2, a1, a0 han de ser iguales a 1. El numero de formas de seleccionar tales dıgitos es(

9

6

)=

(9

9− 6

)=

(9

3

)=

9 · 8 · 73!

= 84.

Ejemplo 19. Queremos formar un comite de 12 personas las cuales han de ser escogidasde entre 10 hombres y 10 mujeres.

1. ¿De cuantas formas podemos hacerlo?Claramente la respuesta es(

20

12

)=

(20

8

)=

20 · 19 · 18 · 17 · 16 · 15 · 14 · 13

8!= 125970.

2. ¿Y si queremos que haya igual numero de hombres que de mujeres?El numero de formas de escoger 6 mujeres de entre 10 es

(106

)=

(104

)= 10·9·8·7

4!= 210,

valor que representa tambien el numero de formas de escoger 6 hombres de entre10. Por el Principio del Producto la respuesta es(

10

6

)·(

10

6

)= 210 · 210 = 44100.

2.3. Selecciones con repeticion teniendo en cuenta el orden.

Como antes A es un conjunto de n elementos elegibles y r es un numero natural queindica el numero de elecciones realizadas. Ahora r puede ser mayor que n, debido a quepermitimos repeticion.

Una variacion con repeticion de orden r de los elementos de A es una seleccionordenada de r elementos de A.

Dos variaciones son distintas si se diferencian en algun elemento, en la posicion de algunode estos en la variacion o en el numero de veces que se repite un elemento. Por ejemplo, siA = {1, 2, 3, 4}, son variaciones diferentes 123, 132 y 1132.

Cada variacion con repeticion de orden r de A podemos verla como una aplicacion delconjunto {1, 2, . . . , r} en A, con lo cual el numero de variaciones con repeticion de orden rde n elementos, denotado tradicionalmente por V R(n, r) o bien por V Rr

n, es igual que elnumero de aplicaciones del conjunto {1, 2, . . . , r} en A, valor que es igual a nr.

La justificacion es inmediata. Basta aplicar el mismo razonamiento que aplicamos paralas selecciones sin repeticion teniendo en cuenta el orden, pero ahora no existe la restriccionde que la imagen asignada a cada elemento del conjunto {1, 2, . . . , r} sea exclusiva para el.

Ejemplo 20. En una quiniela hay 15 partidos de futbol cada uno de los cuales tiene tresresultados posibles 1, x, 2. ¿De cuantas formas distintas se puede completar una quiniela?Son variaciones con repeticion de orden 15 del conjunto {1, x, 2}, es decir, V R(3, 15) = 315.

8

2.4. Selecciones con repeticion sin tener en cuenta el orden.

Una combinacion con repeticion de orden r de los n elementos de A es una seleccionno ordenada de r elementos de A que pueden repetirse. El numero de tales combinacionesse denota por CR(n, r). A veces diremos r-combinacion con repeticion de A parareferirnos a una combinacion con repeticion de orden r de A.

Existe una correspondencia biyectiva entre el conjunto de todas las combinaciones conrepeticion de orden r de los n elementos de A y el conjunto de todas las soluciones dela ecuacion x1 + x2 + · · · + xn = r, donde cada incognita xi puede tomar valores solo enN = {0, 1, 2, . . .}. De hecho xi representa el numero de veces que elegimos al elemento ai

de A.Por otro lado, existe otra correspondencia biyectiva entre el conjunto de soluciones para

la ecuacion anterior y el conjunto de todas las secuencias de longitud n + r − 1 dondeaparece r veces el sımbolo • y aparece n − 1 veces el sımbolo |. Concretamente cadasolucion (x1, x2, . . . , xn) se corresponde con la secuencia

x1︷ ︸︸ ︷• . . . • |

x2︷ ︸︸ ︷• . . . • | · · · |

xn︷ ︸︸ ︷• . . . •

Por lo tanto, buscamos el numero de formas de colocar n − 1 barras en un casillero conn + r − 1 posiciones, siendo ocupadas las restantes casillas por sımbolos •. Dicho numeroviene dado por

(n+r−1

n−1

)el cual es igual que

(n+r−1

r

). Este resultado se recoge en la siguiente

proposicion.

Proposicion 21. El numero de combinaciones con repeticion de orden r de n elementoses

CR(n, r) =

(n + r − 1

n− 1

)=

(n + r − 1

r

).

Ejemplo 22. ¿Cuantos resultados posibles pueden obtenerse al lanzar cuatro dados identi-cos?Un mismo valor puede aparecer en mas de un dado por lo que hay repeticion. Como losdados son identicos no importa el orden en el que aparecen los resultados.

Tenemos el conjunto A = {1, 2, 3, 4, 5, 6} de resultados basicos del cual elegimos conrepeticion y sin tener en cuenta el orden 4 elementos. Se trata de combinaciones conrepeticion de orden 4 para 6 elementos. La respuesta es

CR(6, 4) =

(6 + 4− 1

4

)=

(9

4

)=

9 · 8 · 7 · 64!

= 126.

Ejemplo 23. Una pastelerıa ofrece 8 tipos de pasteles distintos. Si se supone que hay almenos una docena de cada tipo, ¿de cuantas formas se puede seleccionar una docena depasteles?Nos estan preguntando el numero de soluciones de la ecuacion x1 + x2 + · · ·+ x8 = 12 con

9

incognitas sobre N. La respuesta es

CR(8, 12) =

(8 + 12− 1

12

)=

(19

12

)=

(19

7

)= 50388.

Ejemplo 24. Calculese el numero de soluciones de la inecuacion x1 + x2 + x3 ≤ 7 cuyasincognitas se consideran sobre N.Por el principio de la suma podemos sumar el numero de soluciones de cada una de lasecuaciones de la forma x1 + x2 + x3 = r para todo r ∈ {0, 1, . . . , 7}. Obtenemos una suma-toria de numeros combinatorios que puede escribirse como un solo numero combinatorioaplicando que (

m

0

)+

(m + 1

1

)+ · · ·+

(m + k

k

)=

(m + k + 1

k

).

Concretamente,(3 + 0− 1

0

)+

(3 + 1− 1

1

)+ · · ·+

(3 + 7− 1

7

)=

(2 + 7 + 1

7

).

Otro metodo alternativo consiste en darse cuenta de que el conjunto de soluciones dela inecuacion dada esta en correspondencia biyectiva con el conjunto de soluciones de laecuacion x1 + x2 + x3 + x4 = 7, siendo x4 una nueva variable. La respuesta es

CR(4, 7) =

(4 + 7− 1

7

)= 120.

Resumimos todo lo visto hasta ahora sobre selecciones en la tabla siguiente:

n objetos, se eligen r con orden sin ordensin repeticion V (n, r) = n!

(n−r)! C(n, r) =(nr

)= n!

r!(n−r)!

con repeticion V R(n, r) = nr CR(n, r) =(n+r−1n−1

)3. Mas sobre permutaciones

Ya hemos estudiado anteriomente el concepto de r-permutacion y el de permutacion deun conjunto A como selecciones sin repeticion y teniendo en cuenta el orden. Ahora consi-deramos las permutaciones con repeticion permitiendo que haya elementos repetidos.Supongamos n objetos, de los cuales hay r1 de un primer tipo, r2 de un segundo tipo, yası hasta rt de un tipo t, con r1 + r2 + · · ·+ rt = n y donde dos objetos de un mismo tipo seconsideran indistinguibles. Denotamos el numero de secuencias que se pueden formar conesos n objetos, por (

n

r1, r2, . . . , rt,

)

10

y que como mostramos a continuacion es igual a

n!

r1!r2! · · · rt!.

Una forma de demostrar que esta expresion es valida consiste en imaginar un casillero delongitud n, en el cual colocamos en primer lugar los r1 objetos de tipo 1, a continuacionlos objetos de tipo 2, y ası hasta que en el ultimo paso colocamos todos los objetos de tipot en las casillas restantes. El numero de formas de colocar los objetos de tipo 1 es igual a(

nr1

). El numero de formas de colocar los objetos de tipo 2 es igual a

(n−r1

r2

), pues el numero

de casillas libres tras colocar aquellos de tipo 1 es n − r1. Procediendo de esta forma yaplicando el Principio del Producto obtenemos que(

n

r1, r2, . . . , rt

)=

(n

r1

)(n− r1

r2

)(n− r1 − r2

r3

)· · ·

(n− r1 − · · · − rt−1

rt

).

Substituyendo las expresiones para cada numero combinatorio y simplificando, resulta(n

r1, r2, . . . , rt

)=

n!

r1!r2! · · · rt!.

Los numeros(

nr1,r2,...,rt

)se denomian coeficientes multinomiales. La justificacion se

encuentra en la propiedad siguiente.

Teorema 25. (Teorema multinomial)Sean x1, . . . , xt elementos de un anillo tales que xi · xj = xj · xi para cualesquiera i, j ∈{1, 2, . . . , t} y sea n ∈ N. Entonces

(x1 + · · ·+ xt)n =

∑0 ≤ r1, r2, . . . , rt ≤ nr1 + r2 + · · ·+ rt = n

(n

r1, r2, . . . , rt

)· xr1

1 · xr22 · · ·xrt

t .

En la sumatoria anterior hay tantos sumandos como tuplas de numeros naturales (r1, r2, . . . , rt)tales que r1 + r2 + · · ·+ rt = n.

Observese que cuando t = 2, el Teorema Multinomial se reduce a la formula del binomiode Newton, pues al ser r1 + r2 = n, resulta(

n

r1, r2

)=

n!

r1!r2!=

n!

r1!(n− r1)!=

(n

r1

).

Ejemplo 26. ¿De cuantas formas se pueden ordenar todas las letras que aparecen en lapalabra RELEER?Respuesta: (

6

3, 2, 1

)=

6!

3!2!1!= 60.

11

Ejemplo 27. ¿Cual es el coeficiente del termino x2y3z3 en el polinomio (x + y + z)8?Por el Teorema Multinomial, dicho coeficiente es(

8

2, 3, 3

)=

8!

2!3!3!= 560.

En ultimo lugar estudiamos las permutaciones circulares. Dados n y r, con r ≤ n,una permutacion circular de orden r para n objetos es una disposicion de r objetos en rposiciones igualmente espaciadas sobre una circunferencia. Dos permutaciones circularesson iguales si una se puede obtener a partir de la otra mediante una rotacion convenientealrededor del centro de la circunferencia.

Proposicion 28. El numero de permutaciones circulares de orden r de n objetos es(n

r

)· (r − 1)!

Justificamos brevemente esta proposicion. Sobre el conjunto de las r! permutaciones delos r elementos seleccionados definimos una relacion de equivalencia, donde dos permu-taciones son equivalentes si la segunda es obtenible a partir de la primera mediante unadeterminada rotacion. Ya que la clase de equivalencia de una permuatacion dada constade r elementos (que son sus r rotaciones posibles), el conjunto cociente tiene r!

r= (r − 1)!

elementos, que es precisamente el numero de permutaciones circulares para los r elementosselecionados. Por tanto el numero buscado es(

n

r

)r!

r=

(n

r

)(r − 1)!

Ejemplo 29. Se dispone de 20 bolitas de colores diferentes en cada una de las cuales se hataladrado un pequeno orificio. ¿Cuantos collares diferentes pueden resultar si empleamossolo 15 bolitas?Respuesta: (

20

15

)· 14!

Ejemplo 30. ¿De cuantas formas pueden sentarse seis personas en torno a una mesa cir-cular?Respuesta: 5! = 120¿Y si dos personas no desean sentarse en asientos contiguos?Llamemos a dichas personas A y B. El numero de formas en las que A Y B no se sientanen asientos contiguos es igual a 120 menos el numero de formas en las que siempre A y Bocupan posiciones consecutivas. Ahora bien, ¿de cuantas formas se pueden sentar seis per-sonas A,B,C,D,E y F en torno a una mesa circular de modo que A y B ocupen posicionesconsecutivas?Este nuevo problema se resuelve suponiendo que A y B son una misma persona, digamosG, y sentando a G,C,D,E y F entorno a una mesa circular, lo cual puede realizarse de4! = 24 formas posibles. Para cada una de estas disposiciones, si reemplazamos G por A,B

12

o bien por B,A obtenemos una disposicion en la que A y B ocupan posiciones contiguas;por consiguiente el numero de formas en las que A y B ocupan posiciones contiguas es iguala 2 · 4! = 2 · 24 = 48. Finalmente obtenemos que el numero de formas de sentar a las seispersonas de modo que A y B no ocupen posiciones adyacentes es igual a 120− 48 = 72.

La resolucion del problema anterior ilustra otra tecnica tıpica en Combinatoria. A veces,a la hora de calcular el cardinal de un subconjunto A de un conjunto X, resulta mas facilcalcular el cardinal del conjunto complementario A.

Ejemplo 31. ¿Cuantos numeros naturales se escriben en base 10 con a lo sumo cincocifras siendo al menos una de ellas igual a 1?Sea A el conjunto formado por dichos numeros y sea X el conjunto de todos los numerosnaturales que en base 10 se escriben con a lo sumo cinco cifras. Entonces A = X \ Aes el subconjunto de X formado por aquellos numeros en cuya representacion no apareceel dıgito 1. Por el Principio del Producto es inmediato que |X| = 105 y |X \ A| = 95.Finalmente obtenemos |A| = |X| − |A| = 105 − 95 = 40951.