1
$\begingroup$

I am wondering if the following problem has already been approached.

Given a unit length $l$, a segment of length $L$, integer, is also given (call it the master segment), as well as $m$ segments of lengths $m_i$, $i$ running from $1$ to $m$ and all the $m_i$ integer too. The length of all m segments is less than the master segment

The latter segments can be placed on the segment long $N$ only in such a way that the unit length long interval overlap (in other words, each segment can start and finish only at integer values of length of the master segment).

How many ways are there to place all the $m$ segments?

$\endgroup$
  • 1
    $\begingroup$ Can you add some information about the $m$ segments - specifically, how does their total length compare to the length of the master segment? $\endgroup$ – Joffan Mar 8 '15 at 15:31
  • $\begingroup$ Joffan, their total lenght is less than the length of the master segment. Thanks for your help. $\endgroup$ – Bundjev Mar 8 '15 at 17:13
1
$\begingroup$

The order of the $m$ segments can be chosen in $m!$ ways, assuming the segments are distinguishable.

For each such choice, we then have to allocate the spare space: define $s = L - \sum {m_i}$. This can be allocated using a "stars & bars"-type calculation, choosing which are the spaces from a string of $(s+m)$ items, ${s+m \choose s}$.

Total number of choices over these two steps then is $$m!{s+m \choose s}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.