Dividing $N$ into $n$ groups such that a specific pair is a member of at least one group.

Question

$N$ is a set, $\{a_1,a_2,a_3,...,a_r,x,y\}$ and has to be divided into $n$ groups, such that one of the groups has both $x$ and $y$. How do I find the number of ways to do this?

Answer 1

Hint: Think of a new set $$ \tilde{N}=\{a_1,a_2,\ldots,a_r,xy\}, $$ in which we have combined $x$ and $y$ in to a single symbol. How are divisions of $\tilde{N}$ in to $n$ groups related to division of $N$ in to $n$ groups where $x$ and $y$ are in the same part?

Answer 2

Nicholas R. Peterson answered it spot on. I'm not sure I have enough room to expand on his answer in the comments, so I'll append an answer to hopefully help you visualize better.

Consider the children: John Julie Bob Alice Eve

Alice and Bob make a deal to stay in the same group. So rather than permuting five children, we want to permute John, Julie, Eve, {Alice and Bob}. In this sense, we treat Alice and Bob as a "cluster" or group. Equivocally, how would you divide John, Julie, Eve, and Alice into subgroups, ignoring Bob? At the end, you stick Bob into Alice's group.

Does this make more sense?