0
$\begingroup$

I have a problem with blocks that are stacked on top of each other and stacks are positioned next to each other. The number of stacks w (width) and the number of blocks b are variables. The height of a stack is [0,4]. A block can only be positioned on the bottom of a stack or on top of another stack (i.e. we have to respect gravity). All blocks are unique, so vertical and horizontal ordering are important.

Here is a sample of three different layouts for (w,b) = (4,8)

     6        6            6   
     3        3            3   
 7   8        8   7        8   5 2
 5 4 1 2      1 4 5 2      1   7 4
---------    ---------    ---------

I need to calculate the number of possible layouts.

I started by calculating the number of combinations of stack heights. E.g.:

  • 4 4 0 0
  • 4 3 1 0
  • 4 2 2 0
  • 4 2 1 1
  • ...

However, I did not manage to generalize this. We are talking about permutations with variable repeatable items depending on the sum of items.

Maybe I have the wrong approach and we should only concentrate on distributing b blocks in w stacks. But how do I remove the invalid combinations that have blocks floating in the air?

Thank you for your help. :)

P.S. If you wish, you can make the height [0,h] a variable as well. Then we would have (w,h,b)

$\endgroup$
2
  • $\begingroup$ Does the order of the stacks matter? Is there a set number of stacks? $\endgroup$
    – Graham Kemp
    May 8, 2014 at 3:10
  • $\begingroup$ The order of stacks matters and the number of stacks is set for one instance of the problem. But I need to calculate this for w,b = 4,8; 4,12; 5,10; 5,15; ... $\endgroup$
    – Alan
    May 8, 2014 at 3:12

2 Answers 2

Reset to default
2
$\begingroup$

First compute the number of arrangements of block height. This is the number of weak compositions that respect your constraints:$b$ items into $w$ parts at most $h$. Without the "at most $h$" part, that is ${b+w-1 \choose w-1}$ This gives you an ordered set of stack heights, which tells you all the block positions. Now there are $b!$ ways to locate the blocks in those positions, so the total is ${b+w-1 \choose w-1}b!$ With the maximum part of $h$ you can use generating functions: take the coefficient of $x^b$ in $(1+x+x^2+\dots x^h)^w$ and multiply by $b!$

$\endgroup$
5
  • $\begingroup$ Yes. That works! $\endgroup$
    – Graham Kemp
    May 8, 2014 at 3:55
  • $\begingroup$ Tnx! I cant remember how to use generating functions, and WolframAlpha refuses to cooperate. Could you help me compute this please? $\endgroup$
    – Alan
    May 8, 2014 at 4:43
  • $\begingroup$ I know its the seriescoefficient[..., b] function but getting the right seriesdata is giving me trouble. $\endgroup$
    – Alan
    May 8, 2014 at 4:46
  • $\begingroup$ SeriesCoefficient[(Sum[x^i, {i,0,h}])^w, {x,0,b}]*(b!) $\endgroup$
    – Graham Kemp
    May 8, 2014 at 5:05
  • 1
    $\begingroup$ Use lemma 2 from here to get a closed form for "b items into w parts at most h". Then, there is no need of the generating function. $\endgroup$
    – talegari
    May 9, 2014 at 7:21
1
$\begingroup$

Does the order of the stacks matter? Is there a set number of stacks?

If there is a set number of stacks $w$ and the order of the stacks matters (and some stacks may be empty), then count the permutations of blocks and $w-1$ borders between stacks.

$b$ distinct objects in $w$ distinct stacks, where ordering in and of the stack matters, can be arranged $\frac{(b+w-1)!}{(w-1)!}$ ways.

If a maxium stack height is set it... complicates things.  I suspect we have to look into restricted partitions.

$\endgroup$
3
  • $\begingroup$ How does this respect height? edit: I see your edit. $\endgroup$
    – Alan
    May 8, 2014 at 3:18
  • $\begingroup$ I suspect we have to look into restricted partitions. en.wikipedia.org/wiki/… $\endgroup$
    – Graham Kemp
    May 8, 2014 at 3:44
  • $\begingroup$ you were on a good path, i would vote up your answer but i don't have enough karma $\endgroup$
    – Alan
    May 8, 2014 at 5:04

You must log in to answer this question.

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