Rainy day math problem!

December 13, 2007 12:57 PM

How many different conversations can six people have?

How many different conversations can six people have?

Assumptions:
-Topics are not important, individuals are (this is a factorial problem, not a philosophical one). Therefore any unique combination of individuals counts as a conversation.
-Conversations are bidirectional (ie. A talking with B and B talking with A is One conversation, even if neither is listening)
-No crazies (conversations must have not less than two people. However, "People" may or may not inhabit separate corporeal vessels but each single "people" may only participate once in a single conversation.)
-No ghosts
-No ventriloquists


Basically I just want someone to check my math. Thanks mefi!

posted by keasby to education (18 comments total)

A can have a conversation with the other 5 people.
B can have a conversation with the other 4 people, not including A, who we already counted.
...

5 + 4 + 3 + 2 + 1 = 15
posted by demiurge at 1:07 PM on December 13, 2007

1 X 2 X 3 X 4 X 5 = 120.

Or am I missing something?
posted by BitterOldPunk at 1:07 PM on December 13, 2007

15
posted by hermitosis at 1:08 PM on December 13, 2007

Assuming conversations are between two people and two people only, then the answer is 6 * (6 - 1) / 2, or 15.

Assuming conversations can be between any number of people greater than 2, then the answer is 6 choose 2 + 6 choose 3 + 6 choose 4 + 6 choose 5 + 6 choose 6, which is

(6! / (2! (6 - 2)!)) + (6! / (3! (6 - 3)!)) + ... + (6! / (6! (6 - 6)!)) = 57.
posted by jedicus at 1:08 PM on December 13, 2007 [2 favorites]

Oops. Sho nuff. I was missing something.
posted by BitterOldPunk at 1:08 PM on December 13, 2007

15, right? 5+4+3+2+1.
posted by mkultra at 1:08 PM on December 13, 2007

You're talking about the handshake problem.
posted by adiabat at 1:11 PM on December 13, 2007

I got 57 as well, by the same process. And thanks for the handshake link!
posted by keasby at 1:18 PM on December 13, 2007

Each person can be either in or out of a conversation.

So that's 2^6 unique conversations, or 64. There's one degenerate case with no people, and six degenerate cases with just one person. Eliminate those and you get 57 just like jedicus says.
posted by aubilenon at 1:19 PM on December 13, 2007 [4 favorites]

We're allowing n-person conversations where n is in [2..6], so we want this equation, the sum from n=2 to 6 of 6 choose n, which is 15+20+15+6+1 = 57 conversations...which lots of other people have already said by now, but oh well. I agree with them.
posted by silby at 1:21 PM on December 13, 2007 [1 favorite]

congratz, you are quite quick
posted by keasby at 1:23 PM on December 13, 2007

An even faster way
posted by keasby at 1:24 PM on December 13, 2007

Ah! I got so excited to see an application for the handshake problem that I didn't think of more than two people having a conversation.
posted by adiabat at 1:30 PM on December 13, 2007

I don't think it's as simple as the handshake problem, since conversations with more than one participant are allowed.

If I read it correctly, the problem can be phrased as:

"How many ways to partition a group of 6 distinct people into classes ("conversations") such that each class has at least two people in it?"

(The use of the word partition implies that everyone is in one and exactly one of the
classes.)

Assuming that's the right interpretation - the statement is not absolutely clear to me - well, there are some fancy combinatoric gadgets for answering questions like this, but as the numbers are so small here they would be overkill. The groupings have to be either (1) All 6 in a single conversation; (2) 4 + 2, (3) 3+3, or (4) 2+2+2.

If you want to count them using standard combinatoric tools, then, the total is

1
+ (6 Choose 4)
+ (6 Choose 3) / 2
+ (6 Choose 2) * (4 Choose 2)/6

which totals 41.

You can forcibly enumerate the possible groupings; here they are:

{{"ABCDEF"}, {"AB", "CDEF"}, {"ABC", "DEF"}, {"ADEF", "BC"}, {"AC",
"BDEF"}, {"ABCD", "EF"}, {"AEF", "BCD"}, {"ABEF", "CD"}, {"ACD",
"BEF"}, {"AD", "BCEF"}, {"ABD", "CEF"}, {"ACEF", "BD"}, {"AF",
"BCDE"}, {"ABF", "CDE"}, {"ACDE", "BF"}, {"ABCF", "DE"}, {"ADE",
"BCF"}, {"ABDE", "CF"}, {"ACF", "BDE"}, {"AE", "BCDF"}, {"ABE",
"CDF"}, {"ACDF", "BE"}, {"ABCE", "DF"}, {"ADF", "BCE"}, {"ABDF",
"CE"}, {"ACE", "BDF"}, {"AB", "CD", "EF"}, {"AB", "CF",
"DE"}, {"AB", "CE", "DF"}, {"AD", "BC", "EF"}, {"AC", "BD",
"EF"}, {"AF", "BC", "DE"}, {"AC", "BF", "DE"}, {"AE", "BC",
"DF"}, {"AC", "BE", "DF"}, {"AF", "BE", "CD"}, {"AE", "BF",
"CD"}, {"AF", "BD", "CE"}, {"AD", "BF", "CE"}, {"AE", "BD",
"CF"}, {"AD", "BE", "CF"}}
posted by Wolfdog at 1:33 PM on December 13, 2007

That was Mathematica, btw. If anyone's curious, it's a one-liner.

Map[ StringJoin, Select[SetPartitions[Characters["ABCDEF"]], Min[Length /@ #] >= 2 &], {-2}]

posted by Wolfdog at 1:39 PM on December 13, 2007 [1 favorite]

If I read it correctly, the problem can be phrased as:

"How many ways to partition a group of 6 distinct people into classes ("conversations") such that each class has at least two people in it?"

You are not reading it correctly. The correct interpretation is "How many distinct subsets of a set of six people have two or more members?" The correct answer is 57, as several others have already noted.

aubilenon's method has the advantage that it's easy to generalize: for n people, there are 2ⁿ-n-1 possible conversations.
posted by DevilsAdvocate at 2:43 PM on December 13, 2007

Are you sure about that, DA?

OP: "each single "people" may only participate once in a single conversation"

makes me think it can be interperted in 2 ways: 6 people at a party- how many conversations can there be if everyone is in a conversation? and how many different ways could 6 people be divided up in coversations
posted by Monday at 4:28 PM on December 13, 2007

That is "How many different all-conversing states can a group of six people be in?" and a very interesting question, but not what was asked for ('any unique combination of individuals counts as a conversation').
posted by eritain at 12:19 AM on December 14, 2007