Números Combinatorios

Mariano Juncal

Colaborador-Varias OFO - Medalla de Bronce-OFO 2015
Mensajes: 38
Registrado: Sab 16 Oct, 2010 6:49 pm
Medallas: 2

Números Combinatorios

Mensaje sin leer por Mariano Juncal »

Problema 1:

¿Cuántas números de $4$ cifras se pueden formar con los números $1$, $2$,$3$ y $4$, si no se puede repetir ninguna cifra? ¿Y si se puede?


Para la segunda parte, vemos que cada cifra tiene $4$ opciones posibles, entonces la cantidad de números será, al haber $4$ cifras:
$4\times 4 \times4 \times4=4^4$


En general, si yo tengo $k$ cosas para hacer, y $n$ opciones distintas para cada cosa, la
cantidad total de posibilidades es $n^k$

En el ejemplo anterior, $n=4$, $k=4$, y las cosas para hacer eran elegir un numero para cada lugar o cifra.


Para la primer parte, vemos que para la primera cifra (unidades de mil), hay $4$ opciones de números a elegir, que pueden ser $1$, $2$, $3$ o $4$. Para la segunda cifra (centenas), ya no hay $4$ opciones, sino $3$, porque uno de los números ya fue usado para la primera cifra. Ahora, para las decenas, quedan sólo $2$ opciones, y para la unidad $1$. Es decir, la cantidad de números de $4$ cifras distintas formados por los números $1$, $2$, $3$ y $4$ es:
$4\times 3 \times 2 \times 1=24$.

A este número se lo escribe $4!$ y se lee cuatro factorial.
En general, $n!=1 \times 2 \times 3 \times \cdots \times (n-1) \times n$, es decir, $n!$ es el producto de todos los enteros desde $1$ hasta $n$. Los factoriales se usan muchísimo en combinatoria, como vamos a ver más adelante.

¿Pero qué pasa si yo tengo, por ejemplo, $k$ cajas, y tengo $n$ objetos distintos para meter, y tengo que meter exactamente uno en cada caja, cuántas formas hay?

Veámoslo con un ejemplo:

Tengo $3$ cajas, y tengo $5$ cosas para meter, y tengo que poner $1$ sola cosa en cada caja, ¿cuántas formas distintas de hacer esto hay?

Para la primer caja, tengo $5$ posibilidades, para la segunda tengo $4$, ya que una de las cosas la usé en la caja anterior, y ahora, para la tercer caja, tengo $3$, ya que otras $2$ fueron usadas en las primeras dos cajas. El total sería entonces $5\times 4\times 3 = 60$



¿Qué pasa si tengo $5$ cajas y $7$ cosas?

La cantidad de posibilidades sería, entonces,$7\times 6\times 5\times 4\times 3 = 2520$ formas.

Veamos si podemos generalizarlo para $k$ cajas, y $n$ objetos, con $k\leq n$ . Cabe aclarar que $k$ no puede exceder a $n$, porque entonces tendríamos más cajas que objetos, y quedarían cajas vacías, y la idea es meter un objeto en cada una.

La cantidad de posibilidades es: $n \times (n-1)\times (n-2) \times \cdots \times (n-k+1)$, ya que para la primera caja tenemos $n$ posibilidades, para la segunda tenemos $n-1$ porque ya usamos una, para la tercera tenemos $n-2$ y así siguiendo, para la $k$-ésima caja, es decir, para la ultima, tenemos $n-k+1$ (para la primera no restamos nada, para la segunda restamos $1$ porque ya fue usado ese objeto en la primer caja, para la tercera restamos $2$…y así, para la caja $k$, restamos $k-1$, es decir, hay $n - (k-1) = n - k + 1$ posibilidades para la caja en la posición $k$ (la última)

Entonces, como dijimos, la cantidad de posibilidades es $n \times (n-1)\times (n-2) \times \cdots \times (n-k+1)$.

Pero esto se puede escribir de otra forma, ya que si nos fijamos, esto es $\frac{n!}{(n-k)!}$ ya que al producto de los primeros $n$ enteros, le sacamos el producto de los primeros $n-k$ enteros y queda el producto de los enteros, desde $n-k+1$ hasta $n$, que era nuestro resultado.

Ahora, veamos si esto se cumple en los ejemplos que dimos:

Con $3$ cajas y $5$ cosas nos daba $60$, y efectivamente $60= \frac{5!}{2!}$, ya que $5 \times 4\times 3 = \frac{5 \times 4 \times 3 \times 2 \times1}{ 2 \times 1}$, es decir, estamos tachando lo que nos sobra.

Con $5$ cajas y $7$ cosas, el resultado era $2520$, y también $2520 = \frac{7!}{ 2!}$
(el $2!$ en este caso es porque $7-5=2$, que seria el $n-k$, ya que en este caso $n=7$ y $k=5$)

Conclusión: Si yo dispongo de $n$ objetos, y $k$ cajas, con $k\leq n$, la cantidad de formas distintas de meter $1$ objeto en cada caja es $\frac{n!}{(n-k)!}$

Veamos un último ejemplo de esto:

¿Cuántos números distintos de $3$ cifras distintas puedo formar con los números del $1$ al $7$?

Para la primera cifra, tengo $7$ posibilidades, para la segunda $6$, y para la tercera $5$, y esto es $7 \times 6\times 5$, que es lo mismo que $\frac{7!}{4!}$

Acá los $n$ objetos serian los números del $1$ al $7$ ($n=7$), las $k$ cajas serian las posiciones del numero de $3$ cifras ($k=3$), y el total es $\frac{n!}{(n-k)!} = \frac{7!}{4!} = 210$.

Volvamos al tema de formar números. Es claro que si yo quiero formar números de $5$ cifras usando una vez cada número del $1$ al $5$, la cantidad de números que puedo formar es $5!$.

Pero, ¿qué pasa si yo quiero formar números de $5$ cifras, con $1,\: 1,\: 2,\: 3,\: 4$?

La cantidad no será $5!$, porque si lo fuera estaríamos tomando a los dos $1$ como números distintos. Entonces escribamos así a las cifras: $1,\: 1',\: 2,\: 3,\: 4$.

Supongamos que tenemos un número, por ejemplo, $121'34$. ¿Qué pasa si cambiamos de posición el $1$ con el $1'$? Obtenemos el $1'2134$, que en realidad es igual al anterior si sacamos el $'$ que usamos para diferenciarlos. Y a esos dos casos los estamos tomando como distintos en caso de decir que la cantidad de permutaciones es $5!$ Por lo tanto, la cantidad real final de permutaciones, es decir, la cantidad de números de $5$ cifras usando$1,\: 1,\: 2,\: 3,\: 4$ será de $\frac{5!}{2}$.

En realidad el $\frac{5!}{ 2}$ es $\frac{5!}{ 2!}$, que sería la cantidad total de permutaciones si los números fueran distintos, dividido la cantidad de permutaciones de los números iguales, que yo estaría contando como distintos si dejo así nomás el $5!$.

Para entender mejor este concepto, veámoslo con otro ejemplo:

Tenemos la palabra $HAMACA$, y queremos ver cuantas palabras distintas podemos formar moviendo las letras. Pintemos de color las $A$, así las distinguimos:

$HAMACA$

Ahora, tomemos una palabra cualquiera que se forme con esas letras, por ejemplo,

$CAHAAM$, y veamos qué pasa si vamos cambiando solamente las $A$ de lugar

Obtenemos las siguientes palabras equivalentes:

$CA_1HA_2A_3M$

$CA_1HA_3A_2M$

$CA_2HA_1A_3M$

$CA_2HA_3A_1M$

$CA_3HA_1A_2M$

$CA_3HA_2A_1M$

Estas seis palabras en sí son iguales, pero las estaríamos contando como distintas si dijéramos que la cantidad total de palabras que podemos formar es $6!$



Y esto pasaría con cualquier palabra, para cada palabra, habría $6$ formas de variar los colores de las $A$, y quedaría la misma palabra con los colores en otro orden. Por lo tanto, al $6!$, lo tenemos que dividir por $6$. Ese $6$ es en realidad un $3!$, que justamente es la cantidad de formas distintas de ordenar las tres $A$.

Ejemplos:

La cantidad de palabras distintas moviendo las letras de $CASA$ es $\frac{4!}{ 2!}= 12$,

$CASA$
$CAAS$
$CSAA$
$SACA$
$SAAC$
$SCAA$
$ACAS$
$ACSA$
$ASCA$
$ASAC$
$AACS$
$AASC$

¿Pero qué pasa por ejemplo si yo tengo la palabra $ANANA$?

Tendría que dividir el $5!$ por la cantidad de formas de ordenar las $A$ y la cantidad de formas de ordenar las $N$.

Así, el total nos queda $\frac{5!}{3!\: 2!}= 10$ palabras.

($3!$ Es la cantidad de formas de ordenar las tres $A$, y $2!$ las formas de ordenar las dos $N$, por eso dividimos por $3!2!$, ya que de otro modo estaríamos tomando a las $A$ como letras distintas, y lo mismo con las $N$)

(Empezamos por $5!$ porque $ANANA$ tiene $5$ letras, y si fueran todas distintas la cantidad de palabras que podríamos formar sería $5!$)

Un último ejemplo:

¿Cuántas palabras distintas puedo formar moviendo las letras de $MISSISSIPPI$?

$\frac{11!}{4!4!2!} = 34650$

$11!$ porque son $11$ letras en total, y dividimos primero por $4!$ porque hay cuatro $I$, de nuevo por $4!$ porque hay cuatro $S$, y finalmente por $2!$ porque hay dos $P$.


Si esto lo usamos con números en vez de letras, es lo mismo, salvo que aparezca algún $0$, ahí la cosa cambia porque los números no pueden empezar por $0$, y tendríamos que dividirlo en casos.



Veamos un ejemplo de esto:

¿Cuántos números distintos de 6 cifras puedo formar con los dígitos $0,\: 1,\: 1,\: 2,\: 2,\: 3$?

Si empieza con 1, las otras 5 cifras son$0,\: 1,\: 2,\: 2,\: 3$, y se pueden ordenar de $\frac{5!}{2!}=60$ maneras

Si empieza con 2, las otras 5 cifras son $0,\: 1,\: 1,\: 2,\: 3$, y se pueden ordenar de $\frac{5!}{2!}=60$ maneras

Si empieza con $3$, las otras $5$ cifras son $0,\: 1,\: 1,\: 2,\: 2$, y se pueden ordenar de $\frac{5!}{2!\: 2!}=30$ maneras.

El total sería entonces $30 + 60 + 60 = 150$



Problema 2: Soy un jeque árabe, y tengo $7$ camisas, pero tengo que elegir sólo $3$ para irme de viaje a Argentina, ¿de cuántas formas puedo hacerlo?

Asignamos un número a cada camisa, $1$ si la llevo, y $0$ si no la llevo. Si ponemos los $7$ números formando uno solo, obtenemos un número de $7$ cifras, que puede o no empezar por $0$. Ahora, ¿cuántas formas hay de formar números distintos moviendo sus dígitos?

En total son $7$ dígitos, tres son $1$, y cuatro son $0$, entonces la cantidad de posibilidades será $\frac{7!}{3!\: 4!}=35$


Otro ejemplo: Voy a una heladería, que dispone de $10$ gustos en total, pero en mi cucurucho entran $2$. ¿De cuántas formas puedo elegir los gustos, si no me importa qué gusto esta arriba?

Nuevamente, asignamos un $1$ a los gustos que elegimos, y un $0$ a los que no. En total van a ser $10$ números, dos $1$ y ocho $0$, por lo tanto la cantidad de formas de elegir $2$ gustos entre $10$ será de $\frac{10!}{8!\: 2!}=45$.

Generalizando, si yo tengo $n$ cosas distintas, y quiero elegir $k$, con $k\leq n$ , asigno un $1$ a $k$ de los números, y un $0$ a los restantes $n-k$. Esto se puede hacer de $\binom{n}{k}=\frac{n!}{k!\: (n-k)!}$
formas, ya que habrá $n$ números, $k$ unos, y $n-k$ ceros.

Los números de esa forma son conocidos como números combinatorios, y se escriben así:

$\binom{n}{k}=\frac{n!}{k!\: (n-k)!}$
y representan la cantidad de formas distintas de elegir $k$ cosas entre $n$,
sin importar el orden en el cual son elegidas.







Veamos un último ejemplo: Mariano es mi entrenador de olimpíadas, y me dijo que quedemos en vernos dos veces por semana, fines de semana incluidos. ¿De cuántas formas puedo elegir los dos días?

En la semana hay $7$ días, y tengo que elegir $2$, esto lo puedo hacer de $\binom{7}{2}=\frac{7!}{2!\: 5!}=21$ formas.


Para cerrar, vale la pena decir que estas son herramientas que ayudan a que salgan más rápido los problemas, pero no podemos esperar hacer todo en una cuenta con $20$ factoriales. En general se suele dividir el problema en partes, y usar estas cosas varias veces para calcular la cantidad de combinaciones de cada partecita.
Última edición por Mariano Juncal el Mié 02 Ago, 2023 10:15 pm, editado 2 veces en total.
14  
Avatar de Usuario
AgustinChenna.

OFO - Medalla de Bronce-OFO 2021
Mensajes: 188
Registrado: Mié 03 Ago, 2011 9:23 pm
Medallas: 1
Nivel: Ñandú

Re: Números Combinatorios

Mensaje sin leer por AgustinChenna. »

Es genial este apunte, gracias :D
Avatar de Usuario
amcandio

Colaborador-Varias
Mensajes: 312
Registrado: Sab 16 Oct, 2010 12:50 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Posadas, Misiones
Contactar:

Re: Números Combinatorios

Mensaje sin leer por amcandio »

AgustinChenna. escribió:Es genial este apunte, gracias :D
forro, todo para ganar posts y aparecer en el ranking xD
"Prillo es el Lanata de la trigonometria"
Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 404
Registrado: Mié 15 Dic, 2010 6:57 pm
Nivel: Exolímpico

Re: Números Combinatorios

Mensaje sin leer por Martín Vacas Vignolo »

Coincido jaja
[math]
Avatar de Usuario
amcandio

Colaborador-Varias
Mensajes: 312
Registrado: Sab 16 Oct, 2010 12:50 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Posadas, Misiones
Contactar:

Re: Números Combinatorios

Mensaje sin leer por amcandio »

jajaja picaron
1  
"Prillo es el Lanata de la trigonometria"
Avatar de Usuario
julianferres_

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Mención-OFO 2021
Mensajes: 388
Registrado: Sab 17 Sep, 2011 8:01 pm
Medallas: 4
Nivel: Exolímpico
Ubicación: Villa Ramallo, Buenos Aires

Re: Números Combinatorios

Mensaje sin leer por julianferres_ »

Jajaja... Ustedes también están haciendo lo mismo... :o
1  
Florencia
Mensajes: 8
Registrado: Lun 03 Sep, 2012 5:38 pm

Re: Números Combinatorios

Mensaje sin leer por Florencia »

No sé qué onda eso del ranking, pero muchas gracias Mariano, muy bueno y útil el post!!

2. Miguel hizo la lista de todos los números naturales tales que la multiplicación de sus dígitos es igual a 1920 y ningún dígito es igual a 1. Calcular cuántos números tiene la lista de Miguel.

Creo que parte de este problema sale con esto, en otro post pongo mi respuesta para ver si les parece o no...

De nuevo gracias!!
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Números Combinatorios

Mensaje sin leer por Joacoini »

amcandio escribió: Sab 26 Nov, 2011 6:05 pm
AgustinChenna. escribió:Es genial este apunte, gracias :D
forro, todo para ganar posts y aparecer en el ranking xD
Los usuarios de este foro no tienen límites.
3  
NO HAY ANÁLISIS.
Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Mención-FOFO 10 años OFO - Medalla de Bronce-OFO 2021
OFO - Medalla de Bronce-OFO 2022
Mensajes: 202
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 6
Nivel: 3
Ubicación: Córdoba, Córdoba

Re: Números Combinatorios

Mensaje sin leer por Tomás Morcos Porras »

Joacoini escribió: Mié 29 Ene, 2020 3:43 am
amcandio escribió: Sab 26 Nov, 2011 6:05 pm
AgustinChenna. escribió:Es genial este apunte, gracias :D
forro, todo para ganar posts y aparecer en el ranking xD
Los usuarios de este foro no tienen límites.
Absolutamente despreciable.
¿Mis intereses? Las várices de Winston Churchill.
Santiago Pizarro
Mensajes: 3
Registrado: Dom 25 Jun, 2023 12:27 am
Nivel: 1

Re: Números Combinatorios

Mensaje sin leer por Santiago Pizarro »

Buenisimo el apunte, muy bien explicado. Me ayudaste una banda, genioooo
Responder