I'm currently learning some basic combinatoric techniques in a class called "Intro to Combinatorics", and while all the material makes perfect sense and the steps are always clear after-the-fact, I cannot for the life of me seem to derive anything on my own.
As an example, we were learning about using bijections to show that two sets have equal cardinality. If you have a set $A$, which is difficult to count, and a set $B$ which is easy to count, and a bijection $f:A\to B$, then $\|A\| = \|B\|$. So here's an example problem on one of the assignments:
Show that the number of $k$-multisubsets of $[n]=\{1,2,\cdots, n\}$ is $$ {n+k-1\choose k} $$ where a $k$-multisubset of $[n]$ is a $k$-tuple $(a_1,\cdots, a_k)$ with $a_i\in[n]$, and $1\le a_i\le a_{i+1}\le n$.
I toiled over this for a while, but I simply couldn't find a bijection between the set of $k$-multisubsets of $[n]$ and the set of $k$-subsets of $[n+k-1]$. I listed out tons of cases, stretched my imagination to come up with any and all ideas I could, but nothing worked in general, it only worked for "that case". Then, I asked a friend, and the answer is apparently this:
$$ f(\vec a) = \vec a + (0, 1, 2,\cdots, k - 1) $$ (where the result is interpreted as a set). After the fact, it seems so obvious that this should be the result (or that the bijection should look something like this). The basic idea of this bijection is to "remove" the cases where $a_i = a_{i+1}$. I recognized that I had to remove that restriction, but I kept thinking of "bijections" $f(a)\to b$ where if $a_i = a_{i+1}$ then $b_i = b_{i+1}-1$ (working incrementally, so that if $a_i = a_{i+1} = a_{i+2}$ then $b_i = b_{i+1}-1 = b_{i+2}-2$), but this didn't work.
Here's another example of something we did in class: find the number of partitions of $n$ with parts in $A\subseteq\mathbb{N}$. The solution is to denote $S = \{\emptyset\}\cup A\cup A^2\cup A^3\cup\cdots$, and then define a weight function $w:S\to\mathbb{N}$ by $w(\alpha) = \sum_{a\in\alpha}a$ (and $w(\emptyset) = 0$). Then the number of partitions of $n$ with parts in $A$ is given by $\|\{a\in S\ |\ w(a)=n\}\|$, which is also given by $$ \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} $$ I completely understand the machinery at play here, and have no qualms with the derivation of this result. In class we even did examples such as when $A = \mathbb{N}\backslash\{3\}$, and I have no problem. However, now I'm confronted with this problem:
Determine the number $c_n$ of compositions of $n$ in which there are no consecutive pairs of even parts using generating functions.
...and I'm completely and utterly lost. I don't know where to start. I can't use the same idea as in the previous proof, since we can't describe the set $S$ of partitions with no consecutive even parts as a set of combinations with elements in some $A\subseteq \mathbb{N}$. I do know that $$ c_n = [x^n]\sum_{s\in S} x^{w(s)} $$ but from here I have absolutely no ideas. I have to know something about $S$ in a sense, so I can manipulate this generating function and turn it into something else, but exactly what piece of information I need to know about $S$ is beyond me. Maybe a bijection from $S$ onto itself in some weird way, like $A\mapsto A\times B\backslash C$ where $B$ and $C$ are other sets, and then I can derive a functional equation for this generating function? As for what bijection I even could derive, I have absolutely no idea. I've listed out the elements of $S$ for $n = 0$ to $7$ and can't see any patterns.
So, I hope I've demonstrated where my lack of understanding in combinatorics arises; I can't see the steps to take. I can't see the patterns at all, and I can't make the logical connections necessary to manipulate things in useful ways (such as the generating function above).
This is actually quite a shock to me, I thought I would've been at least ok at combinatorics. I've never had any of these problems in functional analysis, complex analysis, calculus, number theory, linear algebra, abstract algebra, general topology... So what's the deal with combinatorics? Why is it so "distant" and esoteric, and what can I do to improve?
