3-2 Ordenaciones con Repetición PDF

Preview

Summary

Download 3-2 Ordenaciones con Repetición PDF

Description

3.2. Ordenaciones con repetición

3.2.1. Presentación: La combinatoria es una herramienta que nos permite calcular de cuántas formas podemos contar, ordenar o seleccionar a los elementos de un conjunto.

En la presente sección estudiaremos a las ordenaciones con

repetición.

3.2.2. Observación: Dado un conjunto A

f

=

a; b; c; d; e

g

podemos imaginarlo como una bolsa donde hay pelotitas, cada una con una de las letras que conforman al conjunto A.

Podemos tomar una pelotita al azar,

registrar cuál pelotita fué y regresarla a la bolsa.

Digamos que la primera vez

que hacemos esto sale la pelotita con la letra b, entonces escribimos

1

7!

b

y regresamos la pelotita a la bolsa. Tal vez la segunda vez salga la pelotita con la letra c, entonces escribimos

2 y regresamos la pelotita a la bolsa.

7!

c

Después de llevar a cabo este proceso un

total de diez veces, podríamos tener una lista como ésta:

1 2 3 4 5

7! 7! 7! 7! 7!

7! 7! 7! 7! 7!

6 7 8 9 10

b c a c d

a c d a a

Podemos observar que ésto proceso nos de…nió a una función f donde I

10 =

: I10

!

A

f 2 N : 1   10g k

k

No está de más notar que los elementos del conjunto I

10

están ordenados, y así, la función conserva la información del orden en que sacamos a las pelotitas. Este proceso de selección ordenada motiva la siguiente de…nición.

3.2.3. De…nición: Dados, un conjunto A, un número natural estrictamente positivo n

2 Z+ 1

el conjunto In

=f

k

y una función f

2N:1  g : ! k

In

n

A

diremos que esta función es una ordenación con repetición de n elementos

del conjunto A. 3.2.4. De…nición: Dados, un número natural estrictamente positivo m

2 Z+

un conjunto A de m elementos, un número natural estrictamente positivo n y el conjunto In

=f

k

2 Z+

2N:1  g k

utilizamos el símbolo

n

n

OR m para describir el número de ordenaciones con repetición de n elementos tomados de un conjunto con m elementos, esto es,

n

ORm

3.2.5.

= #f

f

  : In

A

f es una función de In en A

g

Observación: Dados, un conjunto A, un número natural estricta-

mente positivo

2 Z+ : !

n y función f

In

A

podemos capturar toda la información de la función f mediante la notación:

( (1) (2) (3) f

;f

;f

; :::; f

( )) n

gracias a que tenemos un orden preestablecido para los elementos del dominio.

Por ejemplo, dado el conjunto: A

=f

a; x; r; s; u; w

g

y las funciones:

! 1 7! 2 7! 3 7!

I

3

f

I

A x a s

4

1 & 2 3 4

! 7! 7! 7! 7! g

2

A r w w s

I

5

1 & 23 4 5

! 7! 7! 7! 7! 7! h

A w u a x u

toda la información de ellas queda capturada en la notación: f

=(

x; a; s

) & =( g

r; w; w; s

) & =( h

w; u; a; x; u

)

Esta notación abreviada nos será de utilidad más adelante. 3.2.6.

Ejemplo:

Si dos equipos deportivos van a disputar un par de par-

tidos a ida y vuelta, esto es, que cada uno de ellos será el local en uno de los encuentros, entonces el conjunto

=f

A

l; e; v

g

representa los tres resultados posibles de cada uno de los encuentros: l e v

: : :

que gane el equipo local, que ambos equipos empaten, que gane el equipo visitante.

y el conjunto

f1 2g ;

representa a cada uno de los encuentros, el segundo. Así, tendríamos que el conjunto:

8 >> >> >< >> >> >:

1 2 1 2 1 2

7! 7 ! 7 ! 7 ! 7! 7!

l l

e

v l

1 2

;

l

7 ! 7! 7! 7 ! 7! 7!

1 2

;

1 2

;

l e

e e

v

1

;

1 2

;

1 2 ;

e

al primer encuentro y el

1 2

7 ! 7! 7! 7 ! 7! 7!

l v

e v

v v

;

;

2

al

9 > > > > > = > > > > > ;

está conformado por todos los resultados posibles de ambos partidos. De manera más breve podemos escribir:

8 ( )( )( ) 9 = < ( ) ( ) ( ) : ( )( )( ); l; l

;

l; e

;

l; v

e; l

;

e; e

;

e; v

v; l

;

v; e

;

;

;

v; v

(3.2.5). De cualquier modo resulta que

2 3

OR

3.2.7. Ejemplo:

= 9 = 32

Si lanzamos tres volados, entonces el conjunto A

=f

a; s

3

g

representa los dos resultados posibles de cada uno de los volados: a

:

águila,

s

:

sol.

mientras que el conjunto

f

1; 2; 3

g

representa a cada uno de los volados, el 1 al primero, el 2 al segundo y el 3 al tercero. Así, tendríamos que el conjunto:

8 >> >> < >> >> :

1 2 3 1 2 3

7! 7! 7! 7 ! 7! 7!

a

1

a ;

2

a

3 1

s a

;

a

2 3

7! 7! 7! 7! 7! 7!

a

1

a ;

2

s

3

s

1

a ;

2 3

s

7! 7! 7! 7! 7! 7!

7! 7! 7! 7! 7! 7!

1

a ;

s

2 3

a

s

1

s ;

2 3

a

a s ; s

s s s

9 > > > > = > > > > ;

está conformado por todos los resultados posibles de los tres volados. De manera más breve podemos escribir:

(

a; a; a) ; (a; a; s) ; (a; s; a) ; (a; s; s) ;



(s; a; a) ; (s; a; s) ; (s; s; a) ; (s; s; s) (3.2.5). De cualquier modo resulta que

3 = 8 = 23

OR2

3.2.8. Observación: Dados, el conjunto A

de tres elementos y el conjunto I4

=

=

f

g

a; b; c

f 2N   g :1

k

4

k

de cuatro elementos podemos preguntarnos cuál es el valor de

4

OR3

esto es, podemos preguntarnos cuántas funciones de

I4

en

A

hay.

Para responder a esta pregunta seguimos el siguiente proceso:

(i) Primero nos preguntamos cuántas funciones f

f g!

: 1

A

podemos construír. Es inmediato que hay exactamente tres: 1

7!

a ;

1

4

7!

b ;

1

7!

c

(ii) Ahora nos preguntamos cuántas funciones

f g!

: 1; 2

f

A

podemos construír. Para responder a esto observamos que a partir de cada una de las tres funciones: 1

fg

7!

7!

1

a ;

1

b ;

7! f g c

de 1 en A podemos construír tres funciones de por cada posible imagen para 2:

8 >> >> >< >> >> >:

1 2 1 2 1 2

7! 7 ! 7 ! 7 ! 7 ! 7 !

a

;

a

b

2 1

;

a

c

2 1

;

a

7! 7! 7 ! 7! 7 ! 7!

1

2

a

;

b

b b

c b

1 2

;

1 2

;

1 2

1; 2

7! 7! 7 ! 7 ! 7! 7!

a c

b c

c c

;

en

A,

a saber, una

9 > > > > > = > > > > > ;

o más brevemente: a

a

b

c

(a; a)

(a; b)

(a; c)

b

(b; a)

(b; b)

(b; c)

c

(c; a)

(c; b)

(c; c)

(3.2.5). Esto es, hay

funciones de

f g 1; 2

3 en



3=9=3

2

A.

(iii) A continuación nos preguntamos cuántas funciones f

f

: 1; 2; 3

g!

A

podemos construír. Para responder a esto observamos que a partir de cada una de las nueve funciones:

de

f g 1; 2

en

A

(a; a)

(a; b)

(b; a)

(b; b)

(a; c) (b; c)

(c; a)

(c; b)

(c; c)

podemos construír tres funciones de

5

f

1; 2; 3

g

en

A,

a saber,

3:

una por cada posible imagen para

a

(a; a)

(a; b)

(a; c)

(a; a; a)

(a; b; a)

(a; c; a)

b

(a; a; b)

(a; b; b)

(a; c; b)

c

(a; a; c)

(a; b; c)

(a; c; c)

(b; a)

(b; b)

(b; c)

a

(b; a; a)

(b; b; a)

(b; c; a)

b

(b; a; b)

(b; b; b)

(b; c; b)

c

(b; a; c)

(b; b; c)

(b; c; c)

(c; a)

(c; b)

(c; c)

a

(c; a; a)

(c; b; a)

(c; c; a)

b

(c; a; b)

(c; b; b)

(c; c; b)

c

(c; a; c)

(c; b; c)

(c; c; c)

esto es, hay

funciones de

(iv)

f

1; 2; 3

3

g



9 = 27 = 3

3

en A.

Por último nos preguntamos cuántas funciones

:

f

f

I

g

4

!

A

podemos construír. Para responder a esto observamos que a partir de cada una de las de I

4

27

funciones de

1; 2; 3

en A podemos construír tres funciones

en A, a saber, una por cada posible imagen para

3 funciones de I

4



27 = 81 = 3

4,

esto es, hay

4

en A.

3.2.9. Observación:

Dados, un número natural estrictamente positivo m

2 Z+

un conjunto A de m elementos, un número natural estrictamente positivo n y el conjunto I

n=f

resulta que

k

2 Z+

2N   g :1

mn+1 =

OR

m

nm

pues a partir de cada una de las

OR

6

k

n

nm

(OR )

funciones de

In en A podemos construír m funciones de In+1 en A, a saber, una

por cada posible imagen para

n + 1 2 In+1 esto es, hay

m (ORmn )

In+1 en A.

funciones de

3.2.10. Teorema: Dados, un número natural estrictamente positivo

m 2 Z+ un conjunto

A de m elementos, un número natural estrictamente positivo n 2 Z+

y el conjunto

I n = fk 2 N : 1  k  ng

resulta que

ORnm = mn

Demostración: Daremos la prueba mediante el método de inducción matemática (3.1.2):

(IM1) Veri…car que la proposición

P (0) es verdadera no tiene sentido, pues nuestras de…niciones nos demandan a un número natural estrictamente positivo, por esta razón comenzaremos veri…cando que la proposición

P (1) es verdadera, esto es, que

OR1m = m1 = m pero esto es inmediato, pues hay exactamente una función

fx : para cada elemento

f g ! 7! 1

1

x2A 7

A x

(IM2) Suponemos que se veri…ca

P ( n)

esto es, que se veri…ca la igualdad

ORnm = mn y queremos probar que se veri…ca

P (n + 1) esto es, que se veri…ca la igualdad

ORnm+1 = mn+1 Para esto basta observar que

ORmn+1 = m (ORmn ) = m (mn ) = mn+1 (3.2.9).

8...