Problemas Combinatoria Clase 13
Problemas Combinatoria Clase 13
Problemas Combinatoria Clase 13
1.- Calcular el número de enteros mayores de 5000 con todas sus cifras distintas, pero
donde no aparecen ni el 2 ni el 7.
2.- ¿De cuantas formas distintas pueden sentarse 15 personas en una mesa redonda, si
la persona 1 no puede sentarse al lado de la 2?
4.- Diremos que un número es decreciente si todas sus cifras son decrecientes. Por ejem-
plo 430 y 621 son decrecientes, pero 988 o 978 no lo son. ¿Cuántos números decrecientes
hay?. ¿Cuántos hay con 5 cifras?.
6.- ¿ Cuantos subconjuntos de 3 números del conjunto {1, 2, . . . , 20} pueden elegirse
con la condición de que no haya dos números consecutivos?
7.- Una clase tiene dos filas de 8 asientos. A la clase acuden 14 estudiantes, 5 de los
cuales siempre se sientan en la primera fila, y 4 siempre en la segunda. ¿ De cuantas formas
distintas pueden sentarse?
8.- En una reunión hay 15 hombres y 20 mujeres. De cuantas formas distintas pueden
formarse 15 parejas? ¿ Y 10 parejas?
9.- Necesitamos seleccionar 12 remeros para una barca, 6 remando en la parte derecha
y 6 en la izquierda. Disponemos de 20 personas, pero 9 de ellas sólo reman bien en la
derecha, y 7 sólo bien en la izquierda, y las 4 restantes bien en los dos lados. ¿ De cuantas
formas distintas podemos hacer una buena selección?
x1 + x2 + x3 + x4 = 30
cumpliendo x1 ≥ 2, x2 ≥ 0, x3 ≥ −5, x4 ≥ 8?
1
14.- Supongamos que tenemos 20 palillos consecutivos ocupando 20 plazas
||||||||||||||||||||
¿ De cuantas formas podemos seleccionar 6 palillos de forma que no queden dos huecos
seguidos?
¿ De cuantas formas podemos hacer la selección si entre cada dos palillos seleccionados
debe haber al menos otros dos palillos?
Si en lugar de 20 hay n palillos, queremos seleccionar k, y entre dos palillos seleccionados
debe haber al menos l, ¿de cuantas formas podemos hacer esa selección?
15.- ¿De cuantas formas podemos distribuir 10 manzanas indistinguibles y una naranja
entre tres niños, de forma que cada uno obtenga al menos una fruta?
16.- Queremos colocar 20 libros en 5 estanterı́as cada una de las cuales puede contener
los 20 libros. ¿ De cuantas formas distintas pueden colocarse suponiendo que los 20 libros
son distintos? ¿ Y si son indistinguibles? ¿ Que sucede si tenemos n libros, k estanterı́as,
y cada estanterı́a puede soportar l ≤ n libros?
17.- Hay 2n personas en una fiesta. Cada persona está hablando con otra, ası́ hay n
pares de personas. ¿ Cuantas formas distintas de hacer esos pares hay ?
2
cuanto vale 13 + 23 + . . . n3 . Generalizar el método para calcular 1k + 2k + . . . + nk .
21.- Demostrar que para todos los números reales r y todo entero k y m se cumple
( )( ) ( )( )
r m r r−k
=
m k k m−k
22.- Encontrar el número de enteros en el rango [1, 10000] que no son divisibles ni por
4, ni por 5, ni por 6. En el mismo rango encontrar los que no son potencia de ningún otro
número de ese rango.
S = {4 · a, 3 · b, 4 · c, 5 · d}
S = {∞ · a, 4 · b, 5 · c, 7 · d}
x1 + x2 + x3 + x4 = 14
x1 + x2 + x3 + x4 = 20
tales que
1 ≤ x1 ≤ 6, 0 ≤ x2 ≤ 7, 4 ≤ x3 ≤ 8, 2 ≤ x4 ≤ 6
27.- Sea Dn el número de permutaciones de {1, . . . , n} en las que ningún elemento está
en su posición natural. Demostrar que
( ) ( ) ( ) ( )
n n n n
n! = Dn + Dn−1 + . . . + D1 + D0
0 1 n−1 n
Suponemos D0 = 1.
S = {3 · a, 4 · b, 2 · c}
tales que todas las letras del mismo tipo no pueden aparecer seguidas (no 3 a seguidas, ni
4 b, ni 2 c). Idem, si buscamos permutaciones circulares distintas.
3
29.- Demostrar que Dn es par si y sólo si n es impar.
i1 ̸= 1; i3 ̸= 2, 3, 5; i4 ̸= 4; i6 ̸= 5, 6.
32.- Dado un entero k ≥ 2, sea hn el número de secuencias de longitud n con los sı́mbolos
{1, . . . , k} tales que no hay dos unos consecutivos. Hallar una fórmula de recurrencia para
hn , hallar su función generatriz y su valor asintótico.
33.- n personas están sentadas en una fila de n asientos de un cine. Antes de empezar la
pelı́cula algunos cambian su asiento con el de uno de sus vecinos adyacentes. Supongamos
que ninguno hace más de un cambio de asiento. ¿ Cuántas formas distintas de sentarse
pueden obtenerse haciendo esos cambios de asiento?
hn = 6hn−1 − 9hn−2 + 2n
con h0 = 1, h1 = 0.
hn = 4hn−1 + 4n
con h0 = 3.
41.- Determinar el número de enteros positivos con n cifras, todas impares, y dónde la
cifra 1 y la 3 aparecen un número par y mayor que 0 de veces.
42.- Sea hn el número de secuencias de longitud n con los sı́mbolos {1, 2, 3, 4}, dónde 1
aparece un número par de veces y 3 un número impar de veces. Dar una fórmula para hn .
43.- Sea hn el número de secuencias de longitud n con los sı́mbolos {0, 1, 2, }, dónde
están prohibidos los pares 02 y 20. Dar una fórmula para hn .
4
44.- Sea S = {1, 2, . . . , n} Hallar una fórmula para el número de subconjuntos de S que
no contienen tres números consecutivos.
(Si es hn ese número es h0 = 1, h1 = 2, h2 = 4, h3 = 7, h4 = 13).
S2 (r, 2) = 2r−1 − 1
( ) ( )
r r
S2 (r, r − 2) = +3
3 4