Autor Tema: Dudas problemas de combinatoria

0 Usuarios y 1 Visitante están viendo este tema.

21 Noviembre, 2011, 07:54 pm
Leído 5930 veces

Gaussa

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,551
  • Karma: +1/-0
  • Sexo: Femenino
Hola.

Tengo una serie de problemas de combinatoria en los que dudo no sé cómo hacerlos. Son los siguientes.

- Calcule de las 5 vocales cuál de ellas ocupa el décimo lugar suponiendo que estén ordenadas alfabéticamente.
-  Tenemos los dígitos 2,4,6 y 8. Decir que lugar oupará el número 6248 si los suponemos ordenados en orden creciente.

Estos dos los tengo resueltos en mis apuntes. Mi problema está en que por mucho que leo la solución no la cabo de comprender. Si alguien pudiera explicármelo para ver si lo consigo...

- ¿Cuántas palabras de 8 bits comienzan por 01? ¿Cuántas tienen el primer y último dígito iguales? ¿Tienen exactamente 3 ceros? ¿Al menos 3 ceros? ¿El mismo número de ceros que de unos?

De aquí sólo he hecho las dos primeras que me dan \( VR_{2,6} \)

- Calcule el número de enteros divisibles entre 2, 3 ó 5.

Este no lo entiendo, pues el número de enteros divisbles por 2, por ejemplo, es infinto, ¿no?

- Calcule el número de permutaciones de la palabra ABCDEFG que contengan:
La secuencia ABC
Las secuencias AB, CD y EF
Las secuencias AB, BC y EF

De aquí sólo hice la primera, al de la secencia ABC, que me da \( 5 \cdot{4!} \), espero que al menos ese esté bien.Los otros he hecho intentos, pero no sé plantearlos.

Perdonen por escribir tantos problemas, es que estos los he intentado demasiado sin obtener resultado...

Saludos y muchas gracias.


22 Noviembre, 2011, 12:31 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Citar
- Calcule de las 5 vocales cuál de ellas ocupa el décimo lugar suponiendo que estén ordenadas alfabéticamente.

No se entiende lo que pregunta. Las cinco vocales ordenadas alfabéticamente son a,e,i,o,u. Y no hay ninguna en décima lugar. Intuyo a que se refiere a formar palabras con esa vocales. Pero yo no puedo adivinar o inventar el enunciado. Tal como está, en mi opinión, no tiene sentido.

Citar
-  Tenemos los dígitos 2,4,6 y 8. Decir que lugar oupará el número 6248 si los suponemos ordenados en orden creciente.

Tampoco está muy claro. Pero nuevamente recurriendo a la lógica, la única interpretación posible es que formamos número sólo con los dígitos \( 2,4,6,8 \). Se trata de contar cuantos hay menores o iguales que \( 6248 \).

Como tenemos cuatro cifras a utilizar habrá:

 \( 4 \) números de una cifra (y por tanto menores que \( 6248 \))
 \( 4\cdot 4 \) números de dos cifras (y por tanto menores que \( 6248 \))
 \( 4\cdot 4\cdot 4 \) números de tres cifras (y por tanto menores que \( 6248 \))
 \(  2\cdot 4\cdot 4\cdot 4 \) números de cuatro cifras que empiezan por \( 2 \) ó \( 4 \) (y por tanto menores que \( 6248 \))

 y finalmente añadimos uno más, el \( 6248 \) (el único número que empieza por \( 6 \) menor o igual que \( 6248 \)). Ahora suma todo.

Citar
- ¿Cuántas palabras de 8 bits comienzan por 01? ¿Cuántas tienen el primer y último dígito iguales? ¿Tienen exactamente 3 ceros? ¿Al menos 3 ceros? ¿El mismo número de ceros que de unos?

De aquí sólo he hecho las dos primeras que me dan \( VR_{2,6} \)

\( VR_{2,6} \) está bien para el primero.

Para el segundo serían \( 2\cdot VR_{2,6} \) ya que pueden acabar y empezar simultáneamente por cero o por uno.

Para contar cuantas tiene exactamente tres ceros, nota que para formar una palabra de ocho bits con tres ceros sólo tenemos que elegir donde colocamos los ceros, es decir, escoger tres posciones de entre ocho posibles sin repetir y sin importar el orden (combinaciones sin repetición...)

Para contar cuantas tienen al menos tres ceros; cuenta, por ejemplo, cuantas tienen exactamente tres, cuatro, cinco, etcétera ceros.

Misma idea para cuatro unos y cuatro ceros.


Citar
- Calcule el número de enteros divisibles entre 2, 3 ó 5.
Este no lo entiendo, pues el número de enteros divisbles por 2, por ejemplo, es infinto, ¿no?

Efectivamente. Debieran de decirte enteros menores que alguna cota superior.

Citar
- Calcule el número de permutaciones de la palabra ABCDEFG que contengan:
La secuencia ABC
Las secuencias AB, CD y EF
Las secuencias AB, BC y EF

Para el segundo simplemente considera los paquetes "AB" "CD" "EF" como un sólo elemento, de manera que sólo tienes que contar las permutacioens que puedes hacer con AB,CD,EF,G es decir, permutaciones de cuatro elementos.

Para el segundo si tiene que contener a la secuencia AB y BC tiene que contener a la secuencia ABC. Ahora usa la misma idea que en el anterior.

Saludos.

22 Noviembre, 2011, 08:31 pm
Respuesta #2

Gaussa

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,551
  • Karma: +1/-0
  • Sexo: Femenino
Hola.

Muchas gracias, el manco, todos los problemas muy claros. Me quedan los dos primeros, te escribo lo que viene en mis apuntes, ya que yo no lo acabo de comprender.

- Calcule de las 5 vocales cuál de ellas ocupa el décimo lugar suponiendo que estén ordenadas alfabéticamente.

Fijamos la a en primera posición y permutamos las otras cuatro vocales. Habrá entonces \( 4! \) ordenaciones que comienzan por a. La que buscamos tendrá la forma \( av_2v_3v_4v_5 \). De estas 24 ordenaciones distintas, fijamos cualquiera de las otras vocales en la segunda posición y permutamos las restantes, por lo que habrá \( 3! \) ordenaciones que comienzan por a y continúan por cada una de las restantes vocales en orden alfabético. La permutación es una de la forma \( aiv_3v_4v_5 \). Por un razonamiento igual al anterior habrá \( 2! \) ordenaciones que comiencen por ai y siguen con cualquiera de las tres vocales restantes. En orden alfabético significa que la séptima y la octava empiezan por \( aie \), la novena y la décima por \( aio \) y las dos restantes por \( aiu \). Por ello, la permutación que buscamos será \( aiov_4v_5 \). De las dos ordenaciones posibles para \( v_4,v_5 \), la primera en orden alfabético es \( eu \) y la segunda \( ue \). Por tanto, la que ocupa el décimo lugar será \( aioue \).

-  Tenemos los dígitos 2,4,6 y 8. Decir que lugar ocupará el número 6248 si los suponemos ordenados en orden creciente.

Fijando el 2, tendremos \( 3! \) números que empiezan por 2 y si fijamos el 4, también tendremos \( 3! \) números que empiezan por 4, luego del primero al duodécimo empiezan por 2 los seis primeros y por 4 los seis restantes. El decimotercer número empezará por 6, que será el numero buscado.

Saludos y muchas gracias.


22 Noviembre, 2011, 08:39 pm
Respuesta #3

Héctor Manuel

  • Lathi
  • Mensajes: 3,701
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
Imagino que te refieres al orden lexicográfico:  "Se ordenan todas las palabras de 5 letras que se pueden formar con a,e,i,o,u tal como aparecerían en el diccionario.  ¿Cuál sería la palabra en el lugar 10?"

Dejando la primera letra, a, fija, las otras 24 se ordenan de 4!=24 formas, de modo que desde la palabra 1 hasta la 24, todas empiezan con a.  Entonces la palabra 10 empieza con a.  Dejando fija la segunda letra, e, las otras 3 se ordenan de 3!=6 formas, de modo que de la palabra 1 a la 6 empiezan con ae, y análogamente, de la 7 a la 12 empiezan con ai.

A partir de ahí es fácil terminar.  La palabra 7 es aieou, la 8 es aieuo, la 9 es aioeu, y la 10 es aioue.

Saludos.

22 Noviembre, 2011, 10:59 pm
Respuesta #4

Gaussa

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,551
  • Karma: +1/-0
  • Sexo: Femenino
Hola.

Ya me aclaré con todas las preguntas, muchas gracias a los dos.

Saludos.

23 Noviembre, 2011, 10:17 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Tan sólo me retiero en la mala redacción de los enunciados.

 Un enunciado entendible sería:

 1) Si ordenamos las palabras de cinco letras que podemos formar permutando las vocales. ¿Cuál ocupará el décimo lugar?.

 2) Si ordenamos en orden creciente los números de cuatro cifras que podemos formar permutando los dígitos \( 2,4,6,8 \). ¿Qué lugar ocupará el número \( 6248 \)?.

 Tal como estaba redactados, en mi opinión, no se puede saber lo que realmente pedían.

Saludos.

18 Enero, 2014, 05:47 pm
Respuesta #6

arkady-svidrigailov

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 295
  • Karma: +0/-0
  • Sexo: Masculino
hola, tengo una duda sobre esa de ordenar las permutaciones y mencionar la décima... porque ahí sí es facil... pero si tengo las permutaciones de las 27 letras ordenadas y tengo que decir cuál es la número 16003 cómo hago?

por otra parte creo que descubrí que no sé bien qué patrón se sigue para ordenar n símbolos de "menor" a "mayor" suponiendo que la jerarquía la dé la primera permutación (sea alguna dada de los n símbolos)

19 Enero, 2014, 10:37 pm
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

hola, tengo una duda sobre esa de ordenar las permutaciones y mencionar la décima... porque ahí sí es facil... pero si tengo las permutaciones de las 27 letras ordenadas y tengo que decir cuál es la número 16003 cómo hago?

Fíjate que al ordenar las palabras en orden léxicográfico (como en un diccionario) primero se van cambiando las últimas letras y a medida que se agotan las opciones van cambiando las anteriores. Por ejemplo con las vocales:

aeiou
aeiuo
aeoiu
aeoui
aeuio
aeuoi
aieou
....

Entonces debemos de obtener primero cuantas letras hace falta permutar para llegar a \( 16003 \). Se tiene que:

\( 7!=5040<16003<8!=40320 \)

Por tanto hace falta permutar las \( 8 \) últimas letras. Es decir las \( 27-8=19 \) letras restantes serán las primeras \( 19 \) letras del alfabeto.

Ahora pasa saber cuál es la letra \( 20 \) tenemos en cuenta que:

\( 16003=3\cdot 5040+883 \)

Es decir hemos completado tres ciclos de tres permutaciones de las últimas \( 7 \) letras. Por tanto la letra \( 20 \) ha avanzado tres, es decir, es la letra número \( 23 \) del alfabeto.

Nos queda saber ahora las últimas siete letras. Sería equivalente a saber la palabra \( 883 \) si usamos sólo las letras número \( 20,21,22,24,25,26,27 \) del alfabeto (la \( 20 \) sustituye a la \( 23 \)). Reiteraríamos el argumento...

Obviamente es laborioso, pero es un algoritmo recursivo implementable por ejemplo en un ordenador.

Citar
por otra parte creo que descubrí que no sé bien qué patrón se sigue para ordenar n símbolos de "menor" a "mayor" suponiendo que la jerarquía la dé la primera permutación (sea alguna dada de los n símbolos)

No estoy seguro de entender aquí tu duda. ¿Conoces el orden léxicográfico, el usual con el que se ordenan las palabras en un diccionario?.

Saludos.

CORREGIDO

20 Enero, 2014, 05:54 am
Respuesta #8

arkady-svidrigailov

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 295
  • Karma: +0/-0
  • Sexo: Masculino
en la forma de ordenar las vocales pensaba: primero muevo dos letras, hay sólo una posibilidad. después tres, y para eso voy corriendo la última hacia atrás, cuando llega al final las dos que estaban antes y así... se consideran 4 letras y se va moviendo la última hacia atrás (la "e") hasta que llega al final, y ahora con la "e" en primera posición se empieza a correr la "i" hacia atrás como antes...
el tema es que después me di cuenta que me había olvidado de "aeuio" antes de considerar "aeuoi", y bueno, uno se da cuenta ahí, pero me parece que con muchas letras, las 27 del alfabeto por ejemplo, se haría más complicado.

no entiendo qué razonamiento usas cuando calculás cuál es la letra número 20.

no, no conozco el orden lexilográfico. yo me refería a que sacando los números o las vocales, si uno tuviese los símbolos o signos o como debieran llamarse: ...@#$^(& en ese orden de manera que de de derecha a izquierda crezca la jerarquía (como en los números que en "posición de decenas" vale más), ver de qué manera se irían ordenando las permutaciones de todos esos caracteres.   

21 Enero, 2014, 01:40 pm
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

no entiendo qué razonamiento usas cuando calculás cuál es la letra número 20.

Te pongo un ejemplo con menos letras: con las vocales como antes. Consideramos el listado de \( 5!=120 \) palabras que pueden obtenerse reordenando las vocales. Ordenamos alfabéticamente tales palabras (¡ese es el orden léxicográfico!). Supón que queremos saber que palabra ocupa el lugar \( 17 \).

Reproduciré el razonamiento que hice antes para este caso:

Debemos de obtener primero cuantas letras hace falta permutar para llegar a \( 17 \). Se tiene que:

\( 3!=6<17<4!=24 \)

Por tanto hace falta permutar las \( 4 \) últimas letras. Es decir la \( 5-4=1 \) letra restante será la primera letras de las vocales: la \( a \).

Ahora pasa saber cuál es la letra \( 2 \) tenemos en cuenta que:

\( 17=2\cdot 6+5 \)

Es decir hemos completado dos de permutaciones de las últimas \( 3 \) letras. Por tanto la letra \( 2 \) ha avanzado dos, es decir, es la letra número \( 4 \) de las vocales: la \( o \).

Nos queda saber ahora las últimas tres letras. Sería equivalente a saber la palabra \( 5 \) si usamos sólo las letras número \( 2,3,5 \) de las vocales (la \( 2 \) sustituye a la \( 4 \)). Es decir permutamos las letras \( e,i,u \). Reiteraríamos el argumento. En este caso lo hacemos ya a mano. Las seis permutaciones ordenadas alfabéticamente son:

eiu,eui,ieu,iue,uei,uie

La \( 5 \) es uei por lo que la palabra buscada sería: aouei.

Pongo ahora el listado de las 17 primeras reordenaciones de las vocales ordenadas alfabéticamente, para que veas que el resultado es correcto y te ayude además a seguir el razonamiento anterior.

aeiou
aeiuo
aeoiu
aeoui
aeuio
aeuoi

aieou
aieuo
aioeu
aioue
aiueo
aiuoe

aoeiu
aoeui
aoieu
aoiue
aouei

(fíajte que he ido separando cada ciclo de permutaciones de las tres últimas letras).

Citar
no, no conozco el orden lexilográfico. yo me refería a que sacando los números o las vocales, si uno tuviese los símbolos o signos o como debieran llamarse: ...@#$^(& en ese orden de manera que de de derecha a izquierda crezca la jerarquía (como en los números que en "posición de decenas" vale más), ver de qué manera se irían ordenando las permutaciones de todos esos caracteres.   

Pues es el orden alfabético "de toda la vida". ¿Más claro ahora?.

Saludos.