SELECCIONES ORDENADAS

• Tenemos k objetos distintos para distribuir en n cajasdistintas con

¿de cuántas formas distintas se pueden introducir los k objetos

k n

¿de cuántas formas distintas se pueden introducir los k objetosen las n cajas, de manera que cada caja contenga como

á i bj t ?máximo un objeto?

Elegimos qué cajas son las que van a contener algún objeto.Elegimos qué cajas son las que van a contener algún objeto.

18

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

• Sean nkccCooO nk con ,...,y ,..., 11

¿Cuántas aplicaciones inyectivas distintas

f : O C podemos definir?

Hay que elegir los elementos distintos entre sí,

li k l t di ti t d j t C

kofof ,...,1

se eligen k elementos distintos de un conjunto C quecontiene n elementos.

19

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

• Selecciones ordenadas de k elementos distintos escogidos de un conjunto C = {c1, c2, …, cn} que contiene n elementos.

• Li t d k l t di ti t [ ]ccc• Listas de k elementos distintos [ ]

elegidos de un conjunto C = {c1, c2, …, c } con n elementos.

krrr ccc ,,,21

elegidos de un conjunto C {c1, c2, …, cn} con n elementos.

El número total de aplicaciones inyectivas, seleccionesordenadas o listas es

!n ! !1...21, kn

nknnnnV kn

20

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

Ejemplosj p

1) ¿Cuántos números naturales mayores que 99 y menores que1) ¿Cuántos números naturales mayores que 99 y menores que 1000 tienen las cifras distintas entre sí y distintas de cero?

2) ¿De cuántas formas distintas pueden sentarse 7 personas en una fila de 10 asientos numerados?

21

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

PERMUTACIONES

C i l d l i d d k• Sean ,...,y ,..., 11 nn ccCooO

Caso particular de selecciones ordenadas con k = n

¿Cuántas aplicaciones biyectivas distintas

11 nn

f : O C podemos definir?Hay que elegir los elementos distintos entre sí,

nofof ,...,1

se eligen ordenadamente los n elementos distintos delconjunto C.

22

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

• Permutación es cada una de las diferentes seleccionesPermutación es cada una de las diferentes seleccionesordenadas de los n elementos distintos de un conjunto.

• Listas de los n elementos distintos [c1, c2, …, cn] de unconjunto C ={c1, c2, …, cn} que tiene n elementos.1 2 n

El número total de aplicaciones biyectivas, permutaciones op y , plistas de n elementos es

! , nVP nnn

23

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

Ejemplosj p

1) ¿De cuántas formas distintas pueden sentarse 10 personas en una) ¿ p pfila de 10 asientos numerados?

2) ¿De cuántas formas se pueden colocar 8 torres iguales en untablero de ajedrez de modo que no se ataquen?

3) ¿De cuántas formas distintas se pueden elegir n posiciones enuna cuadrícula de tamaño n × n de forma que no coincida la filauna cuadrícula de tamaño n × n de forma que no coincida la filani la columna para ninguna de las n posiciones?

4) ¿De cuántas formas distintas pueden sentarse 10 personasalrededor de una mesa circular con 10 asientos?

24

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

SELECCIONES ORDENADAS CON REPETICIÓN

• Tenemos k objetos distintos para distribuir en n cajas distintas• Tenemos k objetos distintos para distribuir en n cajas distintas

¿de cuántas formas se pueden introducir los k objetos en las n¿ p jcajas, teniendo en cuenta que cada caja puede contener los kobjetos?objetos?

Elegimos qué cajas son las que van a contener algún objeto.

25

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

• Sean ,..., y ,..., 11 nk ccCooO

¿Cuántas aplicaciones distintasf O C d d fi i ?f : O C podemos definir?

H l i l k l t ffHay que elegir los k elementos

d j C i l

kofof ,...,1

de un conjunto C que tiene n elementos.

26

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

• Selecciones ordenadas con repetición de k elementos elegidosde un conjunto con n elementos, donde el mismo elemento sepuede elegir hasta k veces.

• Listas de k elementos, no distintos, ],,,[21 krrr ccc

elegidos de un conjunto C = {c1, c2, …, cn} con n elementos.

El número total de aplicaciones selecciones ordenadas conEl número total de aplicaciones, selecciones ordenadas conrepetición o listas es

knVR 27

kn nVR ,

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

Ejemplos

1) ¿Cuántos números distintos de seis cifras existen formados sólo por las cifras 1, 2, 3 ?

2) Sean A = { a1, ..., an } un alfabeto y k ) { 1, , n } y

El conjunto de palabras de longitud k sobre el alfabeto A es

Ak = {ai1 ... aik / aij A , 1 j k }.

Entonces card Ak = kkn nVR ,

28

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

SELECCIONES NO ORDENADAS

• Tenemos k objetos idénticos para distribuir en n cajasdistintas con k n

¿de cuántas formas distintas se pueden introducir los kbj t l j d d j tobjetos en las n cajas, de manera que cada caja contenga

como máximo un objeto?

Elegimos cuántas cajas son las que van a contener algúnobjeto

29

objeto.

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

S l i d d C bi i d k l t• Selecciones no ordenadas o Combinaciones de k elementos

escogidos de entre un conjunto que tiene n elementos.

• Subconjuntos { } con k elementos que tienerrr ccc ,,, Subconjuntos { } con k elementos que tiene

un conjunto C = {c1, c2, …, cn} de n elementos.krrr ccc ,,,

21

nnV

C kn ! ,

kk knP

Ck

kn ! ! ,

30

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

Ej lEjemplos

1) ¿Cuántos colores distintos se pueden obtener al mezclar 3 botes) ¿ p

de pintura si disponemos de un total de 7 botes de colores

distintos?

2) ¿Cuántas manos distintas de póker se pueden obtener?

3) ¿Cuántos subconjuntos tiene un conjunto de n elementos?

31

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

4) El sistema Braille (Louis Braille, 1809 1852) consiste en larepresentación de caracteres mediante puntos en altorrelieve.

Las posiciones de los puntos se sitúan en dos columnasLas posiciones de los puntos se sitúan en dos columnasverticales, de tres puntos cada una.

¿Cuántos caracteres son posibles?

32

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

• Alfabeto Braille• Alfabeto Braille

33

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

34http://educ.queensu.ca/~fmc/may2004/braille.html

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

Soluciones

1)

37

2)

5

52

3) nnn n

C 2

5

3)kk

kn kC 2

00,

4) 6306

26 6

6

1

6

1,6

kkk k

C

35

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

Números combinatorios

Se llaman números combinatorios a las expresiones

0, ,con

! ! !

nknk

kknn

kn

Propiedades

1. Un conjunto de n elementos tiene el mismo número de subconjuntos de k elementos que de n k elementos.

k

nkk

nkn

!!

!

36

knkknk !!

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

2. Teorema del binomio de Newton ( Probado por Euler )

kknn

n yxkn

yx

El número de selecciones no ordenadas de tamaño n

k k 0

El número de selecciones no ordenadas de tamaño n

de dos símbolos x, y es

kn

Se elige el símbolo x n k veces

k

el símbolo y k veces.

37

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

ConsecuenciasConsecuencias

n

k

kknn

k

nn

kn

kn

0011112

kk kk 00

kn

kn k

n

k

kknn

k

n )1()1(111000

38

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

3. El número de subconjuntos de k elementos que tiene unconjunto de n elementos es la suma del número deconjunto de n elementos es la suma del número desubconjuntos de k elementos

a) que contienen a un elemento x fijo

b) que no contienen a un elemento x fijob) que no contienen a un elemento x fijo

nnn 11

kkk 1

39

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez

4. Identidad de Vandermonde, 1772

El número de formas diferentes de elegir k personas en un conjunto formado por n hombres y m mujeresconjunto formado por n hombres y m mujeres.

mnmnmnmn

0110m

kn

kmn

kmn

kmn

mnmnk ,,

40

Departamento de Matemática Aplicada. ETSIInf. UPM. Victoria Zarzosa Rodríguez