Counting permutations defined by a simple process

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.

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?

Answer 1

Let us put an additional blue ball in position $0$, to the left of the $n$ balls. The condition on the permutations of the $n$ balls is then that the marked red ball be preceded by an odd number (say $2r-1$) of red balls, which in turn must be preceded by a blue ball. Let us refer to such permutations as good. Let $p_{n,k}$ denote the number of good permutations of the $k$ red balls and $n-k$ blue ones.

Let $j$ be the position of the marked red ball in a good permutation. Then $j\ge2r$.

If $j=2r$, then $j$ is even and the only blue ball to the left of the marked red ball is the additional blue ball in position $0$. So, for any given even $j\in[n]:=\{1,\dots,n\}$, the number of good permutations with $2r=j$ is \begin{equation*} \Big(\prod_{i=0}^{j-2}(k-1-i)\Big)(n-j)!=\frac{(k-1)!(n-j)!}{(k-j)!}. \end{equation*} (If $j>k$, then the latter fraction is understood as $0$.)

Similarly counted are the good permutations with $j>2r$, where we must use one of the $n-k$ blue balls to place it immediately to the left of the $2r-1$ red balls preceding the marked red ball.

Thus, \begin{equation*} \begin{aligned} p_{n,k}&=\sum_{j\in[n]}\Big( 1(j\text{ is even})\frac{(k-1)!(n-j)!}{(k-j)!} \\ &+\sum_{1\le r<j/2}(n-k)\frac{(k-1)!(n-2r-1)!}{(k-2r)!} \Big) \\ &=(k-1)!\sum_{j\in[k]} 1(j\text{ is even})\frac{(n-j)!}{(k-j)!} \\ &+(k-1)!(n-k) \sum _{r=1}^{\lfloor k/2\rfloor } \frac{(n-2 r)!}{(k-2 r)!} \\ &=(k-1)!(n-k+1) \sum_{r=1}^{\lfloor k/2\rfloor } \frac{(n-2 r)!}{(k-2 r)!}. \end{aligned} \end{equation*}

---

This very simple expression is easy to analyze. Indeed, consider what is, according to the OP's comment, the case of interest: $n=2k-1$. Then \begin{equation*} p_{n,k}=q_k:=p_{2k-1,k}=k!\sum_{r=1}^{\lfloor k/2\rfloor } \frac{(2k-1-2 r)!}{(k-2 r)!}. \end{equation*} The OP wanted to show that \begin{equation*} P_k:=\frac{q_k}{(2k-1)!} \end{equation*} is $\le1/3$ and $P_k\to1/3$ as $k\to\infty$.

To prove this, write \begin{equation*} P_k=\sum_{r=1}^\infty a_{k,r}, \tag{1}\label{1} \end{equation*} where \begin{equation*} a_{k,r}:=\frac{k!}{(2k-1)!} \frac{(2k-1-2 r)!}{(k-2 r)!}; \end{equation*} the latter fraction is understood as $0$ if $2r>k$. We can also write \begin{equation*} a_{k,r}=\prod_{i=0}^{2r-1}\frac{k-i}{2k-1-i} =\frac{k}{2k-1}\prod_{i=1}^{2r-1}\frac{k-i}{2k-1-i} \le \frac{k}{2k-1}\frac1{2^{2r-1}}. \end{equation*} It also follows that $a_{k,r}\to\frac1{2^{2r}}$ as $k\to\infty$, for each natural $r$. So, by \eqref{1} and dominated convergence, \begin{equation*} P_k\to\sum_{r=1}^\infty \frac1{2^{2r}}=\frac13, \tag{2}\label{2} \end{equation*} as was desired.

Next, it is easy to see that, for each natural $r\ge2$, $a_{k,r}$ is increasing in natural $k\ge2r$. A little complication here is that $a_{k,1}$ is decreasing in $k$. However, it is rather easy to see that $\sum_{r=1}^3 a_{k,r}$ is increasing in natural $k\ge5$. So, by \eqref{1}, $P_k$ is increasing in natural $k\ge5$. So, by \eqref{2}, $P_k<1/3$ for $k\ge5$. It also easy to see that $P_k<1/3$ for $k\in\{1,3,4\}$ and $P_2=1/3$. Thus, $P_2=1/3$ and $P_k<1/3$ for $k\in\{1,3,4,5,6,\dots\}$, as was also desired.

Answer 2

If we view permutation as runs of red balls interspaced with runs of blue balls, then the requirement is that the marked ball is at the even position within its run.

Let $t$ be the number of red runs; $r_i$ and $b_i$ be the number of red and blue runs of length $i$, respectively.

\begin{split} & (n-k)!(k-1)!\sum_{t\geq 0} \sum_{1r_1 + 2r_2 + \dots = k\atop r_1 + \dots + r_k = t} \binom{t}{r_1,\dots,r_n} (r_2 + r_3 + 2(r_4+r_5) + \dots) \\ &\quad\times \bigg(2\sum_{1b_1 + 2b_2 + \dots = n-k\atop b_1 + \dots + b_k = t} \binom{t}{b_1,\dots,b_n} +\sum_{1b_1 + 2b_2 + \dots = n-k\atop b_1 + \dots + b_k = t-1} \binom{t-1}{b_1,\dots,b_n} +\sum_{1b_1 + 2b_2 + \dots = n-k\atop b_1 + \dots + b_k = t+1} \binom{t+1}{b_1,\dots,b_n} \bigg) \\ &=(n-k)!(k-1)!\sum_{t\geq 0} \sum_{1r_1 + 2r_2 + \dots = k\atop r_1 + \dots + r_k = t} \binom{t}{r_1,\dots,r_n} (r_2 + r_3 + 2(r_4+r_5) + \dots) \\ &\quad\times \bigg(2\binom{n-k-1}{t-1} + \binom{n-k-1}{t-2} + \binom{n-k-1}{t} \bigg) \\ &=(n-k)!(k-1)!\sum_{t\geq 0} \sum_{1r_1 + 2r_2 + \dots = k\atop r_1 + \dots + r_k = t} \binom{t}{r_1,\dots,r_n} (r_2 + r_3 + 2(r_4+r_5) + \dots)\binom{n-k+1}{t} \\ &=(n-k)!(n-k+1)!\frac1{k}\sum_{t\geq 0} \frac1{(n-k+1-t)!}\sum_{1r_1 + 2r_2 + \dots = k\atop r_1 + \dots + r_k = t} \frac{k!}{r_1!\cdots r_n!} (r_2 + r_3 + 2(r_4+r_5) + \dots) \end{split}

In terms of Bell polynomials this can be written as $$=(n-k)!(n-k+1)!\frac1{k}\frac{\partial}{\partial x}\left.\sum_{t\geq 0} \frac1{(n-k+1-t)!} B_{k}(1!,2!x,3!x,4!x^2,5!x^2,\dots)\right|_{x=1}$$ Then using the generating function for Bell polynomials we have

\begin{split} &\left.\frac{\partial}{\partial x}\sum_{t\geq 0} \frac1{(n-k+1-t)!} B_{k}(1!,2!x,3!x,4!x^2,5!x^2,\dots)\right|_{x=1} \\ &= k!\left.\frac{\partial}{\partial x} [y^{n-k+1}t^k]\ \exp(y) \exp(y (t + xt^2 + xt^3 + x^2t^4 + x^2t^5 +\dots))\right|_{x=1} \\ &= \frac{k!}{(n-k+1)!}[t^k] \left.\frac{\partial}{\partial x}(1 + t + xt^2 + xt^3 + x^2t^4 + x^2t^5 +\dots)^{n-k+1}\right|_{x=1} \\ &=\frac{k!}{(n-k)!} [t^k]\ (1+ t + t^2 + t^3 + \dots)^{n-k} (t^2 + t^3 + 2t^4 + 2t^5 + \dots) \\ & = \frac{k!}{(n-k)!} [t^k] \frac{t^2}{(1-t)^{n-k+2}(1+t)} \\ & = \frac{k!}{(n-k)!} (-1)^k \sum_{j=0}^{k-2} \binom{-(n-k+2)}{k-j-2} \\ & = \frac{k!}{(n-k)!} \sum_{j=0}^{k-2} (-1)^j \binom{n-j-1}{k-j-2}. \end{split} All in all, we get the answer: $$(n-k+1)!(k-1)! \sum_{j=0}^{k-2} (-1)^j \binom{n-j-1}{k-j-2} = (k-1)! \sum_{j=0}^{k-2} (-1)^j \frac{(n-j-1)!}{(k-j-2)!}.$$