0
$\begingroup$

$n$ different balls, $k$ different cells. In how many ways I can put the balls in the cells while the order in each cell is important?

Proposed solution: $k^n$.

My question - In the above formula, where is the internal order in each cell is calculated?

For example, if I arrange balls: $\{B_1,B_2,B_3\}$ in bins $\{C_1,C_2,C_3,C_4\}$ from the first ball $B_1$ to the last $B_3$, then there will be never any event which contain a cell where $B_1$ is not the first one inside the internal order.

Is this makes any sense? Or I don't understand the definition of internal order inside a cell?

$\endgroup$
  • 1
    $\begingroup$ Take for example our balls be labeled $1,2,3$ and our bins colored $\color{red}{\text{red}}$ and $\color{blue}{\text{blue}}$. Among the possible arrangements would include $\{(\color{red}{1,2}),(\color{blue}{3})\}$ as well as $\{(\color{red}{2,1}),(\color{blue}{3})\}$. These arrangements are considered different since the order in which $1$ and $2$ appear are different despite both ball $1$ and ball $2$ going into the red bin. $\endgroup$ – JMoravitz Jul 8 '18 at 23:24
  • 1
    $\begingroup$ The answer of $k^n$ is incorrect. You should be able to convince yourself of this by looking at $k=1$ which should have $n!$ as answer. As for a hint on how to proceed... one approach would be to use something similar to stars and bars but with a slight twist. Here, our stars will each be distinctly labeled in order to represent the different balls. The bars will serve as barriers between one bin and another. For the example of three balls and two bins., arrange $123|$ and for five balls and five bins, arrange $12345||||$ $\endgroup$ – JMoravitz Jul 8 '18 at 23:26
  • $\begingroup$ Thank you! I got it! Thanks again for all the help tonight! $\endgroup$ – Stav Alfi Jul 8 '18 at 23:43
1
$\begingroup$

With the help of JMoravitz, the currect answer is (using stars and bars, and then multiply the answer by the amopunt of starts permutations):

$$ \binom{n+k-1}{n}n! = \frac{(n+k-1)!}{(k-1)!} $$

$\endgroup$
0
$\begingroup$

As shown above, the solution is the rising factorial $k^{(n)}$

Let's say we have $n$ books and $(k-1)$ separators, such that we will form $k$ shelves (some of them could be empty).

There are $(n+k-1)!$ possible orders of the $(n+k-1)$ items. But the order of the $(k-1)$ separators does not matter, hence the answer :

$k^{(n)} = k.(k+1).(k+2)\dots (n+k-1) = \frac{(n+k-1)!}{(k-1)!}$

$\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.