# partition $n$ distinct objects, $k$ identical boxes, object 1 and 2 must be in same box

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?

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

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