Counting problem: arranging boxes in cells w/out overlap

moshiko

New member
Joined
Sep 21, 2006
Messages
1
Hi,

I address the following counting problem.
given L empty cells. N boxes. Each box is K cells long.
N*K <= L

I want to arrange the boxes in the cells so they won't overlap.

for example: L=50, N=2, K=10:
I can arrange the first box in cells 1-10, and the second 20-29. but I can't put the second one in 10-19 because it will overlap the first one.

How many ways is there to arrange the boxes (the boxes are the same).
for now, I use Brute-force methods to solve it but it take hours for L>100.

-------------------------------------------------
After solving the first one I want to continue as follows:

suppose L=M*R (M,R are integers)/

for each way of arranging I want to calculate :
take the vector V of length L which has 1 in each occupied cell, 0 otherwise.
S is a vector length M. S(i) = sum(V(i + l*R)) 0<=l<=R-1, 1<=i<=M
then calc MS = max(S).
Note that MS is in the range (0,1,2,..,R);

after finishing I want to know how many ways to arrange resulted in each value of MS (=histogram).

Now I am using brute-force methods to calculate this for each way.
Is there any way to directly know the histogram of MS ?
 
Top