1. Contesta las preguntas en el Problema 2 para el caso de cinco escuelas.
3. Por cada tipo de pan, ¿cuántos sándwiches son posibles?
6. Intenta resolver el problema primero con un cono de dos puntas. (Busque un problema anterior que sea análogo.) Entonces, por cada cono de dos primicias, ¿de cuántas maneras puedes poner una pala superior?
7a. Pregúntate “¿para cuántas opciones tenemos\(f(1)\)?” Entonces pregunta para cuántas opciones tenemos\(f(2)\).
7b. Puede que no sea práctico anotar reglas para todas las funciones para este problema. Pero podrías preguntarte para cuántas opciones tenemos\(f(1)\), para cuántas tenemos\(f(2)\) y para cuántas tenemos\(f(3)\).
7c. Si estás eligiendo una función\(f\), ¿para cuántas opciones tienes\(f(a)\)? Entonces, ¿para cuántas opciones tienes\(f(b)\)?
8a. Ya sabes cómo averiguar de cuántas maneras podrían hacer una lista de tres sabores de los doce. Pero cada conjunto de tres sabores se puede enumerar de varias maneras diferentes. Trate de averiguar de cuántas maneras se puede enumerar un conjunto de tres sabores, y luego intente ver cómo esto le ayuda.
8b. Intenta dividir el problema en casos que puedas resolver por métodos anteriores; luego descubre cómo obtener la respuesta al problema usando estas respuestas para los casos.
12a. Supongamos que tiene una lista en orden alfabético de los nombres de los miembros del club. ¿De cuántas maneras puedes emparejar a la primera persona de la lista? ¿De cuántas maneras puedes emparejar a la siguiente persona que aún no está emparejada?
15. ¿De cuántas maneras puedes asignar a los hombres a sus filas? ¿Las mujeres? Una vez que una mujer y un hombre tienen una fila para compartir, ¿de cuántas maneras pueden elegir sus asientos?
18. Intente aplicar el principio del producto en el caso\(n = 2\) y\(n = 3\). ¿Cómo podría aplicarlo en general?
19. Pregúntese si se aplica el principio de suma o el principio de producto. Pista adicional: Recuerda que cero es un número.
20. ¿Ves una analogía entre este problema y alguno de los problemas anteriores?
26a. Para cada parte de este problema, piense en cuántas flechas se les permite ingresar a un vértice que representa a un miembro de\(Y\).
28. El problema es pedirle que describa una función uno a uno a partir del conjunto de representaciones binarias de números entre\(0\) y\(2n−1\) sobre el conjunto de subconjuntos del conjunto\([n]\). Anota estos dos conjuntos para\(n = 2\). Ambos deben tener cuatro elementos. El conjunto de representaciones binarias debe contener la cadena\(00\). Se podría pensar en esto como la instrucción de “no tomar a nadie y no tomar dos”. En ese contexto, ¿qué podría pensar de que\(11\) la cuerda representa? Esto debería ayudarte a describir una función. Por supuesto ahora hay que averiguar cómo demostrar que es uno a uno y sobre.
31. Empezando por la fila\(1 \;\;8 \;\;28 \;\;56 \;\;70\;\; 56\;\; 28\;\; 8\;\; 1\), pon puntos debajo de ella donde deben estar los elementos de la fila 9. Después pon puntos debajo de eso donde deberían estar los elementos de la fila 10. Haz lo mismo para las filas 11 y 12. Marque el punto donde debe aparecer la fila 12. Ahora marca los puntos que necesitas en la fila 11 para calcular la entrada en la columna 3 de la fila 12. Ahora marca los puntos que necesitas en la fila 10 para calcular las entradas marcadas en la fila 11. Haz lo mismo para las filas 9 y 8. Ahora deberías poder ver lo que necesitas hacer.
32a. Comience tratando de averiguar cuáles son las entradas justo por encima de la diagonal del rectángulo. Después de eso, ¿qué otras entradas puedes averiguar?
32b. Ve si puedes averiguar cuáles tienen que ser las entradas en la columna −1.
32c. ¿Cuál tiene que ser la suma de dos valores consecutivos en la fila −1? ¿Podría depender esta suma de qué dos valores consecutivos tomemos? ¿Hay algún valor de fila −1 que podamos elegir arbitrariamente? Ahora, ¿qué pasa con la fila −2? ¿Podemos tomar decisiones arbitrarias ahí? Si es así, ¿cuántos podemos hacer, y su posición es arbitraria?
36. Lo primero que hay que decidir es “¿Cuáles son los dos conjuntos cuyos elementos estamos contando?” Entonces será más fácil pensar en una beccion entre estos dos conjuntos. ¡Resulta que estos dos conjuntos son conjuntos de conjuntos!
37. Pregúntate “¿Qué es un problema como este haciendo en medio de un montón de problemas sobre contar subconjuntos de un conjunto? ¿Está relacionado, o se supone que nos da un respiro de los sets?”
38. El problema sugiere que piense en cómo obtener una lista de una disposición de asientos. ¿Podría cada lista de personas\(n\) distintas provenir de una tabla de asientos? ¿Cuántas listas de personas\(n\) distintas hay? ¿Cuántas listas podríamos obtener de una tabla de asientos dada tomando diferentes lugares de partida? Sugerencia adicional: Para una manera diferente de hacer el problema, supongamos que ha elegido a una persona, diga la primera en una lista de las personas en orden alfabético por nombre. Ahora asienta a esa persona. ¿Importa dónde se sientan? ¿De maneras puedes sentar a las personas restantes? ¿Importa dónde se sienta la segunda persona en orden alfabético?
39a. Un bloque consiste en todas las permutaciones de algún subconjunto\(\{a_1, a_2,..., a_k \}\) de\(S\). ¿Cuántas permutaciones hay del conjunto\(\{a_1, a_2,..., a_k \}\)?
39c. ¿Qué conjuntos se enumeran y cuántas veces se enumera cada uno si toma una lista de cada fila de la Tabla 1.2.8? ¿De qué manera esta elección de listas te da la beccion en este caso especial?
39d. Puedes hacer un buen uso del principio del producto aquí.
40b. El entrenador está tomando una secuencia de decisiones. ¿Puedes averiguar cuántas opciones tiene el entrenador para cada decisión en la secuencia?
40c. Al igual que con cualquier problema de conteo cuyo contexto no sugiera un enfoque, es útil preguntarse si podría descomponer el problema en partes más simples utilizando ya sea el principio de suma o producto.
43. ¿Cómo podríamos obtener una lista de cuentas de un collar? Pista adicional: Cuando cortamos el collar y lo cortamos en una mesa, hay\(2n\) listas de cuentas que podríamos obtener. ¿Por qué es\(2n\) más que\(n\)?
44a. Primero podrías elegir las parejas de personas. También podrías elegir hacer una lista de todas las personas y luego tomarlas a dos de la lista.
44b. Primero puedes elegir parejas ordenadas de personas, y hacer que la primera persona de cada par sirva primero. También podrías elegir hacer una lista de todas las personas y luego tomarlas a dos de la lista en orden.
45. Podría ser útil simplemente dibujar algunas imágenes de las posibles configuraciones. No hay tantos.
47. Tenga en cuenta que debemos caminar al menos diez cuadras, por lo que diez es el menor número de bloques posible. ¿En cuántas de esas diez cuadras debemos caminar hacia el norte?
48b. En Problema 47 viste que teníamos que tomar diez elecciones de norte o este, eligiendo el norte cuatro veces.
48c. Este problema es en realidad un poco complicado. ¿Qué pasa con la respuesta si\(i > m\) o\(j > n\)? Recuerda que los caminos van hacia arriba o hacia la derecha.
49a. ¿A dónde puedes ir\((0,0)\) en un solo paso? ¿En dos pasos? En cualquiera de estos casos, ¿qué se puede decir de la suma de las coordenadas de un punto al que puede llegar? ¿Se puede encontrar alguna otra relación entre las\(y\) coordenadas\(x\) - y -de un punto al que pueda llegar? Por ejemplo, ¿puedes ir al grano\((1, 3)\)?
49c. ¿Cuántas elecciones tienes que tomar para elegir un camino?
50c. En cada parte, cada una de esas secuencias corresponde a un camino que no puede cruzar (pero puede tocar) una cierta línea.
51b. Dado un camino desde el\((0, 0)\)\((n, n)\) que toca o cruza la línea\(y = x + 1\), ¿cómo se puede modificar la parte del camino desde el primer toque de\((0, 0)\) para\(y = x + 1\) que el camino modificado comience en su lugar en\((−1, 1)\)? El truco es hacer esto de manera sistemática que te dé tu bection.
51c. Un camino toca la línea\(y = x + 1\) o no lo hace. Esto divide el conjunto de caminos en dos bloques.
52b. Mirar hacia atrás en la definición de un Camino Dyck y un Sendero Catalán.
52c. Lo que dificulta esta parte es entender cómo estamos particionando los caminos. A modo de ejemplo,\(B_0\) es el conjunto de todos los caminos que no tienen repuntes siguiendo el último mínimo absoluto. ¿Un camino así puede tener bajadas después del último mínimo absoluto? (La descripción que dimos no\(B_0\) es lo suficientemente sucinta como para ser la respuesta a la segunda pregunta de esta parte.) Como otro ejemplo,\(B_1\) es el conjunto de todos los caminos que tienen exactamente un escalón y quizás algunos bajistas después del último mínimo absoluto. ¿Es posible, sin embargo, que un camino\(B_1\) de entrada tenga alguna bajada después del último mínimo absoluto? Un camino en\(B_2\) tiene exactamente dos repuntes después de su último mínimo absoluto. Si es posible tener un bajón después del último mínimo absoluto, pero tiene que estar en un lugar especial. ¿Qué lugar es ese? Ahora para averiguar cuántas partes tiene nuestra partición, necesitamos saber el número máximo de repuntes que puede tener una ruta siguiendo su último mínimo absoluto. ¿Cuál es este máximo? Podría ser útil dibujar algunas imágenes con\(n = 5\) o\(6\). En particular, ¿es posible que todos los repuntes ocurran después del último mínimo absoluto?
52e. Usando d para abajo y u para arriba, podríamos tener\(u\;u\;d\;d\;u\;u\;d\;d\;u\;d\;u\;d\) como nuestro camino catalán. Supongamos que\(i = 5\). El quinto repunte es el\(u\) en posición 9. Así\(F = u\;u\;d\;d\;u\;u\;d\;d\),\(U = u\), y\(B = d\;u\;d\). Ahora lo\(BUF\) es\(d\;u\;d\;u\;u\;u\;d\;d\;u\;u\;d\;d\). Este es un camino de Dyck que comienza por ir por debajo del\(x\) eje -eje. Los\(d\)'s en las posiciones 1 y 3 toman el camino a la\(y\) coordenada\(−1\). Entonces la\(y\) coordenada sube a\(2\), vuelve a\(0\), arriba de\(2\) nuevo, y finalmente baja a\(0\). Entonces el mínimo absoluto es\(−1\), y ocurre en la primera y tercera posición. Hay cinco tras\(u\) la tercera posición. Entonces este camino de Dyck está en el bloque\(B_5\) de nuestra partición. Ahora viene la pregunta crucial. ¿Por qué hubo cinco\(u\) tras ese último mínimo absoluto en la posición 3? Prueba con el mismo camino y\(i = 3\). Averigua por qué\(u\) hay tres después del último mínimo absoluto en la ruta resultante. Toda esta discusión debería explicar por qué cuándo\(i = 5\), el conjunto de todos los caminos catalanes se mapea en el conjunto\(B_5\). Manteniendo\(i = 5\) por un tiempo, tratar de ver por qué esta correspondencia entre los caminos catalanes y\(B_5\) es una beccion. Entonces, si es necesario, haz lo mismo con\(i = 3\). Esto debería darte suficiente información para hacer el caso general.
55. ¿Cuál tendría que ser el límite inferior de la suma para que este problema sea una aplicación rutinaria del teorema binomial?
56. ¿Para qué te da el teorema binomial\((x − y)^n\)?
57. Considerar\((x + y)^m(x + y)^n\). Pista adicional: ¿Qué\(\binom{m+n}{k}\) cuenta? ¿Qué\(\binom{m}{i} \binom{m}{k-1}\) cuenta?
58. Por ejemplo cuando\(n = 3\), tenemos\(\binom{3}{0} = \binom{3}{3}\) y\(\binom{3}{1} = \binom{3}{2}\). El número de subconjuntos de tamaño par es\(\binom{3}{0} + \binom{3}{2}\) y el número de subconjuntos de tamaño impar es\(\binom{3}{1} + \binom{3}{3}\), y las dos sumas se pueden emparejar en términos iguales. Cuando restamos el número de subconjuntos de tamaño impar del número de subconjuntos de tamaño par, el emparejamiento también nos da\(\binom{3}{0} - \binom{3}{1} + \binom{3}{2} - \binom{3}{3} = 0\).
59. Toma la derivada de algo interesante.
61. Para probar que cada función desde un conjunto\(S\) de tamaño\(n\) hasta un conjunto de tamaño menor que no\(n\) es uno-a-uno, debemos probar que independientemente de la función\(f\) que elegimos, siempre hay dos elementos, digamos\(x\) y\(y\), tal que\(f(x) = f(y)\).
62. El ejercicio anterior podría ayudarte a demostrar que si\(f\) es uno a uno, entonces está encendido. Pista adicional: El principio de suma puede ayudarte a demostrar que si\(f\) es una función onto, entonces\(f\) es uno a uno.
63. El enunciado del principio de casillero generalizado involucra el número de elementos en un bloque, por lo que es probable que un principio de conteo te ayude.
64. Puedes elegir un número específico para\(n\) si quieres. Observe que los dos últimos dígitos de las potencias de un primo distinto de dos no pueden representar un número par.
65. Si bien esto suena como un problema de principio de encasillamiento, el principio de encasillamiento ordinario no garantiza tres de algo.
67. Lo que suele dificultar que los estudiantes inicien este problema es el hecho de que acabamos de definir lo que\(R(4, 4)\) es, y no lo que significa que un número no sea\(R(4, 4)\). Entonces para empezar, tratar de anotar lo que significa decir no lo\(R(4, 4)\) es\(8\). Verás que hay dos cosas que pueden\(R(4, 4)\) evitar ser\(8\). Hay que averiguar cuál sucede y explicar por qué. Una de esas explicaciones podría involucrar a la gráfica\(K_8\).
68. Revisa el Problema 65 y tu solución al mismo.
69. \(a_i\)Sea el número de conocidos de persona\(i\). ¿Puedes explicar por qué la suma de los números\(a_i\) es par?
70. A menudo, cuando hay un contraejemplo, hay uno con mucha simetría. (Precaución: ¡hay una diferencia entre muchas veces y siempre!) Una forma de ayudarse a sí mismo a obtener un ejemplo simétrico, si lo hay, es poner\(8\) vértices en un círculo. Entonces, quizás, podrías dibujar bordes verdes de alguna manera regular hasta que sea imposible dibujar otro borde verde entre dos vértices cualesquiera sin crear un triángulo verde.
71. En Problema 68 lo demostraste\(R(4, 3) ≤ 10\). En Problema 70 lo demostraste\(R(4, 3) > 8\). Así\(R(4, 3)\) es\(9\) o bien\(10\). Decidir cuál es el caso es simplemente difícil. Pero hay un problema relevante que hemos hecho que aún no hemos usado.
72. Eso queremos demostrarlo\(\binom{n}{i} = \dfrac{n!}{i!(n−i)!}\). La inducción matemática nos permite suponer que\(\binom{n-1}{j} = \dfrac{(n−1)!}{j!(n−1−j)!}\) para cada\(j\) entre\(0\) y\(n − 1\). ¿Cómo nos pone esto en condiciones de usar la relación Pascal? ¿Qué casos especiales sobrarán?
73. ¿Qué tipo de relación conoces entre los valores de la forma\(\binom{n}{i}\) y los valores de la forma\(\binom{n−1}{j}\)?
75. Hicimos algo bastante similar en nuestro ejemplo de la prueba inductiva de que un conjunto con\(n\) elementos tiene\(2n\) subconjuntos. El trabajo que hiciste en un problema anterior puede ser similar a parte de lo que necesitas hacer aquí.
76a. Esto puede parecer difícil porque uno no puede decidir de antemano si tratar de inducir en\(m\), sobre\(n\), o sobre su suma. En cierto sentido, no importa en cuál elijas inducir, aunque inducir en la suma parecería más complicado. Para la mayoría de las personas que inducen en n se ajusta mejor a su forma de trabajar con exponentes.
76b. Aquí importa si eliges inducir en\(m\) o\(n\). No obstante, importa sólo en el sentido de que es necesario utilizar más herramientas en un caso. En un caso, es probable que necesites la regla\((cd)^n = c^n d^n\), que no hemos probado. (Sin embargo, ¡podrías probarlo por inducción!) En cualquier caso, puede encontrar la parte (a) útil
79. No dijimos explícitamente que se usara la inducción aquí, pero, sobre todo en este contexto, la inducción es una herramienta natural para probar aquí. Pero no tenemos una variable en\(n\) la que inducirnos. Eso significa que tienes que elegir uno. Entonces, ¿qué crees que es lo más útil? ¿El número de bloques en la partición? ¿El tamaño del primer bloque de la partición? El tamaño del conjunto que estamos particionando? ¿O algo más?
80. Piensa en cómo podrías haber pasado del número de conos de dos pisos al número de conos de tres pisos en el Problema 6.
81. Quizás lo primero que hay que preguntar es por qué probar que si hay\( \binom{m+n−2}{m−1} \) gente en una habitación, entonces hay al menos conocidos\(m\) mutuos o al menos extraños\(n\) mutuos prueba que eso\(R(m, n)\) existe. ¿Ves por qué esto nos dice que hay algún número\(R\) de personas tal que si hay\(R\) gente en una habitación, entonces hay conocidos\(m\) mutuos o extraños\(n\) mutuos? ¿Y por qué eso significa que existe el Número Ramsey? Consejo adicional: Naturalmente, no debería sorprendernos que usarás doble inducción, y puedes usar cualquiera de las dos formas. A medida que piensas en cómo usar la inducción, te vendrá a la mente la relación Pascal. Esto sugiere que quieres hacer suposiciones que involucren a\( \binom{m+n−3}{m−1} \) personas en una habitación, o\( \binom{m+n−3}{m−2} \) personas en una habitación. ¡Ahora tienes que averiguar cuáles son estas suposiciones y cómo te ayudan a probar el resultado! Recordemos que antes hemos avanzado eligiendo a una persona y preguntándonos si esta persona está familiarizada con al menos algún número de personas o desconoce al menos algún otro número de personas.
82. Uno espera necesitar de nuevo una doble inducción aquí. Pero sólo por la ubicación del problema y porque la suma parece doble inducción. Y esas razones no son suficientes para significar que hay que usar doble inducción. Si ya tenías este resultado en la mano, entonces podrías nosotros con doble inducción para dar una segunda prueba de que los Números Ramsey existen. Pista adicional: Lo que sí necesitas mostrar es que si hay\(R(m −1, n) + R(m, n−1)\) gente en una habitación, entonces hay o m conocidos mutuos o n extraños mutuos. Al igual que con problemas anteriores, ayuda comenzar con una persona y pensar en el número de personas con las que esta persona está familiarizada o no. El principio de encasillamiento generalizado te dice algo sobre estos números.
83b. Si pudieras encontrar cuatro conocidos mutuos, podrías asumir que la persona 1 está entre ellos. Y por el principio de encasillamiento generalizado y simetría, así son dos de las personas a la primera, segunda, cuarta y octava a la derecha. Ahora hay muchas posibilidades para esa cuarta persona. Ahora se tiene el arduo trabajo de usar la simetría y la definición de quién conoce a quién eliminar todas las combinaciones posibles de cuatro personas. Entonces hay que pensar en los desconocidos.
86a. ¿Cuál es la definición de\(R(n, n)\)?
86b. Si promedias un montón de números y cada uno es mayor que uno, ¿qué puedes decir del promedio?
86c. Tenga en cuenta que hay\(2^{\binom{n}{2}}\) gráficas en un conjunto de\(n\) vértices.
86d. Una notación para la suma sobre todas las coloraciones\(c\) de\(K_m\) es
\(\sum_{c:c \text{ is a coloring of } K_m} ,\)
y una notación para la suma de todos los subconjuntos\(N\) de\(M\) que tienen tamaño\(n\) es
\(\sum_{N:N⊆M, |N|=n}\)
86e. Si intercambias el orden de suma para que sumes primero sobre los subconjuntos y los colorantes en segundo lugar, puedes aprovechar que para un subconjunto fijo\(N\), puedes contar el número de colorantes en los que es monocromático.
86f. Tienes una desigualdad involucrada\(m\) y\(n\) eso te dice eso\(R(n, n) > m\). Supongamos que se podría trabajar con esa desigualdad para demostrar que si la desigualdad se mantiene, entonces\(m\) es mayor que algo. ¿De qué podrías concluir\(R(n, n)\)?
87. Recuerde, un subconjunto de\([n]\) cualquiera de los dos contiene o no\(n\).
90b. Una recurrencia de primer orden para nos\(a_n\)\(a_n\) da en función de\(a_{n−1}\).
91. Supongamos que ya sabías la cantidad de movimientos necesarios para resolver el rompecabezas con\(n − 1\) anillos.
92. Si tenemos\(n −1\) círculos dibujados de tal manera que definen\(r_{n−1}\) regiones, y dibujamos un nuevo círculo, cada vez que cruza otro círculo, excepto la última vez, termina de dividir una región en dos partes y comienza a dividir una nueva región en dos partes. Consejo adicional: Comparar\(r_n\) con el número de subconjuntos de un conjunto\(n\) de elementos.
98. Podrías intentar resolver los casos\(n = 2, 3, 4\) y luego buscar un patrón. Como alternativa, se podría escribir\(a_{n−1} = ba_{n−2} + d\), sustituir el lado derecho de esta expresión en\(a_n = ba_{n−1} + d\) para obtener una recurrencia que implique solamente\(a_{n−2}\), y luego repetir un proceso similar con\(a_{n−2}\) y tal vez\(a_{n−3}\) y ver un patrón que se está desarrollando.
102a. Hay varias formas de ver cómo hacer este problema. Una es dibujar dibujos de gráficos con un borde, dos bordes, tres bordes, quizás cuatro bordes y calcular la suma de los grados. Otra es preguntar qué le hace eliminar una arista a la suma de los grados. Otra es preguntar qué “aporta” un borde dado a la suma de los grados.
102b. Para hacer tu paso inductivo, piensa en lo que le sucede a una gráfica si borras una arista.
102d. Supongamos que en lugar de sumar el grado de\(v\) sobre todos los vértices\(v\), suma alguna cantidad definida para cada borde\(e\) sobre todos los bordes.
103. Lo que sea que digas debe ser consistente con lo que ya sabes sobre grados de vértices.
108. ¿Qué sucede si eliges una arista y la borras, pero no sus puntos finales?
109. Una aproximación al problema es utilizar hechos que ya conocemos sobre grados, vértices y aristas. Otro enfoque es intentar eliminar un borde de un árbol con más de un vértice y analizar los posibles números de vértices de grado uno en lo que queda.
111. Cuando llegues a cuatro y especialmente cinco vértices, dibuja todos los árboles sin etiquetar que se te ocurran, y luego descubre de cuántas maneras diferentes puedes poner etiquetas en los vértices.
112b. Haz algunos ejemplos.
112c. ¿Es posible\(a_1\) que sea igual a uno de los\(b_j\) s?
112d. Habéis visto que la secuencia\(b\) determina\(a_1\). ¿Determina alguna otra\(a_j\) s? Si supieras todas las\(a_j\) s y todas las\(b_j\) s, ¿podrías reconstruir el árbol? ¿Cuáles son los valores posibles de\(b_1\)? \(b_j\)?
113. ¿Qué vértice o vértices en la secuencia\(b_1, b_2,..., b_{n−1}\) pueden tener grado\(1\)?
115. Si un vértice tiene grado\(1\), ¿cuántas veces aparece en el código Prüfer del árbol? ¿Y un vértice de grado\(2\)?
116. ¿Cuántos vértices aparecen exactamente una vez en el código Prüfer del árbol y cuántos aparecen exactamente dos veces?
118. Piense en seleccionar un borde del árbol a la vez. Dado que has elegido algunos bordes y tienes una gráfica cuyos componentes conectados son árboles, ¿cuál es una buena manera de elegir el siguiente borde? Para demostrar que tu método es correcto, usa la contradicción asumiendo que hay un árbol de expansión con menor costo total. Consejo adicional: Piense en seleccionar un borde del árbol a la vez. Pero ahora hágalo de tal manera que un componente conectado sea un árbol y los otros componentes conectados tengan solo un vértice. ¿Cuál es una buena manera de convertir el componente que es un árbol en un árbol con un vértice más? Para probar que tu método funciona, usa la contradicción asumiendo que hay un árbol de expansión con menor costo total.
119a. Si tienes un árbol de expansión de\(G\) que contiene\(e\), ¿la gráfica que resulta de ese árbol al contraer\(e\) sigue siendo un árbol?
122c. Si decides ponerlo en una repisa que ya tiene libro, tienes dos opciones de dónde ponerlo en esa repisa.
122e. Entre todos los lugares se podrían poner libros, en todas las estanterías, ¿cuántos hay a la izquierda inmediata de algún libro? ¿Cuántos otros lugares hay?
123. ¿Cómo puedes asegurarte de que cada estantería obtenga al menos un libro antes de iniciar el proceso descrito en el Problema 122?
124. ¿Cuál es la relación entre el número de formas de distribuir libros idénticos y el número de formas de distribuir libros distintos?
125. Buscar una relación entre un multijuego de estantes y una forma de distribuir libros idénticos a estantes
126. Tenga en cuenta que\( \binom{n+k−1}{k} = \binom{n+k−1}{n−1} \). Entonces tenemos que averiguar cómo elegir\(k\) elementos o\(n − 1\) elementos de entre\(n + k − 1\) elementos constituye la elección de un multiconjunto. Realmente no tenemos idea de qué conjunto de\(n + k − 1\) objetos usar, entonces, ¿por qué no usar\([n + k −1]\)? Si elegimos\(n −1\) de estos objetos, hay\(k\) sobrantes, el mismo número que el número de elementos de nuestro multiset. Dado que se supone que nuestro multiset debe ser elegido de un conjunto\(n\) -element, tal vez deberíamos dejar que el conjunto\(n\) -element sea\([n]\). A partir de nuestra elección de\(n − 1\) números, tenemos que decidir sobre la multiplicidad de\(1\) través\(n\). Por ejemplo con\(n = 4\) y\(k = 6\), tenemos\(n + k − 1 = 9\). Aquí, se muestra con subrayados, una selección de\(3 = n − 1\) elementos de\([9]: 1, 2, \underline{3}, 4, \underline{5}, 6, 7, \underline{8}, 9\). ¿Cómo los elementos subrayados nos dan un multiconjunto de tamaño\(6\) elegido de un conjunto\([4]\) de elementos? En este caso,\(1\) tiene multiplicidad\(2\),\(2\) tiene multiplicidad\(1\),\(3\) tiene multiplicidad\(2\), y\(4\) tiene multiplicidad\(1\).
127. Una solución a las ecuaciones asigna un número no negativo a cada una de para\(1, 2,...,m\) que los números no negativos se sumen a\(r\). ¿Tal asignación tiene un significado combinatorio?
128. ¿Se te ocurre alguna manera de garantizar que cada destinatario obtenga\(m\) objetos (asumiendo\(k ≥ m\;n\)) justo al inicio del proceso de repartir los objetos?
129. Ya sabemos cómo colocar libros\(k\) distintos en estantes\(n\) distintos para que cada estante obtenga al menos uno. Supongamos que sustituimos los libros distintos por otros idénticos. Si permutamos los libros distintos antes del reemplazo, ¿afecta eso al resultado final? Hay otras formas de resolver este problema.
130. ¿Ves una relación entre composiciones y algo más que ya hemos contado?
131. Si alineamos libros\(k\) idénticos, ¿cuántas adyacencias hay entre libros?
133. Imagínese tomar una pila de\(k\) libros, y dividirla en pilas para ponerla en las cajas en el mismo orden en que originalmente estaban apiladas. Si vas a usar\(n\) cajas, ¿en cuántos lugares tendrás que dividir la pila en pilas más pequeñas, y de cuántas formas puedes hacer esto? Sugerencia adicional: ¿Cuántos arreglos de librerías diferentes corresponden a la misma manera de apilar\(k\) libros en n cajas para que cada caja tenga al menos un libro?
134. El número de particiones de\([k]\) en\(n\) partes en las que no\(k\) está en un bloque se relaciona con el número de particiones de\(k − 1\) en algún número de bloques de una manera que implica\(n\). Con esto en mente, revisa cómo probaste la ecuación de Pascal (recurrencia).
137. ¿Y si la pregunta se hace sobre seis sándwiches y dos bolsas distintas? ¿Cómo cambia la respuesta tener bolsas idénticas?
138. ¿Cuáles son los tamaños posibles de las piezas?
139. Supongamos que hacemos una lista de los\(k\) artículos. Tomamos los primeros\(k_1\) elementos para ser los bloques de tamaño\(1\). ¿Cuántos elementos necesitamos tomar para obtener\(k_2\) bloques de tamaño dos? ¿Qué elementos tiene sentido elegir para este propósito?
141. Para ver cuántas permutaciones rotas de un\(k\) elemento establecido en\(n\) partes no tienen\(k\) es una parte por sí misma, pregúntate cuántas permutaciones rotas de\([7]\) resultado de\(7\) sumar a la de las dos permutaciones en la permutación rota\(\{14, 2356\}\).
142b. Aquí es útil pensar en lo que sucede si borras todo el bloque que contiene en\(k\) lugar de pensar si\(k\) está en un bloque por sí mismo o no.
143. Se puede pensar en una función como asignar valores a los bloques de su partición. Si permutas los valores asignados a los bloques, ¿siempre cambias la función?
144. El código Prüfer de un árbol etiquetado es una secuencia de\(n − 2\) entradas que deben elegirse de los vértices que no tienen grado\(1\). La secuencia puede ser aunque como una función desde el conjunto\([n − 2]\) hasta el conjunto de vértices que no tienen grado\(1\). ¿Qué tiene de especial esta función?
145. Cuando agrega el número de funciones que se mapean\(J\) sobre todos los subconjuntos posibles\(J\) de\(N\), ¿cuál es el conjunto de funciones cuyo tamaño está calculando?
148. ¿Y si los\(j_i\)'s no se suman a\(k\)? Consejo adicional: Piense en enumerar los elementos del conjunto\(k\) -element y etiquetar los primeros\(j_1\) elementos con el número de etiqueta\(1\).
149. El principio de suma ayudará aquí.
150. En qué se diferencian los relevantes\(j_i\) en los coeficientes multinomiales que usas aquí de los\(j_i\)'s en el problema anterior.
151. Piense en cómo se relacionan los coeficientes binomiales con la expansión de una potencia de un binomio y observe que el coeficiente binomial\(\binom{n}{k}\) y el coeficiente multinomial\(\binom{n}{k,n−k}\) son los mismos.
152a. Hemos relacionado los números de Stirling con los poderes\(n^k\). ¿Cómo se relacionan los coeficientes binomiales con la caída de los poderes factoriales?
152b. En la ecuación\(\sum_{j=0}^{n} n^j-S(k, j) = n^k\), podríamos intentar\(x\) sustituir\(n\). Sin embargo no sabemos qué\(\sum_{j=0}^{x}\) significa cuándo\(x\) es una variable. ¿Hay algo más que n que haga un límite superior adecuado para la suma? (Piensa en lo que sabes\(S(k, j)\)).
153. Para la última pregunta, podrías intentar aprovechar el hecho de que\(x = x + 1 − 1\).
154. ¿Qué tiene que ver la inducción con la Ecuación (3.1)? Pista adicional: ¿Qué podrías asumir inductivamente sobre\(x^{\underline{k−1}}\) si estuvieras tratando de probar\(x^{\underline{k}} = \sum_{n=0}^{k} s(k, n)x^n\)?
156a. Hay una solución para este problema similar a la solución al Problema 154.
156b. ¿Te resulta familiar la recurrencia?
156d. Demuestre eso\((−x)^{\underline{k}} = (−1)^kx^{\underline{k}}\) y\((−x)^{\underline{k}} = (−1)^kx^{\underline{k}}\). Pista adicional: La primera pista te permite escribir una ecuación para\((−1)^kx^{\underline{k}}\) como un factorial ascendente de otra cosa y luego usar lo que sabes sobre expresar factoriales ascendentes en términos de factoriales descendentes, después de lo cual tienes que volver a convertir a poderes factoriales de\(x\).
162. ¿Cómo se puede comenzar con una partición de\(k\) y convertirla en una nueva partición de la\(k + 1\) que se garantiza que tenga una parte de tamaño uno, aunque la partición original no lo hiciera?
163. Dibuja una línea a través de la esquina superior izquierda y la esquina inferior derecha de la caja superior.
164. La mayor parte de una partición es el número máximo de cajas en una fila de su diagrama Young. ¿Qué nos dice el número máximo de cajas en una columna?
165. Dibuja todas las particiones autoconjugadas de números enteros menores o iguales a\(8\). Dibuja todas las particiones de enteros menores o iguales a\(8\) en distintas partes impares (muchas de estas tendrán solo una parte). Ahora intenta ver cómo llegar de un conjunto de dibujos a otro de manera consistente.
166. Dibuja las particiones de seis en partes pares. Dibuje las particiones de seis en partes utilizadas un número par de veces. Busque una relación entre un conjunto de diagramas y el otro conjunto de diagramas. Si tiene problemas, repita el proceso usando\(8\) o incluso\(10\) en lugar de\(6\).
167. Dibuja una partición de diez en cuatro partes. Supongamos que cada cuadrado tiene área uno. Luego dibuja un rectángulo de área que\(40\) encierra tu diagrama que toque la parte superior de tu diagrama, el lado izquierdo de tu diagrama y la parte inferior de tu diagrama. ¿Cómo te da este rectángulo una partición\(30\) en cuatro partes?
168c. Considerar dos casos,\(m′ > m\) y\(m′ = m\).
168d. Considerar dos casos,\(n′ > n\) y\(n′ = n\).
169. Supongamos que tomamos dos repeticiones de este proceso de complementación. ¿Qué filas y columnas eliminamos del diagrama? Pista adicional: Para hacer frente a un número impar de repeticiones del proceso de complementación, piense en ello como un número par más\(1\). Así preguntamos qué tipo de partición nos da la partición de una en una parte después de este proceso de complementación.
170. ¿Cuántas composiciones hay\(k\) en\(n\) partes? ¿Cuál es el número máximo de composiciones que podrían corresponder a una partición dada de\(k\) en\(n\) partes?
171a. Estas dos operaciones hacen cosas bastante diferentes a la cantidad de piezas, y se puede describir exactamente lo que solo una de las operaciones hace. Piensa en el diagrama Young.
171b. Piensa en el diagrama Young. En sólo uno de los dos casos se puede dar una respuesta exacta a la pregunta.
171c. Aquí la parte más dura requiere que, después de la eliminación, consideres un rango de posibles números que se están particionando y que le des un límite superior en el tamaño de la pieza. Sin embargo, te permite describir exactamente el número de piezas.
171d. Uno de los dos conjuntos de particiones de números menores de la parte anterior es más susceptible de encontrar una recurrencia que el otro. Sin embargo, la recurrencia resultante no tiene solo dos términos.
171h. Si hay una suma igual a cero, muy bien puede haber una partición de cero.
172. ¿Cómo se compara el número de composiciones de\(k\) en partes\(n\) distintas con el número de composiciones de\(k\) en\(n\) partes (no necesariamente distintas)? ¿Qué tienen que ver las composiciones con las particiones?
173. Si bien podría simplemente mostrar particiones de\(7\) en tres partes y particiones de\(10\) en tres partes, esperamos que no lo hará.Quizás podría anotar las particiones de\(4\) en dos partes y las particiones de\(5\) en dos partes distintas y buscar una bection natural entre ellos. Entonces la esperanza es que descubras una bection a partir del conjunto de particiones de\(7\) en tres partes y las particiones de\(10\) en tres partes distintas. Podría ayudar a dibujar los diagramas Young de particiones de\(4\) en dos partes y las particiones de\(5\) en dos partes distintas.
174. En el caso\(k = 4\) y\(n = 2\), tenemos\(m = 5\). En el caso\(k = 7\) y\(n = 3\), tenemos\(m = 10\).
175. ¿Qué puede hacer con un diagrama Young para una partición de\(k\) en partes\(n\) distintas para obtener un diagrama Young de una partición de\(k − n\) en algún número de partes distintas?
176. Para cualquier partición de\(k\) en partes\(λ_1\),\(λ_2\), etc. podemos obtener una partición de\(k\) en partes impares factorizando la mayor potencia de dos que podamos de cada una\(λ_i\), escribiendo\(λ_i = γ_i · 2_k^i\). ¿Por qué es\(γ_i\) extraño? Ahora\(k\) particiona en\(2^{k_1}\) partes de tamaño\(γ_1\),\(2^{k_2}\) partes de tamaño\(γ_2\), etc. y tienes una partición de\(k\) en partes impares.
177. Supongamos que tenemos una partición de\(k\) en distintas partes. Si la parte más pequeña, digamos\(m\), es menor que el número de partes, podemos agregar una a cada una de las partes más\(m\) grandes y eliminar la parte más pequeña, y hemos cambiado la paridad del número de partes, pero aún tenemos partes distintas. Por otro lado, supongamos que la parte más pequeña, nuevamente digamos\(m\), es mayor o igual que el número de partes. Entonces podemos restar\(1\) de cada parte mayor que\(m\), y sumar una parte igual al número de partes mayores que\(m\). Esto cambia la paridad del número de partes, pero si la segunda parte más pequeña lo es\(m + 1\), la partición resultante no tiene partes distintas. Por lo tanto, este método no funciona. Además, si siempre funcionaba, el caso\(k \neq \dfrac{3j^2+j}{2}\) quedaría cubierto también. Sin embargo, puede modificar este método comparando\(m\) no con el número total de partes, sino con el número de filas en la parte superior del diagrama Young que difieren exactamente en una de la fila anterior. Incluso en esta situación, hay ciertas suposiciones adicionales leves que debes hacer, por lo que esta pista te deja mucho trabajo por hacer. (Es razonable esperar problemas por ese caso excepcional.) No obstante, debería guiarte en una dirección útil.
183. Sustituye algo por\(A\),\(P\) y\(B\) en tu fórmula del Problema 181.
184. Por ejemplo, para obtener el costo de la selección de frutas\(APB\) te gustaría obtener\(x^{20}x^{25}x^{30} = x^{75}\).
186. Considera el ejemplo con\(n = 2\). Entonces tenemos dos variables,\(x1\) y\(x2\). Olvidando\(x_2\), ¿qué suma dice que\(x_1\) o tomamos o no? Olvidando\(x_1\), ¿qué suma dice que\(x_2\) o tomamos o no? Ahora bien, ¿qué producto dice que tomamos\(x_1\) o no y\(x_2\) o tomamos o no?
188. Para las dos últimas preguntas, intenta multiplicar primero algo más sencillo, digamos\((a_0+a_1x+a_2x^2)(b_0+b_1x+b_2x^2)\). Si este problema parece difícil la parte que parece causar a los estudiantes la mayor cantidad de problemas es convertir la expresión que obtienen para un producto como este en notación de suma. Si estás teniendo este tipo de problema, expande el producto (a_0 + a_1x + a_2x^2) (b_0 + b_1x + b_2x^2) y luego averiguar cuál\(x^2\) es el coeficiente de. Intenta escribir eso en notación sumatoria.
189. Anote las fórmulas para los coeficientes de\(x^0\)\(x^1\),\(x^2\) y\(x^3\) en
\[ \left( \sum_{i=0}^{n} a_ix^i \right) \left( \sum_{j=0}^{m} b_jx^j \right).\]
190. ¿En qué se diferencia este problema del Problema 189? ¿Es esta una diferencia importante desde el punto de vista del coeficiente de\(x^k\)?
191. Si este problema parece difícil, la razón más probable es porque las definiciones son todas nuevas y simbólicas. Enfócate en lo que significa\(\sum_{k=0}^{\infty} c_kx^k\) para ser la función generadora de pares ordenados de valor total\(k\). En particular, ¿cómo obtenemos un par ordenado con valor total\(k\)? ¿Qué necesitamos saber sobre los valores de los componentes del par ordenado?
192b. Podrías intentar aplicar el principio del producto para generar funciones a una potencia apropiada de la función generadora que obtuviste en la primera parte de este problema. Consejo adicional: En el Problema 125 encontraste una fórmula para el número de multisets\(k\) -elementos elegidos de un conjunto\(n\) -element. Supongamos que usa esta fórmula para ak in\(\sum_{k=0}^{\infty} a_kx^k\). ¿Para qué obtienes la función generadora?
195. Si bien podrías usar técnicas de cálculo, hay un enfoque mucho más simple. Tenga en cuenta que\(1 + x = 1 − (−x)\). Pista adicional: ¿Puedes ver una forma de usar el Problema 194?
197. Busque un poder de un polinomio para comenzar. Pista adicional: El polinomio al que se hace referencia en la primera pista es un cociente de dos polinomios. El poder del denominador puede escribirse como una serie de potencias.
198. Interpretar Problema 197 en términos de multiconjuntos.
199e. Cuando se\(x_1x_2 ··· x_n\) factoriza del enumerador de árboles, el resultado es una suma de términos de grado\(n − 2\). (El grado de\(x_1^{i_1} x_2^{i_2} ··· x_n^{i_n}\) es\(i_1 + i_2 + ··· + i_n\)). Sugerencia adicional: Anote la imagen (usando\(x\) s) de un árbol en cinco vértices con dos vértices de grado uno, de uno con tres vértices de grado uno, y con cuatro vértices de grado\(1\). Factor\(x_1x_2x_3x_4x_5\) fuera de la imagen y mira lo que queda. ¿Cómo se relaciona con tus vértices de grado uno? Ahora quita los vértices de grado\(1\) del árbol y anota la imagen del árbol que queda. Qué tienen de especial los vértices de grado\(1\) de ese árbol. (Apenas se puede aprender algo de esto con cinco árboles de vértices, así que es posible que desee experimentar un poco con seis o siete árboles de vértices).
200. Este es un buen lugar para aplicar el principio del producto para los enumeradores de imágenes.
201a. El principio del producto para generar funciones le ayuda a dividir la función generadora en un producto de diez funciones más simples.
201b. \(m\)estaba\(10\) en la parte anterior de este problema.
202. Piense en particiones conjugadas.
203a. No tengas miedo de anotar un producto de infinitamente muchas series de poder.
203b. A partir del quinto factor, no hay forma de elegir un\(q^i\) que tenga\(i\) distinto de cero y menos de cinco del factor.
203d. Describe a ti mismo cómo obtener el coeficiente de un poder dado de\(q\).
204. Si infinitamente muchos de los polinomios tuvieran un coeficiente distinto de cero para\(q\), ¿tendría algún sentido el producto?
205. \((1+ q^2 + q^4)(1+ q^3 + q^9)\)es la función generadora para particiones de un entero en como máximo dos dos y como máximo dos tres.
206. \((1+ q^2 + q^4)(1+ q^3 + q^9)\)es la función generadora para particiones de un entero en como máximo dos dos y como máximo dos tres. (Esta es intencionalmente la misma pista que en el problema anterior, pero tiene un punto diferente en este problema).
207. En la serie power\( \sum_{j=0}^{\infty} q^{2ij}\), el\(2ij\) tiene una interpretación diferente si lo piensas como\((2i) · j\) o si lo piensas como\(i · (2j)\).
208. Tenga en cuenta que
\(\dfrac{1 − q^2}{1 − q} · \dfrac{1 − q^4}{1 − q^2} · \dfrac{1 − q^6}{1 − q^3} · \dfrac{1 − q^8}{1 − q^4} = \dfrac{(1 − q^6)(1 − q^8)}{(1 − q)(1 − q^3)}\).
209. Tenga en cuenta que\(q^i + q^{3i} + q^{5i} + ··· = q^i (1 + q^2 + q^4 + ···)\).
210a. Queremos calcular el número de particiones cuyos diagramas Young encajan en un cuadrado de dos por dos. Estas particiones tienen como máximo dos partes y las partes tienen tamaño como máximo dos. Así son particiones de\(1\),\(2\),\(3\), o\(4\). Sin embargo, no todas las particiones de\(3\) o\(4\) tienen diagramas que encajan en un cuadrado de dos por dos. Intente anotar los diagramas relevantes.
210b. Son la función generadora para el número de particiones cuyo diagrama Young encaja en un rectángulo\(n−1\) unidades de ancho y\(1\) unidad de profundidad o en una\(1\) unidad rectangular de ancho y\(n − 1\) unidades de profundidad respectivamente.
210c. ¿Cómo se puede obtener un diagrama de una partición contada por partición es contada por\(\left[ \begin{array}{ll} m+n \\ \;\;\;n \end{array} \right]_q\) a partir de una cuya partición es contada por\(\left[ \begin{array}{ll} m+n \\ \;\;\;m \end{array} \right]_q\)?
210e.iii. Piense en operaciones geométricas en Young Diagramas
210f. ¿Cómo utilizaría la recurrencia Pascal para probar el resultado correspondiente para los coeficientes binomiales?
210g. Para encontrar una beccion, piensa en caminos de celosía.
210h. Si pudieras probar que\(\left[ \begin{array}{ll} m+n \\ \;\;\;n \end{array} \right]_q\) es una función polinómica de\(q\), ¿qué te diría eso sobre cómo calcular el límite a medida que se\(q\) aproxima\(−1\)? Consejo adicional: Intente calcular una tabla de valores de\(\left[ \begin{array}{ll} m+n \\ \;\;\;n \end{array} \right]_q \) con\(q = −1\) usando la relación de recurrencia. Haz una mesa bastante grande para que veas lo que está pasando.
211c. Puede encontrarse con un producto del formulario\(\sum_{i=0}^{\infty} a^i x^i \sum_{j=0}^{\infty} a^j x^j\). Tenga en cuenta que en el producto, el coeficiente de\(x^k\) es\(\sum_{i=0}^{k} a^i b^{k-i} = \sum_{i=0}^{k} \dfrac{a^i}{b^i} \).
214. Nuestra recurrencia se vuelve\(a_n = a_{n−1} + a_{n−2}\).
217.
\(\dfrac{5x + 1}{(x − 3)(x − 5)} = \dfrac{cx + 5c + dx − 3d}{(x − 3)(x − 5)}\)
nos da
\(5x = cx + dx\)
\(1=5c − 3d\).
218. Para tener
\(\dfrac{ax + b}{(x − r1)(x − r2)} = \dfrac{c}{x − r_1} + \dfrac{d}{x − r_2}\)
debemos tener
\(cx − r_2c + dx − r_1d = ax + b\).
221. Puede ahorrarse una tremenda cantidad de álgebra frustrante si elige arbitrariamente una de las soluciones y la llama\(r_1\) y llama a la otra solución\(r_2\) y resuelve el problema usando estos símbolos algebraicos en lugar de las raíces reales. 1 No sólo te ahorrarás algo de trabajo, sino que obtendrás una fórmula que podrías usar en otros problemas. Cuando haya terminado, sustituya en los valores reales de las soluciones y simplifique.
222a. Una vez más se ahorrará mucho álgebra tediosa si usas los símbolos\(r_1\) y\(r_2\) para las soluciones como en el Problema 221 y sustituyes los valores reales de las soluciones una vez que tengas una fórmula para\(a_n\) en términos de\(r_1\) y\(r_2\).
222d. Piensa en cómo te puede ayudar el teorema binomial.
224a. Un camino catalán podría tocar el\(x\) eje varias veces antes de que llegue\((2n, 0)\). Su primer toque puede ser cualquier punto\((2i, 0)\) entre\((2, 0)\) y\((2n, 0)\). Para que el camino toque primero a las\((2i, 0)\), el camino debe comenzar con un repunte y luego proceder como un sendero Dyck de\((1, 1)\) a\((2i−1, 1)\). A partir de ahí debe dar un paso a la baja. ¿Se ve una beccion entre tales caminos Dyck y caminos catalanes de cierto tipo?
224b. ¿El lado derecho de la recurrencia te recuerda algunos productos con los que has trabajado?
224c.
\(\dfrac{1 · 3 · 5 ···(2i − 3)}{i!} = \dfrac{(2i − 2)!}{(i − 1)!2^i i!}\).
226. Intente dibujar un Diagrama de Venn.
228. Intente dibujar un Diagrama de Venn.
231b. Para cada alumno, ¿qué tan grande es el conjunto de distribuciones de mochilas en las que ese alumno obtiene la mochila correcta? Podría ser una buena idea considerar primero casos con\(n = 3\),\(4\), y\(5\). Pista adicional: Para cada par de alumnos (digamos Mary y Jim, por ejemplo) qué tan grande es el conjunto de distribuciones de mochilas en las que los alumnos de esta pareja obtienen la mochila correcta. ¿Qué tiene que ver la pregunta con uniones o intersecciones de conjuntos? Sigue aumentando el número de alumnos para los que haces este tipo de preguntas.
232. Prueba la inducción. Consejo adicional: Podemos aplicar la fórmula del Problema 226 para obtener
\(\begin{equation} \begin{split} \left| \bigcup_{i=1}^{n} A_i \right| &= \left| \left( \bigcup_{i=1}^{n-1} A_i \right) ∪ A_n \right| \\ &= \left| \bigcup_{i=1}^{n-1} A_i \right| + |A_n| - \left| \left( \bigcup_{i=1}^{n-1} A_i \right) ∩ A_n \right| \\ &= \left| \bigcup_{i=1}^{n-1} A_i \right| + |A_n| - \left| \bigcup_{i=1}^{n-1} A_i ∩ A_n \right| \end{split} \end{equation}\)
233b. Que\(T\) sea el conjunto de todos\(i\) esos que\(x ∈ A_i\). En términos de\(x\), ¿qué hay de diferente\(i\) en el in\(T\) y en los que no están\(T\)? Pista adicional: Puede llegar a un punto en el que el teorema del binomio sería útil.
235. Observe que es sencillo averiguar cuántas formas podemos repartir las manzanas para que el niño\(i\) obtenga cinco o más manzanas: dale cinco manzanas al niño\(i\) y luego repartir las manzanas restantes como elija. Y si queremos averiguar de cuántas maneras podemos repartir las manzanas para que un conjunto determinado\(C\) de niños cada uno obtenga cinco o más manzanas, le damos cinco a cada niño adentro\(C\) y luego repartimos\(k − 5|C|\) las manzanas restantes como queramos.
236. Comience con dos preguntas que puedan aplicarse a cualquier problema de inclusión-exclusión. ¿Crees que sería mejor tratar de calcular el tamaño de una unión de conjuntos o el tamaño de un complemento de una unión de conjuntos? ¿Qué tipo de conjuntos (que son concebiblemente útiles para usted) es fácil calcular el tamaño de? (La segunda pregunta se puede interpretar de diferentes maneras, y para cada forma de interpretarla, la respuesta puede ayudarte a ver algo que puedes usar para resolver el problema). Pista adicional: Supongamos que tenemos un conjunto\(S\) de parejas a las que queremos sentar lado a lado. Podemos pensar en alinear\(|S|\) parejas y personas\(2n − 2|S|\) individuales en un círculo. ¿De cuántas maneras podemos organizar tantos artículos en un círculo?
237. Razón algo como lo hiciste en el Problema 236, señalando que si el conjunto de parejas que sí se sientan lado a lado no está vacío, entonces el sexo de la persona en cada lugar de la mesa se determina una vez que sentamos a una pareja en ese conjunto. Pista adicional: Piense en términos de los conjuntos\(A_i\) de arreglos de personas en las que la pareja\(i\) se sienta lado a lado. ¿Qué tiene que ver la unión de los conjuntos\(A_i\) con el problema?
239. ¿Qué tiene que ver el Problema 238 con esta pregunta?
242a. Para\(F\) que cada borde en conecte dos vértices del mismo color, debemos tener todos los vértices en un componente conectado de la gráfica con conjunto de vértices\(V\) y conjunto de bordes\(F\) coloreados del mismo color.
242c. ¿Cómo se relaciona el número que intentas calcular con la unión de los conjuntos\(A_i\)?
243. Una forma de obtener una coloración adecuada de\(G − e\) es comenzar con una coloración adecuada de\(G\) y eliminar\(e\). Pero hay otros colorantes de\(G\) que se vuelven adecuados cuando se quita\(e\).
246. Un enfoque sería tratar de adivinar el resultado haciendo un montón de ejemplos y usar la inducción para demostrar que tienes razón. Si intentas esto, ¿qué vas a poder utilizar para que el paso de inducción funcione? También hay otros enfoques.
253a. ¿Qué\(\varphi^n ◦ \varphi^{−1}\) quieres ser?
254. Si\(σ^i = σ^j\) y\(i \neq j\), ¿sobre qué se puede concluir\(ι\)?
256b. ¿Qué significa que una función sea la inversa de otra?
261. Una vez que sabes dónde van las esquinas de la plaza bajo la acción de una isometría, ¿cuánto sabes de la isometría?
264. ¿De cuántas maneras puedes elegir un lugar al que puedas moverte vértice\(1\)? Habiendo hecho eso, ¿de cuántas maneras puedes colocar los tres vértices adyacentes al vértice\(1\)?
265a. ¿De cuántas maneras puedes elegir un lugar al que puedas moverte vértice\(1\)? Habiendo hecho eso, ¿de cuántas maneras puedes colocar los tres vértices adyacentes al vértice\(1\)?
265b. ¿Por qué es suficiente enfocarse en permutaciones que toman vértice\(1\) a sí mismo?
270. Si un subgrupo contiene, digamos,\(ρ^3\) y algo de volteo, ¿cuántos elementos de\(D_4\) debe contener?
272. Si la lista\((i σ(i) σ^2(i) ... σ^n(i))\) no tiene elementos repetidos pero la lista\((i σ(i) σ^2(i) ... σ^n(i) σ^{n+1}(i))\) tiene elementos repetidos, entonces ¿qué elemento o elementos son repeticiones?
277. El elemento\(k\) está o bien en un ciclo por sí mismo o no lo está.
286. Antes de intentar demostrar que\(\overline{\overline{σ}}\) en realidad es una permutación de los colorantes, sería útil verificar la segunda parte de la definición de una acción de grupo, a saber, esa\(\overline{\overline{σ}} ◦ \overline{\overline{\varphi}} = \overline{\overline{σ ◦ \varphi}}\).
289. Si\(z ∈ Gx\) y\(z ∈ G y\), ¿cómo se pueden utilizar elementos de\(G\) para explicar la relación entre\(x\) y\(y\)? Pista adicional: Supongamos que\(σ\) es un miembro fijo de\(G\). Como\(τ\) rangos sobre\(G\), ¿qué elementos de\(G\) ocurren como\(τσ\)?
295. ¿Cómo se compara el tamaño de una multiórbita con el tamaño de\(G\)?
301. Estamos pidiendo el número de órbitas de algún grupo en listas de cuatro\(R\) s, seis\(B\) s, y siete\(G\) s.
305. Hay cinco tipos de elementos en el grupo de rotación del cubo. Por ejemplo, hay seis rotaciones por\(90\) grados o\(270\) grados alrededor de un eje que conecta los centros de dos caras opuestas y hay\(8\) rotaciones (de\(120\) grados y\(240\) grados, respectivamente) alrededor de un eje que conecta dos vértices diagonalmente opuestos.
306. ¿Es posible que una rotación no trivial arregle algún color?
309. Hay\(48\) elementos en el grupo de automorfismos de la gráfica. Consejo adicional: Para este problema, puede ser más fácil preguntar qué elementos de grupo fijan una coloración en lugar de qué colorantes son fijados por un elemento de grupo.
326. El grupo de automorfismos de la gráfica tiene\(48\) elementos y contiene\(D_6\) como subgrafo. Pista adicional: Las permutaciones con cuatro ciclos y los dos ciclos\((1 \; 4)\),\((2 \; 5)\), o\((3 \; 6)\) están en el grupo de automorfismos. Una vez que conoces la estructura del ciclo de\(D_6\) y\((1\; 4)D_6 = \{(1\; 4)σ|σ ∈ D_6\}\), conoces la estructura del ciclo de cada elemento del grupo.
327. ¿Qué tiene que ver el grupo simétrico en cinco vértices con este problema?
329c. En la relación de una función, ¿cuántos pares\((x, f(x))\) tienen el mismo\(x\) -valor?
332. Para la segunda pregunta, ¿cuántas flechas tienen que dejar el conjunto vacío? ¿Cuántas flechas tienen que dejar un conjunto de talla uno?
339. ¿De qué es el dominio\(g ◦ f\)?
345. Si tenemos bolas de vainilla, chocolate y fresa sentadas en círculo en un plato, ¿podemos distinguir entre VCS y VSC?
349. Para mostrar una relación es una relación de equivalencia, hay que demostrar que satisface la definición de una relación de equivalencia.
353. Para comenzar, en Problema 38 las clases de equivalencia corresponden a arreglos de asientos.
361. Probablemente has adivinado que la suma es\(n^2\). Para probarlo por contradicción, hay que asumir que es falso, es decir, que hay\(n\) tal que\(1+3+ 5 + ··· + 2n − 1 \neq n^2\). Entonces el método del Problema 360 dice que debe haber un tal más pequeño\(n\) y sugiere que lo llamemos\(k\). ¿Por qué lo sabes\(1+3+5+ ··· + 2k − 3=(k − 1)2\)? ¿Qué pasa si agregas\(2n − 1\) a ambos lados de la ecuación?
365. Probablemente ya lo has visto, con valores pequeños de\(n\), a veces\(n^2\) y a veces\(2^n\) es mayor. Pero si sigues experimentando una de las funciones parece hacerse más grande y permanecer más grande que la otra. El número\(n = b\) donde ocurre este cambio es una buena opción para un caso base. Para no estropear el problema por ti, no vamos a decir aquí de qué\(b\) es este valor. No obstante, no deberías sorprenderte más adelante en la prueba si necesitas usar la suposición de que\(n/g\;t\;b\). Pista adicional: Es posible que hayas llegado al punto de asumir eso\(2^{k−1} > (k − 1)^2\) y te hayas encontrado preguntándote cómo probarlo\(2^k > k^2\). Algo natural para probar es multiplicar ambos lados de\(2^{k−1} > (k − 1)^2\) por\(2\). Esto termina dándote\(2^k > 2k^2 − 4k + 2\). En base a la experiencia previa es natural que esperes ver cómo convertir este nuevo lado derecho en\(k^2\) pero no ver cómo hacerlo. Aquí está la pista. Solo necesitas demostrar que el lado derecho es mayor o igual a\(k^2\). Para ello, es necesario demostrar que uno de los dos\(k^2\) s en de\(2k^2\) alguna manera equilibra el\(−4k\). A ver si puedes averiguar cómo te\(k > b\) puede ayudar el hecho de que solo estés considerando\(k\) s con.
366. Cuando sospechas que un argumento no es válido, puede ser útil probar explícitamente varios valores de\(n\) para ver si tiene sentido para ellos. A menudo, los valores pequeños de\(n\) son adecuados para encontrar el defecto. Si encuentras una falla, invalida todo lo que viene después (a menos que, por supuesto, puedas arreglar la falla).
370. Podrías comenzar ignorando la palabra único y dar una prueba del teorema más simple que resulta. Entonces mira tu prueba para ver cómo puedes incluir la singularidad en ella.
377. Un problema anterior puede ayudarte a poner tu respuesta en una forma más simple.
378. ¿Cuál es la representación de la serie de poder\(e^{x^2}\)?
381. Sólo hay un elemento que puedes elegir. En el primer caso, o lo eliges o no.
387b. En algún momento, puede que le resulte útil el teorema binomial.
391. Obsérvese que cualquier permutación es producto de un desajuste de los elementos no fijados por la permutación multiplicada por una permutación cuya descomposición de ciclo consiste en un ciclo.
392. Es probable que aparezca un coeficiente binomial en tu respuesta.
397. Si\(f(x) = \sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!} \) y\(g(x) = \sum_{j=0}^{\infty} b_j \dfrac{x^j}{j!} \), ¿cuál es el coeficiente de\(\dfrac{x^n}{n!}\) in\(f(x)g(x)\)? No se sorprenda si su respuesta tiene un coeficiente binomial en ella. De hecho, el coeficiente binomial debería ayudarte a acabar con el problema.
399. Dado que los conjuntos de una estructura\(k\) -set no están vacíos y disjuntos, el conjunto de conjuntos\(k\) -element se puede organizar como una\(k\) -tupla de\(k!\) maneras.
403. La definición alternativa de un funciton en la Sección 3.1.2 puede reafirmarse para decir que una función de un conjunto\(k\) -elemento\(K\) a un conjunto\(n\) -elemento\(N\) puede ser pensada como una\(n\) -tupla de conjuntos, tal vez con algún vacío, cuya unión es\(K\). Para pensar en la función como una\(n\) -tupla, numeramos los elementos de\(N\) como número\(1\) a número\(n\). Entonces el\(i^{\text{th}}\) conjunto en la\(n\) -tupla es el conjunto de elementos mapeados al\(i^{\text{th}}\) elemento de\(N\) en nuestra numeración?
404. No se sorprenda si ve un seno hiperbólico o un coseno hiperbólico en su respuesta. Si no estás familiarizado con estas funciones, búscalas en un libro de cálculo.
407. El EGF para\(\sum_{i=1}^{n} \binom{n}{k} k\) es\(\sum_{n=1}^{\infty} \sum_{i=1}^{n} \dfrac{n!}{k!(n−k)!} k \dfrac{x^n}{n!}\). Puedes cancelar los\(n!\) términos y los\(k\) términos. Ahora intenta ver si lo que queda puede considerarse como el producto de dos EGF.
421a. Para aplicar la fórmula exponencial, debemos tomar la función exponencial de un EGF cuyo término constante es cero, o en otras palabras, para una especie de estructuras que no tiene estructuras que utilicen el conjunto vacío.
421b. Una vez que conoces el conjunto de vértices de una gráfica, todo lo que tienes que hacer para especificar la gráfica es especificar su conjunto de aristas.
421d. ¿Cuál es la definición de cálculo\(\log (1 + y)\)?
421f. Busque una fórmula que implique sumar sobre todas las particiones del entero\(n\).
