Coloring $\{1,2,…,2n\}$ elements in red and blue, such that if $i$ is red, $i-1$ is also red.

The purpose is to find the number of ways to color $2n$ following integers in red and blue, such that if $i$ is red, so is $i-1$.

I tried to use Inclusion-Exclusion principle, but I got stuck in the calculations.

It is a little tricky.

I am trying to count the number of cases where there are $k$ bad tuples $\color{blue}{i-1}\color{red}{i}$.

I need to get ${2n-k\choose k}$ term for this calculation.

Explanations I ran into merely stated that there were $k$ places that are "taken", but it doesn't make much sense as they can't be taken until they are taken, I mean, it's more in retrospect.

How can I explain such a process? Edit: the final answer is very clear to me, but the binomial expression is what I struggle with.

• There are $2n$ ways. If $i$ is red, so is $i-1$, so is $i-2$, $\ldots$. So, you only have one choice, choosing the last red element. – Emre May 16 '16 at 14:18
• I don't look for the final answer. I am to present an identity. That's why I need help with the binomial expression. – Meitar May 16 '16 at 14:23
• Are you sure you posted the question correctly, I don't see why you use blue $i-1$ next to red $i$ where your question suggest something totally different. – Emre May 16 '16 at 14:26
• Because there is an identity I am to arrive at, which uses inclusion and exclusion. Looking at forbidden coloring, I can use the principle. How come this principle not relevant? – Meitar May 16 '16 at 14:27
• The problem as stated simply has nothing whatever to do with inclusion-exclusion! Which is why it seems likely you've stated the problem wrong... – David C. Ullrich May 16 '16 at 14:31

Try it like this you have $k$ BR blocks and $2n-2k$ unit blocks. So, you have $2n-k$ empty spots, and you want to choose $k$ spots out of these $2n-k$ to place BR blocks. B=blue,R=red
• I am a little confused when it comes to having $2n$ colored blue. It is legal and will leave me with $2n-(k+1)$ R blocks. How can I relate to that? – Meitar May 16 '16 at 14:41