0
$\begingroup$

A total of $k$ identical one-dimensional sticks of length $d$ are placed in a one-dimensional space of length $L$ (where $k\cdot d\leq L$). The values of $d$ and $L$ are integers and the sticks must be placed in such a way that their endpoints lie on points with integer coordinates.

In how many different ways can they be placed such that no two sticks overlap?

$\endgroup$
2
  • $\begingroup$ Your thoughts first please. $\endgroup$
    – Paul
    Apr 15, 2016 at 10:25
  • $\begingroup$ Well, I think it is equal to the number of different sequences ${x1,x2,...,xk}$ where $x2>=x1+d$, $x3>=x2+d$ and so on($0<=x<=L-d$). $\endgroup$ Apr 15, 2016 at 10:50

1 Answer 1

1
$\begingroup$

I'm not sure what you've tried so far, but will start off with a somewhat more general statement.

Let $L, k_1,\ldots,k_n\in\mathbb{N}$ for some $n$. Suppose we have $k_i$ sticks of length $i$ such that the combined length $S$ of all sticks is smaller than $L$. The number of ways to place the sticks on $[0,L]$ without overlap in such a way that all endpoints are integer coordinates, equals $$\frac{(L-S+k_1+\ldots+k_n)!}{(L-S)!k_1!\ldots\cdot k_n!}.$$

To show this, we basically need one observation. Namely, that the holes can be seen as a collection of identical sticks of length one. Take for instance the case where $L=6$ and we have two sticks of length $2$. In that case we need to distribute two holes of length $1$ between the sticks. If, for instance, the two sticks are placed next to each other on the left side of the interval $[0,L]$, the two holes of length $1$ are placed right next to it.

We can now encode each situation by some string, composed of integers and the letter $H$. The latter stands for a hole of length $1$. The situation above could for instance be described as $22HH$: from left to right a stick of length $2$, a stick of length $2$, a hole of length $2$. And, for instance, $12HH3H2H3$ would describe a situation where $L=15$ and where we have one stick of length $1$, two of length $2$ and three of length $3$.

What we need to do then, is count how many different of such strings there are. The number of holes of length $1$ equals $L-S$ and so the total number of characters to be distributed equals $L-S+k_1+\ldots+k_n$. If we simply take the factorial of this, there are potentially an aweful lot of combinations that are counted more than once. For instance, in the example above, the configuration $22HH$ would be counted four times. To compensate, you have to divide by the amount of permutations of all equal characters. Since there are two $H$'s in the example, you'd have to divide by $2! =2 $ to compensate for this.

Notice that questions like 'How many different permutations of the word BANANA are there?' are essentially the same.

Corollary: if $k, d, L\in\mathbb{N}$, the number of ways to correctly place the sticks equals $$\frac{(L-kd+k)!}{(L-kd)!k!}.$$

$\endgroup$
1
  • $\begingroup$ Thanks @HSN ! That really helped! :) $\endgroup$ Apr 17, 2016 at 13:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .