There are $N$ marbles in a line, numbered $1$ through $N$ from left to right. We need to count numbers of ways to remove exactly $M$ marbles such that there are exactly $C$ remaining connected components.
A part $[a,b]$ of sequence is called a connected component if for all $a \le i \le b$ there is a marble at position $i$ and also there are no marbles at positions $a-1$ and $b+1$ (either because those marbles have been removed or because they are out of range $[1,N]$).
Example : Let $N=3$, $M=2$ and $C=1$ then answer is $3$ as we can remove any of the two pairs of marbles.
If $N=3$, $M=1$ and $C=2$ then answer is $1$ as we can remove only marble $2$.
Can there be some direct formula in $N$, $M$ and $C$ or algorithm to do this question? O(log N) or a O(1) solution is expected.
So some faster approach is expected.Please help
Let $x_0$ be the number of marbles removed at the start of the line, $y_1$ the number in the first remaining component, $x_1$ the number of marbles separating the first two components, $y_2$ the number in the next component, and so on up to $x_{C}$. Each $x_i, y_i\ge1$ except possibly $x_0$ and $x_{C}$ which need only be nonnegative. We have $$ \sum_{i=0}^C x_i=M \mathrm{\ and\ }\sum_{i=1}^C y_i = N-M.$$
Let $u_i$ and $v_i$ respectively be the amount by which $x_i$ and $y_i$ exceed the minimum allowable value. Then $u_i$ and $v_i$ are only constrained to be nonnegative, and $$ \sum_{i=0}^C u_i=M-C+1\mathrm{\ and\ }\sum_{i=1}^C v_i= N-M-C.$$
We can assign the $u_i$'s and $v_i$'s independently; by "stars and bars", the number of solutions is $$ \binom{M-C+1+C}{C} \binom{N-M-C+C-1}{C-1} = \binom{M+1}{C}\binom{N-M-1}{C-1}.$$