Solución 01 - MAT1314

Pontificia Universidad Católica de Chile
Facultad de Matemáticas
Departamento de Matemática
Profesor: Héctor Pastén – Ayudante: Alejandra Schild
Introducción a la Combinatoria - MAT1314

Solución 1
17 de Marzo 2023
Problema 1. Determine el número de palabras de 9 letras que se pueden formar con las letras
{a, b, c} y tales que la letra a aparezca exactamente 4 veces y la b aparezca exactamente 3 veces
(como por ejemplo cabcababa).
Si tomamos ahora un natural n arbitrario, a1 , . . . , ak sı́mbolos (letras) y enteros n1 , · · · , nk tales
que n1 + . . . + nk = n, ¿cuántas palabras de largo n se pueden formar de modo que la letra ai
aparezca exactamente ni veces?
Solución. Para construir dichas palabras, empecemos con una lista de n espacios vacı́os. Primero
elegimos la ubicación de cada uno de los n1 sı́mbolos a1 , luego elegimos la ubicación de cada uno
de los n2 sı́mbolos a2 entre los n − n1 espacios restantes, y ası́ sucesivamente. El número de formas
de seleccionar las posiciones para los sı́mbolos ai es exactamente n−ni−1 −nni−2 −···−n1

i
, pues tenemos
n − ni−1 − ni−2 − · · · − n1 posiciones libres y debemos seleccionar ni de ellas.
Por el principio de multiplicación, obtenemos que el número de palabras es
k k
Y n − ni−1 − ni−2 − . . . − n1 Y (n − ni−1 − ni−2 − . . . − n1 )! n!
= = .
ni ni !(n − ni − ni−1 − ni−2 − . . . − n1 )! n1 !n2 ! · · · nk !
i=1 i=1
Problema 2. Consideremos un tablero de N × N. La casilla C(n, k) describe la casilla en

la n-ésima fila y k-ésima columna. Construiremos un triángulo numérico usando la siguiente
recurrencia:
1. C(n, 0) = 1 para todo n ≥ 0.
2. C(n, 1) = n para todo n ≥ 1.
3. C(n + 1, k) = C(n + 1, k − 1) + C(n, k) para 1 < k < n + 1.
4. C(n + 1, n + 1) = C(n + 1, n) para n ≥ 1.
Demuestre que C(n, n) es el n-ésimo número de Catalán.
1
Solución. Sea T (n, k) el conjunto de tuplas (a1 , . . . , an+k ) ∈ {−1, 1}n+k con n coordenadas iguales
a 1, k coordenadas iguales a −1 y tales que sus sumas parciales son no negativas, es decir:
a1 + · · · + aj ≥ 0 ∀ j ∈ {1, . . . , n + k} .
A este tipo de sucesiones

las llamaremos sucesiones aceptables.
Podemos probar que T (n, k) y C(n, k) cumplen las mismas recurrencias y tienen los mismos casos

bases. De hecho:

1. Claramente T (n, 0) = 1.

2. T (n, 1) = n pues el −1 puede estar en cualquiera de las n + 1 posiciones excepto por la
primera (n opciones).
3. Sea A el conjunto de secuencias en T (n + 1, k) cuya última coordenada es igual a 1. La

operación de quitar ese 1 del final establece una biyección entre A y T (n, k). Ahora sea B el
conjunto de secuencias en T (n + 1, k) cuya última coordenada es igual a −1. La operación de
quitar ese −1 del final establece una biyección entre
B y T (n +1, k − 1). Claramente
AyB
forman una partición de T (n + 1, k), por lo que T (n + 1, k) = T (n + 1, k − 1) +T (n, k).
4. En una secuencia en T (n + 1, n + 1) necesariamente se cumple que la última coordenada

es igual a −1, o de lo contrario la penúltima suma parcial serı́a negativa. La operación de
quitar ese −1 del
final
establece
una biyección con las secuencias en T (n + 1, n). Luego
T (n + 1, n + 1) = T (n + 1, n).

De esta forma, se cumple queT (n, k) = C(n, k).
Quedó pendiente probar que T (n, n) es el n-ésimo número de Catalán. Esto será demostrado en
la ayudantı́a 3.
Problema 3. Sea α un número irracional y ε > 0 un real (fijo). Demuestre que existe un
entero positivo n tal que nα está a una distancia menor que ε de algún entero.
1
Solución. Tomemos un entero positivo m tal que m < ε y dividamos al intervalo (0, 1) en los
1
siguientes m intervalos de longitud m :

1 1 2 m−1
0, , , , ..., ,1 .
m m m m
Por el principio del palomar, tenemos que entre los números α, 2α, 3α, . . . , (m + 1)α, existen dos
números cuyas partes decimales (fraccionarias) caen en el mismo intervalo (ninguno de esos números
puede caer en un extremo de los intervalos porque α es irracional). Supongamos que estos números
1
son pα y qα, con 1 ≤ p < q ≤ m + 1. Entonces (q − p)α está a una distancia menor que m < ϵ de
un entero.
2
Problema 4. Sea n un entero positivo. Se tienen n puntos P1 , . . . , Pn en un cı́rculo (cerrado)
de radio 1, y uno de ellos es el centro. Para cada i ∈ {1, . . . , n} calculamos las distancias desde
Pi hasta cada uno de los otros puntos, y definimos di como la menor de ellas. Demuestre que:
d21 + . . . + d2n ≤ 9.
Solución. Para cada i ∈ {1, . . . , n} sea Di un disco sin borde con centro Pi y radio di/2. Estos
discos son disjuntos. Además como el centro del cı́rculo unitario es uno de los puntos escogidos,
todos los discos Di están contenidos en una ampliación del cı́rculo inicial de radio 1 a uno de
radio 3/2 (porque todas las distancias di son menores o iguales a 1). Como los discos son disjuntos,
tenemos que
πd21 πd2 9π
+ ... + n ≤ .
4 4 4

Solución 01 - MAT1314

Cargado por

Copyright:

Formatos disponibles

Solución 01 - MAT1314

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Solución 01 - MAT1314

Cargado por

Copyright:

Formatos disponibles

Pontificia Universidad Católica de Chile

Introducción a la Combinatoria - MAT1314

Problema 2. Consideremos un tablero de N × N. La casilla C(n, k) describe la casilla en

1. C(n, 0) = 1 para todo n ≥ 0.

2. C(n, 1) = n para todo n ≥ 1.

3. C(n + 1, k) = C(n + 1, k − 1) + C(n, k) para 1 < k < n + 1.

4. C(n + 1, n + 1) = C(n + 1, n) para n ≥ 1.

Demuestre que C(n, n) es el n-ésimo número de Catalán.

A este tipo de sucesiones

3. Sea A el conjunto de secuencias en T (n + 1, k) cuya última coordenada es igual a 1. La

4. En una secuencia en T (n + 1, n + 1) necesariamente se cumple que la última coordenada

También podría gustarte