Return to Question

Consider $n$ labeled balls, $k$ of which are red and $(n-k)$ blue. Given a permutation of these balls, we tick $n-1$ times. For the $i$-th tick, if the $i$-th ball in the permutation is red, then it paints the $(i+1)$-th ball in the permutation blue (if the latter is already blue, then it remains blue). We secretly mark one of the red balls at the beginning. How many permutations are there in which our marked ball becomes blue by the end of the process?

I want to prove that the answer is

$$ \sum_{j=0}^{k-2}(-1)^j\frac{n!2^{k-2-j}{{k-1}\choose{j}}(k-1-j)}{n-j}. $$

To show this, I was trying to use the inclusion-exclusion principle without success. How could we derive this formula?

ps.: There are other (maybe nicer) formulas that would work, but I am particularly interested in the one given above.

Consider $n$ labeled balls, $k$ of which are red and $(n-k)$ blue. Given a permutation of these balls, we tick $n-1$ times. For the $i$-th tick, if the $i$-th ball in the permutation is red, then it paints the $(i+1)$-th ball in the permutation blue (if the latter is already blue, then it remains blue). We secretly mark one of the red balls at the beginning. How many permutations are there in which our marked ball becomes blue by the end of the process?

I want to prove that the answer is

$$ \sum_{j=0}^{k-2}(-1)^j\frac{n!2^{k-2-j}{{k-1}\choose{j}}(k-1-j)}{n-j}. $$

To show this, I was trying to use the inclusion-exclusion principle without success. How could we derive this formula?

ps.: There are other (maybe nicer) formulas that would work, but I am particularly interested in the one given above.

Edit: Thank you for all the great answers so far! My main question, however, remains open: how to prove that the formula I proposed is correct?

Consider $n$ balls, $k$ of which are red and $(n-k)$ blue. Given a permutation of these balls, we tick $n-1$ times. For the $i$-th tick, if the $i$-th ball in the permutation is red, then it paints the $(i+1)$-th ball in the permutation blue (if the latter is already blue, then it remains blue). We secretly mark one of the red balls at the beginning. How many permutations are there in which our marked ball becomes blue by the end of the process?

I want to prove that the answer is

$$ \sum_{j=0}^{k-2}(-1)^j\frac{n!2^{k-2-j}{{k-1}\choose{j}}(k-1-j)}{n-j}. $$

To show this, I was trying to use the inclusion-exclusion principle without success. How could we derive this formula?

ps.: There are other (maybe nicer) formulas that would work, but I am particularly interested in the one given above.

Consider $n$ labeled balls, $k$ of which are red and $(n-k)$ blue. Given a permutation of these balls, we tick $n-1$ times. For the $i$-th tick, if the $i$-th ball in the permutation is red, then it paints the $(i+1)$-th ball in the permutation blue (if the latter is already blue, then it remains blue). We secretly mark one of the red balls at the beginning. How many permutations are there in which our marked ball becomes blue by the end of the process?

I want to prove that the answer is

$$ \sum_{j=0}^{k-2}(-1)^j\frac{n!2^{k-2-j}{{k-1}\choose{j}}(k-1-j)}{n-j}. $$

To show this, I was trying to use the inclusion-exclusion principle without success. How could we derive this formula?

ps.: There are other (maybe nicer) formulas that would work, but I am particularly interested in the one given above.

Consider $n$ balls, $k$ of which are red and $(n-k)$ blue. Given a permutation of these balls, we tick $n$ times. For the $i$-th tick, if the $i$-th ball is red, then it paints the $(i+1)$-th ball blue (if the latter is already blue, then it remains blue). We secretly mark one of the red balls at the beginning. How many permutations are there in which our marked ball becomes blue by the end of the process?

I want to prove that the answer is

$$ \sum_{j=0}^{k-2}(-1)^j\frac{n!2^{k-2-j}{{k-1}\choose{j}}(k-1-j)}{n-j}. $$

To show this, I was trying to use the inclusion-exclusion principle without success. How could we derive this formula?

ps.: There are other (maybe nicer) formulas that would work, but I am particularly interested in the one given above.

Consider $n$ balls, $k$ of which are red and $(n-k)$ blue. Given a permutation of these balls, we tick $n-1$ times. For the $i$-th tick, if the $i$-th ball in the permutation is red, then it paints the $(i+1)$-th ball in the permutation blue (if the latter is already blue, then it remains blue). We secretly mark one of the red balls at the beginning. How many permutations are there in which our marked ball becomes blue by the end of the process?

I want to prove that the answer is

$$ \sum_{j=0}^{k-2}(-1)^j\frac{n!2^{k-2-j}{{k-1}\choose{j}}(k-1-j)}{n-j}. $$

To show this, I was trying to use the inclusion-exclusion principle without success. How could we derive this formula?

ps.: There are other (maybe nicer) formulas that would work, but I am particularly interested in the one given above.