0
$\begingroup$

We have $n$ distinct objects to distribute into $k$ identical boxes, how many different partitions there is where object 1 and 2 are both placed together in the same box.

I tried all sorts of things using sterling numbers of second kind to come up with an efficient formula (no more than $n + k$ operations) with no luck, is this possible?

$\endgroup$
  • $\begingroup$ Consider objects 1 and 2 to be a single object. How many ways are there to place $n-1$ objects into $k$ boxes? $\endgroup$ – jvdhooft Apr 20 '17 at 11:54
  • $\begingroup$ thanks so much! I can't believe I did not see this :) make your comment an answer if you like I'll accept it $\endgroup$ – alvin Apr 20 '17 at 11:55
0
$\begingroup$

You can consider objects 1 and 2 to be a single object, as they always have to be together. As such, the number of ways to place the $n$ distinct objects into $k$ non-empty boxes equals the Sterling number $S(n-1,k)$.

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