Problemas Combinatoria Clase 13

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 5

1 Problemas de Combinatoria.

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?

3.- De un grupo de 10 hombres y 12 mujeres, ¿ de cuantas formas se puede elegir una


comisión de 5 miembros en la que al menos haya dos mujeres? ¿ Cuantas si además el
hombre 1 y la mujer 1 no pueden pertenecer ambos a la comisión ?

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?.

5.- Sea S = {1, 2, . . . , 365}. ¿Cuántos subconjuntos de tamaño 40 contiene? ¿Y mul-


tisets (subconjuntos no ordenados con repetición) de tamaño 40? Si en un aula hay 40
estudiantes, ¿cúal es la probabilidad de que haya dos estudiantes que cumplan los años el
mismo dı́a?.

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?

10.- ¿ Cual es el número de permutaciones de las letras de la palabra MISSISSIPI?

11.- ¿De cuantas formas podemos colocar 5 torres en un tablero de ajedrez 8 × 8 de


forma que ninguna pueda comer a ninguna otra? ¿ Cuantas si además exigimos que la
primera fila y la primera columna tengan al menos una torre?

12.- En una fila de 20 asientos se sientan 5 hombres y 6 mujeres.


i)Calcular el número de formas distintas de sentarse. ii) Calcular el número de formas
distintas de sentarse si no puede haber dos hombres juntos. iii) Dar una fómula para el
problema del apartado anterior si hay h hombres, m mujeres y s asientos.

13.- ¿ Cuantas soluciones enteras tiene la ecuació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 ?

18.- Supongamos que la siguiente 5 × 6 rejilla indica una red de calles

¿ De cuantas formas podemos ir desde la esquina inferior izquierda a la superior derecha


con un camino de longitud mı́nima? ¿ De cuantas formas en una rejilla n × m? ¿Y en una
de tres dimensiones n1 × n2 × n3 ?

Encontrar para que valores de n y k es


( ) ( )
n n
=3
k+1 k

19.- Sea n un entero positivo. Demostrar que


∑ n ( )2 {
k n 0, (2m) si n es impar;
(−1) = m
k (−1) m , si n=2m.
k=0

20.- Hallar a3 , a2 y a1 tales que


( ) ( ) ( )
m m m
m3 = a3 + a2 + a1
3 2 1
Calcular usando que
( ) ( ) ( ) ( ) ( )
0 1 n−1 n n+1
+ + ... + + =
k k k k k+1

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.

23.- Determinar el número de submultisets de 12 elementos del multiset

S = {4 · a, 3 · b, 4 · c, 5 · d}

Idem submultisets de 10 elementos de

S = {∞ · a, 4 · b, 5 · c, 7 · d}

24.- Determinar el número de soluciones enteras de la ecuación

x1 + x2 + x3 + x4 = 14

tales que 0 ≤ xi ≤ 8. Idem si 1 ≤ xi ≤ 8.

25.- Determinar el número de soluciones enteras de la ecuación

x1 + x2 + x3 + x4 = 20

tales que
1 ≤ x1 ≤ 6, 0 ≤ x2 ≤ 7, 4 ≤ x3 ≤ 8, 2 ≤ x4 ≤ 6

26.- Determinar el número de permutaciones de {1, 2, . . . , 8} en las cuales ningún


número par está en su posición natural. Idem, permutaciones que tengan exactamente cu-
atro enteros en su posición natural. Idem, permutaciones que tengan al menos un impar en
su posición natural. Hallar una fórmula para el número de permutaciones de {1, 2, . . . , n}
que tiene exactamente k enteros en su posición natural.

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.

28.- Determinar el número de permutaciones del multiset

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.

30.- Contar las permutaciones i1 i2 i3 i4 i5 i6 de {1, 2, 3, 4, 5, 6} tales que

i1 ̸= 1; i3 ̸= 2, 3, 5; i4 ̸= 4; i6 ̸= 5, 6.

31.- Sea fn el n-ésimo número de Fibonacci. Demostrar que si m es divisible por n, fm


lo es por fn . Demostrar que si el m.c.d. de m y n es d, el m.c.d. de fm y fn es fd .

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?

34.- Resolver la ecuación de recurrencia hn = (n + 2)hn−1 con el valor inicial h0 = 2.

35.- Resolver la ecuación de recurrencia hn = 5hn−1 − 6hn−2 − 4hn−3 + 8hn−4 con


valores iniciales h0 = 0, h1 = 1, h2 = 1, h3 = 2.

36.- Supongamos que tenemos 2n puntos en un cı́rculo. Sea hn el número de formas


de unir estos puntos en pares de forma que los correspondientes segmentos no se corten.
Hallar una fórmula de recurrencia para hn .

37.- Resolver la relación de recurrencia

hn = 6hn−1 − 9hn−2 + 2n

con h0 = 1, h1 = 0.

38.- Resolver la ecuación de recurrencia

hn = 4hn−1 + 4n

con h0 = 3.

39.- Determinar la función generatriz de hn = n3 .

40.- Determinar la función generatriz para el número hn de soluciones enteras y no


negativas de
2x1 + 5x2 + x3 + 7x4 = n

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).

45.- Demostrar que los números de Stirling cumplen


( )
n
S2 (r, r − 1) =
2

S2 (r, 2) = 2r−1 − 1
( ) ( )
r r
S2 (r, r − 2) = +3
3 4

46.- Calcular los 10 primeros números de Bell.

También podría gustarte