1

I'm looking for more detailed information about the following problem, but i'm missing a right keyword, or term for this:

Let's assume i have 10 people and they are assigned to groups:

person    group
0         A
1         A
2         A
3         B
4         B
5         B
6         C
7         C
8         D
9         D

i want to assign each person to another one, but that person must not be within the same group. How many different groupings (seen as a whole) are possible here?

I thought it would be the right way to use combinations without repetition: $$ \frac{10!}{3!\cdot 3!\cdot 2!\cdot 2!} $$ is that the right way?

What i finally want do achieve is, to create an algorithm, that checks whether a fully assignment (each person is connected to another one) is possible.

e.g.

1    A
2    A
3    A
4    B
5    C

is not possible, as the 3. A can not be assigned to another group.

but (with sample-assignment):

1    A      |    1 -> 3    
2    A      |    2 -> 4
3    B      |    3 -> 2
4    B      |    4 -> 5
5    C      |    5 -> 1

is possible.

MS1
  • 111
  • This reminds me a bit of a derangement - how many ways can you sort $n$ letters and $n$ envelopes such that no letter is in the correct envelope (the letters each initially correspond to one envelope) but instead of $1$ letter in each envelope, there are several. – Zubin Mukerjee Nov 21 '14 at 12:27
  • I'm a bit confused. Are people allowed to be assigned to more than one person? If not, then I agree with your next-to-last example that an assignment is not possible, but then I don't understand why there is an assignment in the last example? Certainly you need an even number of people to have an assignment! – Casteels Nov 21 '14 at 12:29
  • @Casteels : No, every person is only allowed to assign to one person (of a different group). It's also directed, meaning 1 -> 3 does not imply 3 -> 1 I also edited my post and put an example-assignment on the last example – MS1 Nov 21 '14 at 18:53
  • @ZubinMukerjee : Thanks a lot! Seems to be the best hint so far. Could be worth a try to modify it for groups. – MS1 Nov 21 '14 at 19:25

1 Answers1

0

Construct a graph whose vertices are the people, and where an edge connects two people if they are in different groups. The assignment is possible if and only if this graph has a perfect matching (that is, a subset of edges such that each vertex is a member of exactly one chosen edge).

Counting the number of perfect matchings (your first question) as well as finding a maximal matching (which may be perfect if there is one) are both discussed in the Wikipedia article here. Neither is easy, though finding a matching appears to have complexity of the order of $VE$ where $V$ and $E$ are the number of vertices and edges in the graph.

rogerl
  • 22,399
  • Unfortunately i think that is not the solution: As far as i understood, a perfect matching graph is only possible if the number of vertices is even. But my last example in the question shows, that it's also possible with odd number of vertices. If we use a graph here i think we need to choose a directed one. – MS1 Nov 21 '14 at 19:04
  • @MS1 I see. I didn't understand the facts as you presented them in your example. – rogerl Nov 23 '14 at 22:46