Combinatorics: Couples in Committees

[SamuelB]

So, I have a problem, and I've done it numerically, but I did a really tedious process of taking number and plugging them in and considering all the cases and I was wondering if someone could explain this in more generic terms.

Problem: How many ways can n couples be placed into k nonempty committees with no couple on the same committee? Also, n > k.

If you can explain it with numbers that would be great too, just so I can see a different method.

 

[SamuelB]

In addition

I thought that it might be important to mention that I do know Stirling numbers, and thought about using these, but couldn't.

The numbers in my equation were 6 couples and 5 committees. I solved this problem, but, as I said, it was an arduous task with the method I took. I thought about considering all the committees and using inclusion/exclusion. Is this a better method? I don't know how I would start to set those up.

As I said, I have the solution and turned in the assignment,, but I'm just looking for better methods to the work I'm doing.

 

[pka]

Problem: How many ways can n couples be placed into k nonempty committees with no couple on the same committee? Also, n > k.
If you can explain it with numbers that would be great too, just so I can see a different method.

This can be done by using the complement of inclusion/exclusion.
That is, find the number of ways at least one couple is on the same committee. Then subtract that from the total possible ways.

This is an eddied PS.
I take that along with the people the committees are distinct.
To count the number of onto functions from a set of A to a set on C is done with a summation \(\displaystyle \text{Surj}(A,B)=\sum\limits_{k = 0}^B {( - 1)^k \binom{B}{k}(B-k)^A)}\)

If there are N committees and C couples the answer to the OP is
\(\displaystyle \sum\limits_{k = 0}^C {( - 1)^k \binom{C}{k}\text{Surj}(2C-k,N)}\)

 

[SamuelB]

I take that along with the people the committees are distinct.]

The committees aren't supposed to be distinct. Also, I may have misinterpreted your previous equation, but I tried 3 couples and 2 committees and drew them out. I believe there are only 4 different ways to place the people such that no couples are in the same committee.

 

[pka]

The committees aren't supposed to be distinct. Also, I may have misinterpreted your previous equation, but I tried 3 couples and 2 committees and drew them out. I believe there are only 4 different ways to place the people such that no couples are in the same committee.

The formula I gave you is correct if the committees are distinct.
In 3 couples and 2 committees it gives 8 as the answer.
In 4 couples and 2 committees it gives 16 as the answer.

But if the committees aren't distinct then we have unordered partitions which greatly complicates the counting.
With In 4 couples and 3 committees, the committees can have from one to six members as long as the total is 8. There are a total if 5 ways to partition 8 into three sums.
Two of those are 4+3+1 & 4+2+2.
All men on one the divide the wives up 3+1 or 2+2 and we have an example of a favorable case. You can see how that gets complicated very quickly.

 

[SamuelB]

Sorry, I was responding to your previous formula, which you took down. I do agree that your new formula will solve the problem and I can actually move from the distinct committees to the non-distinct committees.

If we have the 3 couples and 2 committees and the committees aren't distinct we can solve them as distinct and divide by 2!. This could be done with any of the problems to solve them when they aren't distinct because one simply has to get rid of the arrangement of the committees.

I'm thinking now that the situation with non-distinct committees could be found using inclusion/exclusion and Stirling Numbers. Any thoughts on this?