Técnicas de contarClase - Academia Cartagena99 de contar 2.pdf · SELECCIONES ORDENADAS •...

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


• 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


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


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


• 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


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


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


• 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


• 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 ,


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


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.


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


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


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


• Alfabeto Braille• Alfabeto Braille

33


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


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


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 !!


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


ConsecuenciasConsecuencias

n

k

kknn

k

nn

kn

kn

0011112

kk kk 00

kn

kn k

n

k

kknn

k

n )1()1(111000

38


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


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


Técnicas de contarClase - Academia Cartagena99 de contar 2.pdf · SELECCIONES ORDENADAS •...

Documents

Transcript of Técnicas de contarClase - Academia Cartagena99 de contar 2.pdf · SELECCIONES ORDENADAS •...