Divisibilidad

Conceptos básicos
El concepto fundamental en el que estaremos interesados ahora, será el de divisibilidad, por ello introduciremos la siguiente definición .
Definición 1.1 Sean a y b dos números enteros. Decimos que a divide a b (lo que simbolizamos con a|b) si existe un entero c tal que
b = ac. Esto equivale a decir que b es múltiplo de a , o a que la división b ÷a no deja residuo.
Si a no divide a b, escribimos:



Esto es lo mismo que decir que la división b ÷a deja residuo.
Ejemplos:
3|12 pues 12 =4×3
4|20 ya que si c=5, 20= 4c.
3|0 dado que 0=3c cuando c=0




Para cualquier entero a, a+1 | a² -1, ya que a ² -1 =(a +1) × k con k = a-1.
De la definición podemos derivar ciertas propiedades básicas:
1.Todo número se divide a sí mismo: a | a
2.Si a | b, entonces a |-b. Como 4 |8 (8=4×2), 4|-8. (pues -8=4×(-2)).
3.Si a | b, entonces a |bc para todo entero c. (4|12, entonces 4|12×5).
4.Si a y b son positivos y a |b, entonces a≤ b.
5.Si a | b y b | c entonces a | c. Ejemplo: 2|10 y 10 |30, entonces 2 |30.
Si a |b y a |c entonces a | (b+c).Así 2|4 y 2|6 implica 2 | (4+6)
La prueba de la última propiedad es típica de las pruebas de problemas de divisibilidad, así que se incluye para tener un modelo.
Prueba. Si a | b y a |c, entonces existen números enteros m y n tales que b =am y c= an. Entonces b+c = am+ an = a (m+n). Como b + c = ak cuando k = (m+n), la definición de divisibilidad nos dice que a | b +c. La prueba queda terminada.
La prueba anterior puede extenderse a varios sumandos:
Teorema 10.1 Si a |x₁ ,a |x₂, a |x₃,... a |x_n, entonces
A | (c₁x₁ +c₂x₂+c₃x₄+...+c_nx_n)
Para cualquier combinación de enteros, c₁,c₂,c₃,...c_n.

Dados a y b, un número de la forma ax + by se denomina una combinación lineal de a y b. En general dados x₁,x₂,...,x_n, un número de la forma u₁x₁ + u₂x₂+...+u_nx_n se conoce como una combinación lineal de los números x₁,x₂,....x_n. Entonces el teorema anterior lo enunciamos: “Si un número divide a un conjunto de enteros, divide a cualquier combinación lineal de los mismos.”

Por ejemplo dado que 3 |6 , 3|12 y 3|15, aplicando el teorema anterior con c₁=5, c₂= -7, c₃=2, deducimos que 3 | (6 ×5 + 12× (-7) +15 ×2 )
El concepto de divisibilidad puede generalizarse de la siguiente manera:
Teorema 10.2 (Algoritmo de la división)Sean a y b dos enteros con b > 0. Entonces existen enteros únicos c y r tales que a = bc+r y 0≤ r < b.
Lo importante a notar es que el residuo es positivo y cumple o ≤ r < b, y si



Entonces 0 < r < b. Básicamente, el entero c es el cociente de la división a÷b y r es el residuo.
Ejemplos:A= 12, b= 5. a=b×2+2.
A= 38, b= 8. a=b×4+6.
A= 20, b= 4. a=b×5+0.
A= 7, b= 10. a=b×0+7.
A= -15, b= 4. a=b×(-4)+1.
A= 18, b= -5. a=b×(-3)+3.
A= -14, b= -3. a=b×5+1.

Este algoritmo adquirirá mayor importancia en la siguiente sección.
Definición 10.2
Un número positivo se llama número primo si tiene solo dos divisores positivos distintos. Un número mayor a 1 que no es primo se denomina compuesto.
Teorema 10.3
Todo número mayor a 1 es divisible por algún primo.
Prueba. Sea n >1. Supongamos que no es divisible por ningún primo. En particular, n mismo no puede ser primo pues seria divisible entre si mismo. Como n no es primo, tiene algún divisor positivo d₁ distinto de 1 y n, es decir 1 < d₁ < n. Pero d₁ no puede ser primo porque dividiría a n. Entonces existe un d₂ que divide a d₁ tal que 1 < d₂ < d₁ < n. Como d₂ no puede ser primo porque divide a n, repetimos el argumento con d₂ para obtener un d₃ tal que 1 < d₃ < d₂ < d₁ < n. Como d₃ no puede ser primo existe un d₄ que divide a d₃ y así sucesivamente. Esto lleva a una contradicción pues no es posible continuar indefinidamente este proceso ya que entre 1 y n solo hay un número finito de términos. Por tanto n debe ser divisible entre algún primo.
Este tipo de pruebas se conoce como por descenso infinito y se basa en que si la condición pedida no se cumple se crea una sucesión infinita decreciente de elementos positivos, lo cual es imposible porque los enteros positivos tienen elemento mínimo. Las pruebas por descenso infinito fueron ampliamente usadas por Fermat.
El teorema anterior será usado en muchas pruebas en la siguiente forma “Si n es un número compuesto , hay un primo p que lo divide”.
Sea n un entero mayor a 1. Si n es primo, es igual a sí mismo. Si no es primo existe un primo p₁ que lo divide y entonces p = p₁n₁. Si n₁ es primo, n es igual a un producto de primos, de lo contrario existe un primo p₂ que divide a n₁ y así p=p₁p₁n₂. Si n₂ es primo, n es igual a un producto de primos, en caso contrario existe un primo p₃ que lo divide. Continuamos aplicando este argumento y construimos una sucesión n₁,n₁,n₃... decreciente de enteros positivos que debe terminar, es decir en algún momento n_k es un número primo. De esta manera ya probamos el siguiente teorema:
Teorema 10.4 Todo número mayor a 1 puede escribirse como producto de primos.
Es decir, un número n> 1 puede escribirse de la forma:

Donde cada p_j es un número primo.
Por ejemplo 12=2²×3, 60=2²×3×5, 101=101,99=3²×11. Ahora bien, al igual que 12= 2×6=3×4 tiene varias factorizaciones, nada nos garantiza que un número dado no se pueda factorizar de maneras diferentes en producto de primos (sin importar el orden). Pero después probaremos que para cada número dado la factorización en primos sí es única. Así podemos establecer el siguiente teorema (aunque la prueba de la unicidad la posponemos hasta tener las herramientas necesarias).
Teorema 10.5 (Teorema fundamental d la aritmética)Todo número se puede factorizar de manera única como producto de primos.
Para finalizar la sección probaremos uno de los resultados clásicos de la teoría de los números y que fue establecido hace cerca de 2000 años.
Teorema 10.6 (Euclides) Hay una cantidad infinita de números primos.
Prueba. Supongamos que hay una cantidad finita de números primos y sea p₁,p₂,...p_n la lista de todos ellos. Consideremos el número p₁×p₂×... ×p_n+1. Como ese número es mayor a 1 hay un primo que lo divide. Sea p tal que p | p₁×p₂×... ×_np+1. Como p | p×p₂×... ×p_n+1 se sigue que p |1 , lo cual es imposible. Concluimos que debe existir una cantidad infinita de primos.

9.1 Problemas y ejercicios

1.-Demostrar que la suma de los ángulos de un polígono de n lados es ( n-2) 180 º.
2.-Demostrar las siguientes identidades:
3.-Verifica que
4.-Todos los números de la forma 1007, 10017,100117,1001117,... son divisibles entre 53.
5.-Se tienen 2n puntos, y de todos los segmentos que los unen se colorean n² +1. Prueba que existen 3 puntos tales que los 3 segmentos que los unen están pintados.

Inducción matemática

Consideremos por un momento el polinomio p (x) = x + x+41. Sustituyendo x = 1,2,3... obtenemos los valores
Observemos que todos los valores obtenidos son números primos ¿Será cierto que para cualquier entero x el valor que se obtiene es un número primo?

Responderemos esta pregunta más adelante. Veamos otro problema de ejemplo.

Considera un triángulo rectángulo isósceles con catetos iguales a 1 sobre la hipotenusa de éste se levanta un segundo triángulo de cateto igual a 1, sobre la hipotenusa de este nuevo triángulo se levanta un tercer triángulo rectángulo y así sucesivamente. Encuentra la longitud de la hipotenusa del triángulo número 1998.

Usando el teorema de Pitágoras obtenemos que la primera hipotenusa vale √2, la tercera vale √3, la cuarta vale √4. Si este patrón continuara, obtendríamos que la hipotenusa del triángulo 1998 sería √1999. Pero, ¿podemos asegurar que este patrón realmente continúa?

El método de inducción matemática.

En muchos problemas necesitamos demostrar que una propiedad que depende de un número entero n se cumple para todos los enteros positivos. La técnica canónica que usaremos para lograr este objetivo se denomina inducción matemática.
En su forma simple, este método consta de dos etapas:

1.Se verifica que la propiedad se cumple para un valor inicial ( n=1).
2. Se demuestra que si la propiedad se cumple para algún entero k, entonces se cumple para el siguiente (k +1).

Una vez verificados esos 2 requisitos, podemos verificar que la propiedad se cumple para n = 1, 2,3,....

Veamos un ejemplo práctico antes de analizar porque funciona el método. En el problema del triángulo, queremos comprobar la propiedad
La hipotenusadel triángulo n es √(n +1).
Notemos que la propiedad depende de un y sólo un número entero, el valor de n.Esto es un indicador de que el método de inducción matemática podría ser apropiado.
La primera etapa pide mostrar que la propiedad se cumple para n=1, es decir , que la hipotenusa del primer triángulo es √2, lo cual es cierto en virtud del teorema de Pitágoras.
En la segunda etapa, imaginamos que ya sabemos que la propiedad se cumple para algún valor de k ( o sea la hipotenusa del triángulo k es √(k +1) ).Queremos probar que la propiedad también se cumple para k +1 (o sea, la hipotenusa del triángulo k+1 es √(k +2)).
Para calcular la hipotenusa del triángulo k +1 aplicamos el teorema de Pitágoras. Uno de sus catetos es 1, y el otro es la hipotenusa del triangulo anterior, el cual estamos suponiendo que vale √(k +1). Entonces

Comprobamos que si la propiedad se cumple para un entero k, se cumple para k +1 . Entonces la inducción matemática nos garantiza que la propiedad siempre se cumple, y ya somos capaces de asegurar que la hipotenusa del triangulo 1998 es √1999.
¿Por qué funciona el método?
Este proceso puede compararse a una escalera, donde la primera etapa nos da el primer peldaño, y la segunda etapa construye nuevos peldaños a partir de los anteriores. La primera etapa prueba que la propiedad se cumple para n=1, dándonos un punto de partida. La segunda etapa dice que si sabemos que la propiedad se cumple para algún entero, se cumple para el siguiente.¡ Pero la primera etapa nos dice que la propiedad se cumple para n =1! Entonces podemos asegurar que la propiedad se cumple para el siguiente entero, es decir n =2. Como la propiedad se cumple para n=2, la segunda etapa nos dice que se cumple para el siguiente n =3.Como ahora ya sabemos que se cumple para n=3 ,la segunda etapa nos dice que la propiedad se cumple para n =4, y así sucesivamente.
Esto basta para asegurar que la propiedad se cumple para n= 1,2,3,4... ya que no importa que número escojamos, en algún momento la escalera “alcanza” ese número.
Variantes del método de inducción.

El análisis del método de inducción sugiere algunas variantes. Por ejemplo, en la primera etapa , el valor inicial no necesariamente tiene que ser 1. Si en la primera etapa probamos (por ejemplo) que la propiedad se cumple para n =10 , el método de inducción nos garantiza que la propiedad se cumple únicamente para n= 11,12... y si probásemos que la propiedad se cumple para n = -3, el método de inducción nos garantiza que la propiedad se cumple para n = -3,-2,-1, 0, 1,2,... Sin embargo, en la mayoría de los problemas el paso inicial es n =0 o n = 1.
La segunda etapa también es susceptible de modificación. Un ejemplo sería probar que si la propiedad se cumple para algún entero k , se cumple para k +2 . En este caso suponiendo que el valor inicial fuese n =1, habríamos que la propiedad se cumple para n = 1, 3,,5,7... ( Cerciorarse de este hecho). Sin embargo, las modificaciones a la segunda etapa son bastante raras, y con frecuencia pueden evitarse escogiendo adecuadamente las variables de la inducción.

Importancia de las dos etapas.
Si bien es cierta que la segunda etapa es la que “demuestra” que la propiedad se cumple, la primera tiene una importancia fundamental. Un error común es dar por sentada la primera parte del método y comprobar únicamente la segunda. Este es un error que se debe evitar, pues es necesario tener un punto inicial para que la inducción pueda funcionar. Consideremos el siguiente ejemplo.
En el problema del triángulo, imaginemos que equivocadamente hubiéramos notado que la hipotenusa del triangulo n era √(n-1).
En la segunda etapa suponemos que la propiedad se cumple para un k e intentamos probar que también se cumple para un k +1. Usando el teorema de Pitágoras:

Y concluimos que la hipotenusa del triangulo n es ! √(n-1) en vez de √(n+1)!
El error provino de omitir la primera etapa, que es la que nos provee de una base verdadera para que la segunda etapa construya una escalera de verdades.
Analicemos ahora el problema del polinomio. Después de probar los primeros 20 números obtenemos siempre números primos ( esto equivaldría a realizar la primera etapa), sin embargo, como nos es difícil probar la segunda parte, nos vemos tentados a decir “ después de hacer muchos casos”, concluimos que el polinomio siempre devuelve números primos”. Este es un error aún más grande que el anterior ,pues
P (41) = 41₂ +41 +41 = 41 (41 +1+ 1)= 41× 43
Y tenemos que el polinomio no siempre genera números primos. La moraleja es que si algún patrón parece repetirse de manera constante, es bueno señalarlo, pero hasta no realizar ambos pasos de la inducción no podemos garantizar que la propiedad siempre se cumple (aunque la comprobemos en muchos casos particulares).

8 Principio de las casillas

El principio de las casillas es también conocido como el principio del Palomar se enuncia como sigue:

(Principio de las casillas)Si se dispone de n casillas para colocar m objetos y m >n, entonces en alguna casilla deberán colocarse por lo menos dos objetos.

Este principio puede parecer tan obvio a simple vista que parecería un poco extraño estudiarle en un capitulo aparte. Pero como veremos, una gran variedad de problemas combinatorios pueden atacarse con este principio, especialmente aquellos en los que se desea demostrar la existencia de alguna situación. Veamos unos ejemplo muy sencillos.

Ejemplo. En cualquier grupo de seis personas, hay tres personas que se conocen todas entre sí o tres personas que no se conocen ninguna a la otra (asumiendo que si x conoce a Y entonces Y también conoce a X).
Consideremos una persona de las seis, digamos a A. Las restantes cinco personas caen en dos clases: conocen a A o no conocen A. Por principio de las casillas, una de esas clases debe tener al menos tres personas.
Supongamos que hay al menos tres personas que no conocen a A, si algún par de ellas no se conocen, junto con A ya son personas que no se conocen entre sí, y en el caso restante las tres personas se conocen todas entre sí. Un argumento similar se ocupa en el caso cuando las tres personas conocen a A.

Ejemplo. Algunos de los cuadritos de una cuadricula de 3 × 7 se pintan de negro y los otros se dejan en blanco. Probar que forzosamente las líneas de la cuadrícula forman un rectángulo en cuyas cuatro esquinas los cuadraditos tienen el mismo color (los cuatro blancos o los cuatro negros).
Solución. Supongamos que tenemos una cuadricula pintada de manera tal que no se forma el rectángulo con las esquinas del mimo color.Simbolicemos por N al color negro y por B al blanco, y observemos que los cuadritos de una columna pueden haber quedado pintados según las siguientes8 posibilidades :p₁=NNN,p₂=NNB,p₃,p₄=BNN,p₅=NBB,P₆=BNB,p₇=BBN,p₈=BBB.

Supongamos que una de las columnas esta pintada según la posibilidad p ₁; entonces con cualquiera de las posibilidades en que la columna tiene dos N`s se formara un rectángulo con las esquinas negras, así que ninguna columna está pintada así; pero entonces las columnas están solo pintadas según las según las posibilidades p ₁, p ₅,p ₆,p ₇,p ₈; como el número de columnas es 7, entonces el principio de las casillas nos dice que debe haber dos columnas iguales, pero aquí también, por el principio de las casillas, como son tres cuadritos en cada columna y sólo dos colores hay un color que se repite, y entonces es obvio que se forma un rectángulo con las esquinas del mismo color. Concluimos entonces que la posibilidad p ₁ no aparece. Lo mismo ocurre al considerar la posibilidad p ₈. Entonces ninguna de las posibilidades p ₁ y p ₈ aparece; pero así sobran sólo 6 posibilidades, con lo cual , otra vez aplicando el principio de las casillas, tenemos dos columnas iguales, y de ahí una contradicción.

7.2 El triángulo de Pascal y el teorema del binomio

Acomodemos en una tabla los valores de C (n,k) con los valores de n por filas y los de k por columnas

La identidad de Pascal nos dice que todo elemento del triangulo es igual a los dos que se encuentran directamente sobre de ella .Esto quiere decir que si construimos un arreglo triangular de números (comenzando con el 1 en la primera fila) de modo que toda entrada sea la suma de las dos que están encima de ella, los números que aparecen son precisamente los coeficientes binomiales. El arreglo que se forma se conoce como triángulo de Pascal.
El triángulo de Pascal encierra muchas relaciones numéricas, por ejemplo, la suma de todos los números en la n- ésima fila es 2ⁿ equivalente al teorema 7.3. Fijémonos ahora en la suma de las “diagonales”. En la siguiente figura, consideremos las diagonales cuarta (en verde), quinta (en rojo) y sexta (en azul) contando desde cero. Sus sumas son respectivamente 1+3+1=5, 1+4+3=8 y 1 +5+6+1=13.
Entonces tenemos que la suma de los elementos de la diagonal verde y la roja es igual a la suma de los elementos de la diagonal azul. Esto sucede en general si d _rdenota la suma de los elementos de la r-ésima diagonal, entonces:

d_r+1 =d _r + d_r-1 .

Además, dado que d₀= 1 y d₁ =1.Los números que se forman de esta manera se conocen como números de Fibonacci. Decimos entonces que la suma de los números en la r-ésima diagonal del Triángulo de Pascal es igual al r-ésimo número de Fibonacci.Otra relación interesante es la propiedad hexagonal

Escojamos un número en el interior, por ejemplo el 10 = C (5,3). Fijémonos en el hexágono de números que se forma a su alrededor con 6= C(4,2), 4 =C (4,3), 10=C (5,2), 5=C(5,4) ,20=C(6,3), 15=C (6,4).Si se multiplican vértices alternados de este hexágono se obtiene en ambos casos la misma cantidad:
4×10×16= 600= 6 ×5×20.
Esta propiedad también es válida formando hexágonos de este tipo en cualquier parte del triángulo. Sin embargo, quizás la relación más interesante en el triángulo de Pascal se relaciona con el teorema del binomio.
Consideremos el producto (a+b⁵). Al desarrollarlo, ¿con qué coeficiente aparece ab ? Aquellos que conozcan el teorema del binomio dirán enseguida: El coeficiente es C (5,3).¿Pero porque sucede así? Uno podría decir: “porque si desarrollamos (a+b)⁵=a⁵ +5ab⁴ + 10a²b³ + 10a³b² +5ab⁴ +b⁵ +vemos que el coeficiente es 10”.Pero esa respuesta en realidad no esta diciendo la razón de porque el coeficiente se calcula precisamente como C (5,3).
Para analizar la situación vamos a diferenciar los factores:
(a+b)⁵= (a₁+b₁) + (a₂+b₂) +( a₃+b₃) +( a₄+b₄) +( a₅+b₅) .
Donde las a_i y las b_j, son iguales entre sí.pero que estamos considerando como diferentes por ahora. Si efectuamos el producto de la derecha vemos que los términos que cuentan con ab³² son:
a₁a₂a₃b₄b_{5 ,} a₁a₂b₃a₄b₅ , a₁a₂b₃b₄a₅ , a₁b₂a₃a₄b₅ , a₁b₂a₃b₄a₅ ,

a₁b₂a₃a₄b₅ , b₁a₂a₃a₄b₅ , b₁a₂a₃b₄a_5, b₁a₂b₃a₄a_{5 ,} b₁b₂a₃a₄a₅ .

En otras palabras, si efectuamos la multiplicación “larga” de los cinco factores, los 10 términos de arriba son los que quedan en la columna de ab. Una manera de contar la lista consiste en fijarnos que siempre hay precisamente cinco posiciones de las cuales dos son ocupadas por b`s y tres por a`s. Entonces, dependiendo si nos fijamos en las a`s o en las b`s obtenemos que hay C (5,3) o C (5,2) que en ambos casos es 10.

Ejercicios y problemas

1.-Interprete combinatoriamente la siguiente afirmación:

2.-Demuestre la propiedad hexagonal del triángulo de Pascal
3.-Demuestre que la suma de los elementos en la r-ésima diagonal del triángulo de Pascal es precisamente el r- ésimo número de Fibonacci.
4.-Demuestre que

7 Coeficientes binomiales

En el capitulo anterior, vimos que C (n, k) representa el número de subconjuntos de k elementos que tiene un conjunto con n elementos. Además, vimos que se puede calcular mediante la formula

A lo largo de este capitulo veremos una gran variedad de otras propiedades, pero el enfoque será distinto al anterior. Para poder desarrollar las habilidades de demostración en combinatoria, nuestras pruebas no se basaran en el cálculo explicito con la fórmula, sino en el hecho de que son el número de k-subconjuntos de un conjunto con n elementos. Así, aunque podemos demostrar las propiedades desarrollando la formula con factoriales, de este modo las combinaciones nunca serán más que herramientas de conteo para nosotros, mientras que el uso de su definición como número de subconjuntos nos permite adquirir nuevas habilidades que nos serán extremadamente útiles al momento de enfrentarnos a la resolución de problemas.
7.1 Identidades básicas.
Al usar las combinaciones en el capitulo anterior, habían unos casos especiales (cuando los subconjuntos son de un elemento, cuando se escoge todo el subconjunto), que tal vez notaste. A continuación los enunciamos para poder usarlos libremente

Dado que sólo hay una manera de escoger todos los elementos, y solo una manera de no escoger ninguno, tenemos que C (n,n) = C (n,0)=1 . Por otro lado, si un conjunto tiene n elementos y queremos escoger uno, tenemos n opciones. Así C (n,1)=n.

Para demostrar la segunda, notamos que cada vez que escogemos k elementos para formar el subconjunto, estamos determinando a los n-k que no estén en el subconjunto. Y viceversa, escoger n-k que no estén en el subconjunto automáticamente determina a los k que si están. Si para cada una elección de unos hay una elección correspondiente de los otros, el total en ambos casos es el mismo ( igual número de formas de escoger los k que sí van a estar y los n-k que no van a estar). Esto es,

La demostración dada es un ejemplo de como se evita la aplicación mecánica de la fórmula, usando un argumento basado en le definición. El siguiente resultado ya no es tan simple y a la vez es muy interesante, se conoce como la identidad de pascal.

Hagamos un análisis previo .Supongamos que S = { a₁,a₂,a₃,...,a_n }es el conjunto que tiene n elementos, con los que queremos formar subconjuntos con k elementos. Fijémonos en un elemento cualquiera, digamos a₁. De todos los conjuntos que queremos formar, algunos contendrán a a y otro no, sin embargo
Total de subconjuntos con k elementos =
(subconjuntos con k elementos que contienen a a₁)
+ (subconjuntos con k elementos que no contienen a a₁).

El total es, por definición C (n,.k).Ahora queremos contar cuantos de ellos contienen a a₁.
Si uno de tales conjuntos tiene a a₁, hay que llenar k-1 posiciones con cualquiera de los otros n-1. En otras palabra, como ya sabemos que a₁ es un elemento, hay que escoger k-1 de los n-1 restantes, lo que se puede hacer de C (n-1,k-1) formas.
Para formar un conjunto que no contiene a a₁, hay que escoger k elementos de los n-1 que son distintos a a. Esto lo podemos hacer de C (n-1,k)formas. Entonces, por las observaciones de arriba, concluimos que C (n,k)= C (n-1,k-1) + C (n-1,k)
Sabemos contar cuantos subconjuntos de tamaño k tiene un conjunto de n elementos, ¿pero cuántos subconjuntos tiene en total? Hay un conjunto con 0 elementos (el vacío), hay n con un solo elemento, hay C (n,2), que tienen dos elementos,etc. En otras palabras , queremos calcular la suma
Como hemos estado haciendo, analizaremos primero un caso particular como ejemplo. Imaginemos que tenemos el conjunto S= { p,q,r,s,t}. Como tiene 5 elementos, queremos calcular C (5,0)+ C(5,1)+C(5,2)+C(5,3)+C(5,4)+C(5,5). La idea que usaremos será “representar” los subconjuntos con sucesiones de unos y ceros del siguiente modo: consideramos cinco espacios _ _ _ _ _ y escogemos un subconjunto; si un elemento aparece en el conjunto escribimos un 1 en su posición, y de lo contrario ponemos un cero.
Ejemplo: Si el conjunto escogido fuera {q,s,t , escribiríamos 01011 porque solo el segundo, el cuarto y el quinto elementos están en el subconjunto. Si el subconjunto fuera { p,q} la sucesión seria 11000, y al subconjunto vacío le toca 00000. También es claro que si escogemos cualquier sucesión de longitud cinco hecha de unos y ceros, representa algún subconjunto. Por ejemplo la sucesión 10101 es el subconjunto {p,r,t} y la sucesión 00001 es el subconjunto { t}.
Así cada sucesión es un subconjunto y cada subconjunto una sucesión. Entonces contar subconjuntos es lo mismo que contar sucesiones. El principio de la multiplicación nos dice que hay 2⁵ de tales sucesiones. Por tanto, hay 32 subconjuntos.
No había nada especial en que el subconjunto tuviera 5 elementos. Si tuviese n elementos, usaríamos sucesiones de longitud n. El argumento es completamente análogo. De nueva cuenta resumimos nuestro análisis en un teorema.
Teorema 7.3
Un subconjunto con n elementos tiene 2 Un subconjunto con n elementos tiene 2ⁿ subconjuntos diferentes.

6.3 Combinaciones

Para terminar esta sección, consideramos el siguiente tipo de problemas: “Dada una colección de n objetos. ¿De cuantas maneras se peden escoger k de ellos?
Veamos un ejemplo concreto. El conjunto a considerar será A = {a,e,i,o,u} y nos preguntamos de cuantas maneras se pueden escoger tres vocales. Un primer intento diría:
Como hay que formar arreglos de tres letras a partir de un conjunto que tiene 5 elementos, hay P (5,3) = 60 arreglos.Sin embargo, el razonamiento anterior es incorrecto. Para ver el porqué, imaginemos que las letras escogidas, son, a, i, u. Estas forman los arreglos aiu,aui, iua,iau,uia,uai. Entonces seis diferentes arreglos representan la misma elección . El problema es que aquí no se nos pide el número de arreglos, sino simplemente el numero de formas de escoger las letras. Es decir,no importa el orden.
Nuestro problema es, que si contamos arreglos, estamos contando seis veces el número que queremos. Esto es así porque cada vez que escogemos tres letras, hay 3! = 6 formas de revolverlas entre si .Si por cada grupo de 3 letras hay 6 arreglos, entonces el número que buscamos es un sexto del numero de arreglos. Entonces la respuesta que buscamos es 60/6 = 10.
¿Qué habría pasado si en vez de grupos de 3 hubiéramos formado grupos de cuatro?¿o de dos? ¿Y si en vez de un conjunto de 5 elementos hubiésemos comenzado con uno de 10 o de 20?
Para encontrar la formula, supongamos que comenzamos con un conjunto de n elementos y queremos contar de cuantas formas se puede hacer un grupo de k de sus elementos. Al igual que en el razonamiento anterior, comenzamos contando el numero de arreglos de tamaño k. El teorema 6.4 nos dice que este número es

Pero al igual que en el ejemplo, este no es el número que buscamos ya que varios arreglos pueden representar el mismo grupo. Pero ya sabemos que k objetos se pueden revolver de k! maneras entre si. Entonces el número de grupos es 1/ k! veces el número de arreglos. De este modo, el número de formas de escoger k elementos a partir de un conjunto con n elementos (sin importar el orden) es
Un subconjunto de k elementos de un conjunto con n se llama a veces una combinación, por lo que al número calculado se le llama combinaciones de n en k (o “n en k” por brevedad). También se le da el nombre de coeficiente binomial por razones que aprenderemos más adelante. Se representa de varias maneras algunas de las cuales son entre otras, son:
Resumimos Nuestro trabajo n el siguiente teorema.
6.5Combinaciones de n en k. El numero de subconjuntos con k elementos de un conjunto con n elementos es
Las combinaciones juegan un papel central n la combinatoria, por lo que dedicaremos todo el capitulo siguiente al estudio de sus propiedades. Por ahora únicamente nos interesa su aplicación al conteo (cálculos numéricos) .

Ejemplo. El poker se juega con 32 cartas, cada una de las cuales tiene un “número” que puede ser 7,8,9,10,J, Q ,K,A y un símbolo (o “palo”) que puede ser ♠, ♣,♥,♦.De este modo, (10, ♥) representa el diez de corazones. Un jugador recibe 5 cartas.

1.Si de las cinco cartas, hay 3 de u mismo número y dos de otro, ¿de cuántas maneras se puede hacer?
2.Si el jugador recibe cuatro cartas del mismo número (por tanto la última de distinto ¿Cuantos casos posibles hay?
3.¿De cuantas formas puede recibir sus cartas de modo que las cinco sean del mismo palo?

1.Primero usamos el principio de la multiplicación para ver que hay 8 × 7= 56 formas de escoger que número se va a repetir 3 veces y cual se va a repetir dos (porque en total hay 8 números .
Ahora para cada una de esas elecciones, hay que escoger tres cartas de las cuatro que tienen el primer número. Esto puede hacerse de C(4,3) maneras. Para formar las dos restantes , escogemos dos de las cuatro que tienen el segundo número, lo cual puede hacerse de C (4,2) formas. El total de formas es
2.-Hay 8 formas de escoger el número que se repite cuatro veces (que es lo mismo que hacer C (8,1)). La carta restante necesariamente es de un número distinto, porque solo hay cuatro de cada número, así que la podemos escoger de cualquiera de las 28 restantes (en total son 32 cartas) por lo que el número de casos posibles es 8 × 28= 224.
3. El palo tiene cuatro opciones (que es lo mismo que (C 4,1)). De las 8 cartas de cada palo hay que escoger 5. Entonces el total es