How many ways there are to arrange ten (or n) identical boxes in a row of ten (or n) places when stacking is allowed? I guess you need to find how many different arrays there are but how?

  • 1
    $\begingroup$ If you consider the height of stack $j$ as $x_j$, then you're looking at the equation $$ x_1 + x_2 + x_3 + x_4 + \ldots + x_{10} = n $$ The number of solutions can be found with the "stars and bars" method. $\endgroup$ – Matti P. Nov 15 '18 at 11:21
  • $\begingroup$ This is an example of a composition problem. $\endgroup$ – N. F. Taussig Nov 15 '18 at 17:13
  • $\begingroup$ Thanks a bunch. I was quite sure this was some classical problem but just couldn't figure it out myself $\endgroup$ – user2566933 Nov 16 '18 at 19:51

Arrange the $n$ boxes in a row, like so: $$\square\ \square\ \square\ \square\ \square\ \square\ \square\ \square\ \square\ \square\ \square\ \square\ \ldots\ \square\ \square\ \square\ \square\ \tag{1}$$ There are $n-1$ spaces in between. "Stacking" the boxes means inserting a $|$ into some of the spaces in $(1)$, indicating when a new stack shall begin. Since there are $2^{n-1}$ ways to choose a subset of the $n-1$ spaces there are $2^{n-1}$ ways to arrange the boxes in a row of nonempty stacks.


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.