2
$\begingroup$

Say we have $n$ marbles arranged in a row. How many ways are there to take $k$ marbles out without $t$ of them in a row?

Say the answer is $s_{k,n,t}$. Then $s_{k,n,t}=s_{k,n-1,t}+s_{k,n-2,t} + \cdots + s_{k,n-t,t} $. This can be argued whether the first marble is there, and whether the second one is there, etc.

When $t=2$ the answer is $\binom{n-k+1}{k}$, which can be proved with induction and the recursive formula. Do we have a "clean" formula in general?

This sounds like a classical problem that has an answer. I haave not found it though.

$\endgroup$
3
  • $\begingroup$ Your tags indicate that you want to use Pólya's theorem here; how do you propose doing that? $\endgroup$ Commented Apr 4 at 15:26
  • $\begingroup$ I thought since the marbles line up in a line, there are some symmetry there to make use of. I do not know currently if such an approach works. $\endgroup$ Commented Apr 4 at 15:29
  • $\begingroup$ What you should be looking for with Pólya is not whether the line (or whatever) has symmetry, but whether you're trying to count objects up to symmetry; counting equivalence classes, in other words. If you're not, then it doesn't help you. $\endgroup$ Commented Apr 4 at 15:37

2 Answers 2

Reset to default
6
$\begingroup$

The solution with $t=2$ generalizes immediately to the solution with general $t$. Unfortunately, the binomial coefficient $\binom ab$ used in the $t=2$ solution generalizes to something much worse. You know, of course, that $\binom ab$ is the coefficient of $x^b$ in the expansion of $(1+x)^a$. For $t=3$, we will need to generalize it to the trinomial coefficient: the coefficient of $x^b$ in the expansion of $(1 + x + x^2)^a$. This appears in OEIS sequence A027907 but, unlike the binomial coefficient, it has no nice formula with factorials. For $t=4$, we will need the quadrinomial coefficient (A008287 in the OEIS), which is not nice either.

In general, let $C_t(a,b)$ be the coefficient of $x^b$ in $(1 + x + x^2 + \dots + x^{t-1})^a$, so that $C_2(a,b) = \binom ab$. Then the answer to the marble problem for general $t$ is $C_t(n-k+1,k)$.

$\newcommand{\bcirc}{{\boldsymbol{\bullet}}} \newcommand{\wcirc}{{\boldsymbol{\circ}}}$A generating function approach is a good way to get there. We can think of one of the solutions as a sequence of $n-k$ $\bcirc$ (marble) and $k$ $\wcirc$ (no marble) symbols, with no instance of consecutive $\underbrace{\wcirc \wcirc \cdots \wcirc}_{t}$.

Let's artificially add an extra marble to the end, for a total of $n-k+1$ $\bcirc$ symbols. This lets us divide up the sequence into blocks that have $0$ or more $\wcirc$'s (empty spaces where marbles have been taken), followed by a $\bcirc$ (marble). (Without the extra marble, we couldn't be sure that the end of the sequence forms a block.) The options for the blocks are: $$\bcirc, \quad \wcirc\bcirc, \quad \wcirc\wcirc\bcirc, \quad \dots, \quad \underbrace{\wcirc \wcirc \dots \wcirc}_{t-1}\bcirc.$$ Because there are $n-k+1$ marbles, including the artificial one, there are $n-k+1$ blocks. All the arrangements of $n-k+1$ blocks (including ones which have the wrong number of $\wcirc$'s) are given by the expansion of $$(\bcirc + \wcirc\bcirc + \wcirc\wcirc\bcirc + \dots + \underbrace{\wcirc \wcirc \dots \wcirc}_{t-1}\bcirc)^{n-k+1}$$ where we treat multiplication as concatenating blocks, and have it distribute over addition. For example, \begin{align} (\bcirc + \wcirc\bcirc + \wcirc\wcirc\bcirc)^2 &= (\bcirc + \wcirc\bcirc + \wcirc\wcirc\bcirc)(\bcirc + \wcirc\bcirc + \wcirc\wcirc\bcirc) \\ &= \bcirc(\bcirc + \wcirc\bcirc + \wcirc\wcirc\bcirc) + \wcirc\bcirc(\bcirc + \wcirc\bcirc + \wcirc\wcirc\bcirc) + \wcirc\wcirc\bcirc (\bcirc + \wcirc\bcirc + \wcirc\wcirc\bcirc) \\ &= \bcirc\bcirc + \bcirc\wcirc\bcirc + \bcirc\wcirc\wcirc\bcirc +\wcirc\bcirc\bcirc + \wcirc\bcirc\wcirc\bcirc + {}\\ &\quad+ \wcirc\bcirc\wcirc\wcirc\bcirc + \wcirc\wcirc\bcirc\bcirc + \wcirc\wcirc\bcirc\wcirc\bcirc + \wcirc\wcirc\bcirc\wcirc\wcirc\bcirc \end{align} lists all the arrangements with no more than $2$ consecutive marbles taken out, and a total of $1$ real marble remaining (and $1$ artificial marble at the end).

To turn this into a count of solutions, first allow the $\wcirc$'s and $\bcirc$'s to commute: now we have $$(\bcirc + \wcirc \bcirc + \wcirc^2 \bcirc + \dots + \wcirc^{t-1}\bcirc)^{n-k+1} = \bcirc^{n-k+1} (1 + \wcirc + \wcirc^2 + \dots + \wcirc^{t-1})^{n-k+1},$$ and in this expansion, every arrangement we want to count has simplified to $\wcirc^{k} \bcirc^{n-k+1}$. To count the solutions, we want to extract the coefficient of $\wcirc^{k} \bcirc^{n-k+1}$ from $\bcirc^{n-k+1} (1 + \wcirc + \wcirc^2 + \dots + \wcirc^{t-1})^{n-k+1}$, or equivalently the coefficient of $\wcirc^{k}$ from $(1 + \wcirc + \wcirc^2 + \dots + \wcirc^{t-1})^{n-k+1}$.

If we want real mathematicians to take us seriously, we must now replace $\wcirc$ by a real variable, and say that the answer is the coefficient of $x^k$ in $(1 + x + x^2 + \dots + x^{t-1})^{n-k+1}$.

$\endgroup$
1
$\begingroup$

This problem can be conquered by combining Stars and Bars theory with Inclusion-Exclusion, as is done in this answer. Consider the following enumeration problem:

  • $~x_1 + x_2 + \cdots + x_{k+1} = (n-k).$

  • $~x_1, ~x_2, ~\cdots, ~x_{k+1} \in \mathbb{Z_{\geq 0}}.$

  • $~x_1, ~x_2, ~\cdots, ~x_{k+1} \in \mathbb{Z_{\leq t-1}}.$

To see that this represents the problem, consider the following tableau:

- - - | - - - | - - - ... - - - | - - -

The $~k~$ selected marbles are represented by the bars in the above tableau. These bars create $~(k+1)~$ islands that each represent a group of consecutive marbles that remain. Reading these islands from left to right, and letting $~x_1, ~x_2, ~\cdots, ~x_{k+1}~$ represent the sizes of each of the islands, none of the sizes is allowed to be $~\geq t.$ Since $~k~$ marbles have been selected, the size of the islands must sum to $~(n-k).$

If you ignore the third constraint above (i.e. the upper bound constraint), then by Stars and Bars theory, the enumeration would be

$$\binom{[n-k] + [(k+1)-1]}{[k+1]-1} = \binom{n}{k}, \tag1 $$

as expected.

Let $~r~$ denote $~\displaystyle \left\lfloor ~\frac{n-k}{t} ~\right\rfloor.$ This means that for those solutions where the third constraint is ignored, no more that $~r~$ of the variables can be $~\geq t.~$

For $~j \in \{1,2,\cdots,r\},~$ let $~f(j)~$ denote the number of solutions where the variables $~x_1, x_2, \cdots, x_j~$ are in violation of the upper bound constraint, and where the other $~k+1 - j~$ variables may or may not be in violation of the upper bound constraint.

Then $~f(j)~$ equals the enumeration of the number of solutions to

  • $~x_1 + x_2 + \cdots + x_{k+1} = (n-k).$

  • $~x_1, ~x_2, ~\cdots, ~x_{k+1} \in \mathbb{Z_{\geq 0}}.$

  • $~x_1, ~x_2, ~\cdots, ~x_j \in \mathbb{Z_{\geq t}}.$

$~f(j)~$ is easily computed by setting $~y_i = x_i - t ~: ~i \in \{1,2,\cdots,j\}.~$ Then, the above enumeration is equivalent to the enumeration of

  • $~y_1 + y_2 + \cdots + y_j + x_{j+1} + x_{j+2} + x_{k+1} = (n-k) - jt.$

  • $~y_1, ~y_2, ~\cdots, ~y_{j} \in \mathbb{Z_{\geq 0}}.$

  • $~x_{j+1}, ~x_{j+2}, ~\cdots, ~x_{k+1} \in \mathbb{Z_{\geq 0}}.$

By Stars and Bars theory,

$$f(j) = \binom{[n-k-jt] + [(k+1)-1]}{[k+1]-1} = \binom{n - jt}{k}. \tag2 $$

Now, Inclusion-Exclusion theory makes the final computation routine.

Per (1) above, let

$$~T_0 ~\text{denote} ~\binom{n}{k}. \tag3 $$

Per (2) above, consider that instead of the $~j~$ variables being represented specifically by $~\{x_1,x_2,\cdots,x_j\},~$ there are $~\displaystyle \binom{k+1}{j}~$ ways that the $~j~$ variables could have been designated.

So, for $~j \in \{1,2,\cdots,r\},~$ let

$$T_j ~\text{denote} ~f(j) \times \binom{k+1}{j} = \binom{n - jt}{k} \times \binom{k+1}{j}. \tag4 $$

Then, the final computation is

$$\sum_{j=0}^r (-1)^j T_j. \tag5 $$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.