Return to Answer

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}. \end{split} All in all, we get the answer: $$(n-k+1)!(k-1)! (-1)^k \sum_{j=0}^{k-2} \binom{-(n-k+2)}{k-j-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)!}.$$

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} \end{split} and the rest is trivial.

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}. \end{split} All in all, we get the answer: $$(n-k+1)!(k-1)! (-1)^k \sum_{j=0}^{k-2} \binom{-(n-k+2)}{k-j-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.

$$(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)$$ $$\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)$$ $$\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)$$

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} \\ &= \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} \\ &= [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} \\ &=[t^k]\ (n-k+1) (1+ t + t^2 + t^3 + \dots)^{n-k} (t^2 + t^3 + 2t^4 + 2t^5 + \dots) \\ & = (n-k+1) [t^k] \frac{t^2}{(1-t)^{n-k+2}(1+t)} \\ & = (n-k+1) (-1)^k \sum_{j=0}^{k-2} \binom{-(n-k+2)}{k-j-2} \end{split} and the rest is trivial.

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} \end{split} and the rest is trivial.