Actualmente estoy aprendiendo algunos conceptos básicos de la combinatoric técnicas en una clase que se llama "Introducción a la Combinatoria", y mientras que todo el material tiene perfecto sentido y los pasos son siempre claros después de los hechos -, no puedo por la vida de mí parecen derivar nada por mi propia cuenta.
Como un ejemplo, estábamos aprendiendo sobre el uso de bijections para demostrar que dos conjuntos tienen igual cardinalidad. Si usted tiene un conjunto $A$, que es difícil de contar, y de un conjunto $B$, lo que es fácil de contar, y un bijection $f:A\to B$,$\|A\| = \|B\|$. Así que he aquí un ejemplo de problema en uno de los trabajos:
Muestran que el número de $k$-multisubsets de $[n]=\{1,2,\cdots, n\}$ es $$ {n+k-1\elegir k} $$ donde un $k$-multisubset de $[n]$ $k$- tupla $(a_1,\cdots, a_k)$$a_i\in[n]$, e $1\le a_i\le a_{i+1}\le n$.
He trabajado más de esto por mientras, pero yo simplemente no podía encontrar un bijection entre el conjunto de $k$-multisubsets de $[n]$ y el conjunto de $k$-subconjuntos de a $[n+k-1]$. Me aparece fuera de toneladas de los casos, se extendía a mi imaginación para llegar con cualquier y todas las ideas que he podido, pero nada funcionó en general, sólo funcionó para "que el caso". Entonces, le pregunté a un amigo, y la respuesta es aparentemente esto:
$$ f(\vec a) = \vec + (0, 1, 2,\cdots, k - 1) $$ (donde el resultado se interpreta como un conjunto). Después del hecho, que parece tan obvio que esto debe ser el resultado (o que el bijection debería ser algo como esto). La idea básica de este bijection es "quitar" los casos en que $a_i = a_{i+1}$. Me reconoció que tenía que quitar esa restricción, pero me quedé pensando en "bijections" $f(a)\to b$ donde si $a_i = a_{i+1}$ $b_i = b_{i+1}-1$ (trabajo de forma incremental, de modo que si $a_i = a_{i+1} = a_{i+2}$$b_i = b_{i+1}-1 = b_{i+2}-2$), pero esto no funcionó.
He aquí otro ejemplo de algo que hicimos en clase: encontrar el número de particiones de $n$ con partes en $A\subseteq\mathbb{N}$. La solución es para denotar $S = \{\emptyset\}\cup A\cup A^2\cup A^3\cup\cdots$, y, a continuación, definir una función peso $w:S\to\mathbb{N}$ $w(\alpha) = \sum_{a\in\alpha}a$ (e $w(\emptyset) = 0$). A continuación, el número de particiones de $n$ con partes en $A$ está dado por $\|\{a\in S\ |\ w(a)=n\}\|$, que también se da por $$ \begin{aligned} [x^n]\sum_{a\in S}x^{w(a)} & = [x^n]\sum_{k\ge 0}\sum_{a\in A^k}x^{w(a)} \\ & = [x^n]\sum_{k\ge0}\left(\sum_{a\in A}x^{w(a)}\right)^k \\ & = [x^n]\left(1-\sum_{a\in A}x^{w(a)}\right)^{-1} \end{aligned} $$ Estoy totalmente de entender la maquinaria en juego aquí, y no tienen reparos con la obtención de este resultado. En clase hicimos ejemplos como el de al $A = \mathbb{N}\backslash\{3\}$, y no tengo ningún problema. Sin embargo, ahora estoy enfrentado con este problema:
Determinar el número de $c_n$ de las composiciones de $n$ en el que no hay pares consecutivos, incluso de las piezas mediante la generación de funciones.
...y estoy completa y absolutamente perdido. No sé por dónde empezar. No puedo usar la misma idea que en la prueba anterior, ya que no podemos describir el conjunto de $S$ de las particiones sin consecutivos, incluso las partes como un conjunto de combinaciones con elementos en algunos $A\subseteq \mathbb{N}$. Me hacen saber que $$ c_n = [x^n]\sum_{s\in S} x^{w(s)} $$ pero a partir de aquí me tienen absolutamente ninguna idea. Tengo que saber algo acerca de $S$, en un sentido, por lo que puedo manipular la generación de esta función y convertirlo en otra cosa, pero, exactamente, ¿qué pieza de información que necesita saber acerca de $S$ es más allá de mí. Tal vez un bijection de $S$ sobre sí misma, en cierto modo extraño, como $A\mapsto A\times B\backslash C$ donde $B$ $C$ son otros de los conjuntos, y luego puede derivar una ecuación funcional para la generación de esta función? Como por lo bijection yo ni siquiera podía derivar, no tengo absolutamente ninguna idea. He enumerado los elementos de $S$ $n = 0$ $7$y no puede ver los patrones.
Así que, espero que ya se ha demostrado en donde mi falta de entendimiento en la combinatoria surge; no puedo ver los pasos a seguir. No puedo ver los patrones en todo, y yo no puedo hacer las conexiones lógicas necesarias para manipular las cosas en formas útiles (tales como la generación de la función anterior).
Esto es realmente un shock para mí, pensé que habría sido al menos aceptar en la combinatoria. Nunca he tenido ninguno de estos problemas en el análisis funcional, análisis complejo, el cálculo, la teoría de números, álgebra lineal, álgebra abstracta, topología general... Así que ¿cuál es el trato con la combinatoria? ¿Por qué es tan "distantes" y esotérico, y ¿qué puedo hacer para mejorar?
