[XXXXXXX]

Buenas Noches,
Espero haberle pegado a la sección que era, esto es de discretas, me suena que podría acomodarse aquí...

Tengo estos dos ejercicios, probablemente les parezcan muy fáciles, pero a mi no.

8. Demuestre que el número de palabras de longtiud \( 2n \) que se pueden formar de un alfabeto de \( n \) letras sin que dos seguidas sean iguales es:

\( \dfrac{1}{2^n}((2n)!-\displaystyle\binom{n}{1}2(2n-1)!+\displaystyle\binom{n}{2}2^2(2n-2)!+\ldots+(-1)^n2^nn!) \)

9. Sea \( S=\{2,3,5,11,13,17,19\} \). Utilice el principio del palomar para probar que hay al menos 4 subconjuntos tales que la suma de sus elementos sean iguales.

Necesito ayuda con los dos, y esto es lo que he intentado:
8) Dice alfabeto de tamaño n, formar palabras de tamaño 2n sin que se repitan símbolos contiguos.
Según mi interpretación, puedo elegir entre los n símbolos para el primer espacio. Para el segundo puedo elegir cualquiera menos el que ya coloqué (es decir: n-1 símbolos). Para el tercero puedo elegir cualquiera (inclusive el primero) excepto el anterior (de nuevo hay n-1 opciones), así sigo sucesivamente, teniendo (n-1) opciones para los restantes (2n-1) espacios. Luego, la fórmula quedaría:

\( n(n-1)^{2n-1} \)

Pero... eso no tiene nada que ver con la respuesta dada, es decir, con lo que hay que demostrar...
No solo no se parecen "de presencia", además arrojan resultados distintos...
Ej: para n=2, la fórmula dada arroja 4 palabras, mi fórmula tira 2. Para n=3 arrojan 30 y 96 respectivamente.
Contando las dichosas palabras, a lo "boludo", verifico que mi respuesta está bien !! (digamos, el alfabeto {0,1} tendría las palabras 1010 y 0101; y el alafabeto {a,b,c} tira 96 -esto lo hice con un árbol... no lo subo acá ya que no lo considero necesario-)
Entonces... qué estoy haciendo mal o qué es lo que realmente cuenta la dichosa formulita ?
La fórmula tiene "pinta" a inclusión-exclusión (por la intercalación de signos), pero no le encuentro forma.
Escrita en forma de sumatoria quedaría (si no me equivoco):

\( \displaystyle\sum_{i=0}^n{}(nci)(-1)^i2^i(2n-i)! \)

Y bueno, las palabras que yo conté no se excluyen entre sí de ningún modo (me creerán que en serio saqué las 96 palabras... y eso es una gran pérdida de tiempo).
Además me intriga que para un caso la fórmula a demostrar da mayor (n=2) y para el otro menor (n=3). So ?

Problema 10)
Número de subconjuntos de S = 2^|S| = 128.
Podríamos descontar el de tamaño 7 (que es único y por ende ningún otro podrá sumar lo mismo) y el vacío. Entonces nos quedan 126 (que es divisible entre 3... esto es como buena señal)
La máxima suma es 70. La mínima es 2. Hay varios números que "no salen", pero no encuentro una forma no "a prueba y error" (o más bien, haciendo la lista) de contarlos. Algunos de ellos son: 4,6,9,12, ... (no, tampoco tienen secuencia aparente)
Noté que todos los elementos de S son primos, supongo que eso tendrá parte importante en la solución (?)
Algo me decía que la respuesta saldría por el lado de que hay 42 sumas distintas posibles entre los elementos de S y que por el principio fuerte del palomar habrán cuando menos 4 subconjuntos de S tal que su suma es igual. Pero... 42 suena un número muy pequeño (si hubieran 42 sumas posibles, implicaría que no se pueden obtener 26 números entre el 2 y el 70, y eso suena demasiado). Y bueno, cómo contaría en tal caso las posibles sumas ? (obvio hacer una lista no sería óptimo... me echaría una media hora, ni se diga si extendieramos el problema a conjuntos más grandes)

Les agradescería mucho cualquier orientación. O si me dicen de algún ejercicio similar. He revisado varios ejercicios del tipo acá en este foro, pero no encuentro la forma.
Una aclaración para el 10): A pesar de que dice claro: "probar usando el principio del palomar", quiero aclarar (valga la redundancia) que la respuesta no se limita a decir "tienes por ejemplo los subconjuntos bla, ble, bli y blo cuya suma es blu y queda demostrado"

De este taller sale la evaluación que me harán (bueno, "2 ó 3 puntos de ella", aspiro que sean 4 ó 5 como mucho), y tengo la mala experiencia del parcial pasado de que el único punto que no logré hacer, el profesor lo colocó (Bueno, la "iluminación vino a mí" y pude colocar algunas cosillas que terminaron teniendo sentido xD, pero no quiero repetir eso -No, no hice copia, pero creo que le causé lastima al profesor o algo y me colocó más de lo que merecía...)

P.D: Ya posteé la pregunta en otro foro, pero no conseguí respuesta, agradezco a cualquiera que me oriente, por favor.
Perdonenme por subir las imágenes a un host externo, no se me da el uso del tex y no estoy muy de tiempo como para aprender :|

[Luis Fuentes]

Hola

 Bienvenido al foro.

 Recuerda leer y seguir  las reglas del mismo así como el tutorial del LaTeX para escribir las fórmulas matemáticas correctamente.

 Intentar usar el LaTeX no lleva tanto tiempo; piensa además que a todos aquellos que quieren ayudarte tampoco les sobra. Y parece razonable molestarse en colaborar con ellos.

 Por esta vez te han corregido alguna fórmula desde la administración (corrige tu las restantes eliminando los archivos alojados en servidores externos al foro).

 Por ejemplo para obtener:

\( \dfrac{1}{2^n}((2n)!-\displaystyle\binom{n}{1}2(2n-1)!+\displaystyle\binom{n}{2}2^2(2n-2)!+\ldots+(-1)^n2^nn!) \)

 debes de poner:

[tex]\dfrac{1}{2^n}((2n)!-\displaystyle\binom{n}{1}2(2n-1)!+\displaystyle\binom{n}{2}2^2(2n-2)!+\ldots+(-1)^n2^nn!)[/tex]

 En cuanto a los ejercicios:

 8. No está muy bien enunciado. Se refiere a palabras en las que cada letra aparezca exactamente dos veces, pero no de manera contigua.

 Entonces el número de palabras será. Entonces si llamamos \( A \) al conjunto de palabras con todas las letras dos veces, y a \( A_i \) el conjunto de palabras con todas las letras dos veces en las que la letra \( i \) aparece dos veces seguidas se tiene que, el número de palabras en las condiciones que te piden es:

\(  card(A)-\displaystyle\sum_{i=1}^n{}card(A_i)+\displaystyle\sum_{i,j=1, i<j}^n{}card(A_i\cap A_j)+\ldots+(-1)^ncard(A_1\cap \ldots \cap A_n) \)

 De ahí y usando permutaciones con repetición es fácil sacar la fórmula que te indican. Inténtalo.

9. Nota que las sumas más alta y más baja posibles son respectivamente 36 y 5. Por tanto hay 32 posibles sumas distintas. Pero hay \( 2^7 \) subconjuntos distintos. Concluye...

MAL.

Saludos.

CORREGIDO

[XXXXXXX]

Hola,
Ante todo, gracias por la respuesta (y corrección)

Pensaré el primer punto a ver si obtengo la fórmula, espero que así sea. Cualquier duda vuelvo y la comento.
Sobre el segundo (10), cómo es eso de que la mayor suma es 36 ? Eso sería solo considerando subconjuntos de 2 elementos, no ?
Y pues tal restricción no está dada (o bueno, quizá esa sea la razón, pero de donde sale ? Yo estaba casi seguro que la mayor suma era 70)

Gracias de nuevo.
P.D: Siento la mala redacción, voy tarde y me deja el bus 

[Luis Fuentes]

Hola

 Tienes razón respecto al segundo. Luego lo corrijo. Ahora he de irme.

Saludos.

[Luis Fuentes]

Hola

 No se me ocurre una forma demasiado obvia de resolver el ejercicio por el principo del palomar. El argumento ha de ser sutil, porque por ejemplo con los números \( \{2, 3, 4, 8, 16, 17, 19\} \) el resultado no es cierto.

 Una forma de probarlo sin el principio del palomar es tener en cuenta que:

\( 2+3=5,\qquad 11+19=17+13 \)

 De manera que agrupando dos a dos esos cuatro subconjuntos tenemos cuatro subconjuntos que suman \( 35 \).

Saludos.

[XXXXXXX]

Hola nuevamente,

Logré entender la fórmula, son permutaciones con repeticiones fijas, cierto ?
Contamos el total de palabras que sería algo como

\( \displaystyle\frac{(2+2+...+2)!}{2!2!...2!} = \displaystyle\frac{2n!}{2^n} \)
Luego le descontamos las que tienen una letra consecutiva (digamos "aa"):
La forma de escoger esa letra es 1 entre las n letras del alfabeto, i.e. \( \displaystyle\binom{n}{1} \)
Podemos conseguir esta cantidad de palabras:

\( \displaystyle\frac{(2+2+...+1)!}{2!2!...1!} = \displaystyle\frac{(2n-1)!}{2^{n-1}} \)
Luego le sumamos la intersección, que sería las palabras que tienen exactamente dos letras agrupadas de a dos:
Se pueden escoger esas dos letras 2 entre n, i.e. \( \displaystyle\binom{n}{2} \)
Podemos conseguir esta cantidad de palabras:

\( \displaystyle\frac{(2+2+...1+1)!}{2!2!...1!1!} = \displaystyle\frac{(2n-2)!}{2^{n-2}} \)

Y bueno, seguimos hasta las que tienen todas sus letras "agrupadas" de a dos.
Las podemos elegir \( \displaystyle\binom{n}{n} \) (y bueno, da uno... pero para conservar la idea)
De estas hay:

\( \displaystyle\frac{(1+1+...1+1)!}{1!1!...1!1!} = \displaystyle\frac{(n)!}{2^{0}} \)

Ahora, factorizamos ese \( 2^n \),
Otras manipulaciones que por mi limitado manejo de tex no pongo...
Y... tarán ?
(Está bien o fue purita casualidad que me saliera ?)

Sobre el punto dos (el 10), el profesor dijo que no sacará ese tema, igual, está interesante la justificación. (Había notado lo del \( 2+3=5 \), pero lo otro lo pasé por alto)

De nuevo, gracias.
Es el primer foro donde me responden satisfactoriamente 
(casi siempre ignoran mis preguntas)

Buena Noche.

[Luis Fuentes]

Hola

 Si, tu resolución del primer ejercicio es correcta. 

Saludos.

P.D. Gracias por esforzarte en usar el LaTeX.

Para poner exponentes de más de un caracter utiliza las llaves. Es decir:

- Si pones [tex]2^(n-1)[/tex] te sale \( 2^(n-1). \)

- Si pones [tex]2^{n-1}[/tex] te sale \( 2^{n-1}. \)