Return to Answer

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.

Now it is rather easy to see that (i) $\sum_{r=1}^3 a_{k,r}$ is increasing in natural $k\ge5$ and (ii) for each natural $r\ge2$, $a_{k,r}$ is increasing in natural $k\ge2r$. 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.

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.

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}

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.

Now it is rather easy to see that (i) $\sum_{r=1}^3 a_{k,r}$ is increasing in natural $k\ge5$ and (ii) for each natural $r\ge2$, $a_{k,r}$ is increasing in natural $k\ge2r$. 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.

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} 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). \end{equation}

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}