2
$\begingroup$

I know that number of ways to distribute $n$ distinct objects into $k$ distinct boxes is $k^n$, but there order of objects in a box doesn't matter.
If we want to stack objects in a box, then order also matters. I can't figure out how to solve this.
How can we calculate this ?

$\endgroup$
1
$\begingroup$

Hint: You can line up n objects in $n!$ ways. Now, consider a line up of the objects, and place dividers between them. Then, stack according to which order they appear in the line up.

$\endgroup$
  • $\begingroup$ Ok, so from stars and bars, we can place k-1 dividers in $^{n+k-1}C_{n-1}$ ways, and then multiply it by n! ? $\endgroup$ – Happy Mittal Jun 25 '14 at 6:34
1
$\begingroup$

What you want is the number of partitions of the set $N$ with cardinality $n$ into at most $k$ parts. We can use stirling coefficients of the second kind to rewrite as: $$\sum_{i=0}^k {n\brace i}$$

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