Placing numbered balls into numbered boxes.

69 Views Asked by At

If I have $n$ balls labeled $1, 2, ..., n$ and $m$ boxes labeled the same way, how many ways can I put the balls into the boxes so that if $ball 1 \leq ball 2$ then we require $ box(ball 1) \leq box(ball 2)$

For example, ball 6 is less than ball 7, so ball 7 can never be in a box to the left of whichever box contains ball 6. They may share.

If I have balls 1,2 and boxes 1,2,3 then we could have (1,2) placed in boxes: (1,2); (1,3); (2,3), (1,1); (2,2); (3,3) for a total of six ways.

I hope I am explaining the situation well enough. The basic idea is that we have to put the ordered balls into ordered boxes so that their $\leq$ order is preserved. How could I count this?