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.

  • 4
    $\begingroup$ 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. $\endgroup$ – Emre May 16 '16 at 14:18
  • $\begingroup$ I don't look for the final answer. I am to present an identity. That's why I need help with the binomial expression. $\endgroup$ – Meitar May 16 '16 at 14:23
  • $\begingroup$ 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. $\endgroup$ – Emre May 16 '16 at 14:26
  • $\begingroup$ 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? $\endgroup$ – Meitar May 16 '16 at 14:27
  • 1
    $\begingroup$ 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... $\endgroup$ – 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

  • $\begingroup$ 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? $\endgroup$ – Meitar May 16 '16 at 14:41
  • $\begingroup$ It appears to me that It doesn't matter actually. All channels could be what ever they are... That's the concept of Exclusion and Inclusion.. $\endgroup$ – Meitar May 16 '16 at 14:49
  • $\begingroup$ This is different from your comment. Once you choose the highest number red, everything is determined-blue above because that is the highest red and red below by induction. I don't understand this answer $\endgroup$ – Ross Millikan May 16 '16 at 15:05
  • $\begingroup$ The OP does not want the solution, s/he wants to apply inclusion/exclusion to the problem. $\endgroup$ – Emre May 16 '16 at 15:07

1 must be blue: If I = 1 then i-1 doesn't exist and therefore isn't red, so it must be blue. If i=2 then I-1 is blue so 2 is blue, and so on. All i Must be blue.


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.