9
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Combinatorics is the hardest. I hardly ever know what to do either $\endgroup$
    – leibnewtz
    Oct 1, 2017 at 0:09

1 Answer 1

3
$\begingroup$

I will answer the "how to improve" portion of your question.
Basic combinatorics is pretty easy, as it just revolves around a few principles. However, for your type of questions, I have no idea how to solve as well. It seems that you are a self-learner, which I am too, so I would recommend buying a few books on advanced combinatorics and then solving a couple of questions if you can. When you get stuck, "sit" on the questions for hours, even days. If you still don't get a complete answer, make clear to yourself how you got stuck, and then maybe you will find a breakthrough. Otherwise, admit defeat. It is not shameful if you have tried. Look at the answers and make sure you understand completely the PROCESS at which one gets the answer, not just the answer itself. After a few days or weeks, come back to the question and do it again. If you are able to do it, make sure you did not get the correct answer out of a mistake (it is possible). If you are still not able to solve it, "sit" on it again, and admit defeat if necessary. Keep on trying this, as eventually, you will understand and master the solution process. It also takes experience to solve these questions, and through these means, you will become experienced.
Learn on.
This link may also help: How to improve mathematical creativity?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.