Join In the Party

Probability Level 4

How many ways are there for 5 people to be friends with each other on Facebook, such that each person is friends with at least 1 other person in the group.

Details and assumptions

Facebook friendship is mutual. If $A$ is friends with $B$ , then $B$ is friends with $A$ .

2 ways are considered distinct, if the status of friendship between 2 people changed. For example, if $A$ and $B$ are friends, and $C, D, E$ are all friends with each other, then this is a different way from if $A$ and $E$ are friends, and $B, C, D$ are all friends with each other.

The answer is 768.

2 solutions

Zakiy Firdaus Alfikri
Oct 22, 2013

Number of connection between those 5 people is $\frac{5 \times 4}{2} = 10$ . Each connection has two possibilities (friend or not friend). So, the number of ways for 5 people to be friends with each other is $2^{10} = 1024$

Now, we calculate the number of way if one person is not friends with no one. There are $2^{6}$ ways for the other 4 people to be friends with each other. Then the number of ways for 1 person not to be friends with others = $5 \times 2^{6} = 320$

Using the same calculation we get:

Number of ways for 2 person not to be friends with others = $\frac{5 \times 4}{2} \times 2^{3} = 80$

Number of ways for 3 person not to be friends with others = $\frac{5 \times 4 \times 3}{3 \times 2} \times 2^{1} = 20$

Number of ways for 4 person not to be friends with others = $\frac{5 \times 4 \times 3 \times 2}{4 \times 3 \times 2 \times 1} \times 2^{0} = 5$

Number of ways for 5 person not to be friends with others = $1 \times 2^{0} = 1$

So, the number of ways for 5 people to be friends with each other, such that each person is friends with at least 1 other person in the group = $1024 - 320 + 80 - 20 + 5 - 1 = \boxed{768}$

I got 768 by: $10C10 + 10C9 + 10C8 + 10C7 + (10C6 - 5) + (10C5 - 5 \cdot 6) + (10C4 - 5\cdot(6C4)) + ((5C2)\cdot(3C2)) = 768$

Wei Jie Tan - 7 years, 7 months ago

Hi Do you mind explaining why you need 1024 - 320 + 80 -20 +5 -1? When you are counting the number of way for 1 person not to be friends with other, isn't 320 include the number of ways for 2,3,4,5 people not to be friends with others? Because when you isolate 1 person, in the $2^6$ , isn't the 2 persons not to be friends with others included inside as well?

Siyu Ren - 7 years, 7 months ago

Gilbert Simmons
Oct 21, 2013

I have considered those possible ways out of the 2^10 in total that do NOT have every person friends with at least 1 other person in the group.

If there are only 0, 1 or 2 friendships, this is definitely the case. There are 10C0, 10C1 and 10C2 ways of this happening respectively.

If there are 3 friendships, then the cases can be counted by eliminating one of the people and then counting the ways of 3 friendships between the rest (out of the 6 possible friendships remaining), i.e. 5 x 6C3. We must note here that we will have counted friendships that are cycles of 3 twice (and there are 5C3 of them). We must subtract that number.

If there are 4 friendships it is only possible to exclude one friend, and in 5 x 6C4 ways.

If there are 5 friendships the same applies - 5 x 6C5

And with 6. 6 x 6C6.

If there are 7 or more friendships, it is impossible for the condition in the problem not to be held.

Therefore there are 2^10 - (10C0 + 10C1 + 10C2 + 5 x 6C3 - 5C3 + 5 x 6C4 + 5 x 6C5 + 5 x 6C6) = 768 ways.

Meh I used up all my solutions so I'll just post mine here.

Let $A_n$ be the answer for $n$ people. Creary $A_2=1$ . (also $A_0=A_1=1$ )

We can find $A_n$ from $A_{n-1},A_{n-2},\dots$ by complementary counting.

There are $n$ people, so there are $2^\binom{n}2$ possible ways to friend them. Now we count the number of ways such that at least one person is not friends with anyone else. We now have $n$ cases:

Case 1: 1 person is alone.

There are $\binom{n}1$ ways to choose this person. Now the problem is reduced to friending $n-1$ people such that each person is friends with at least one other person, which is just $A_{n-1}$ ways. Thus there are a total of $\binom{n}1A_{n-1}$ total ways.

Case 2: 2 people are alone.

There are $\binom{n}2$ ways to choose the people. Now the problem is reduced to friending $n-2$ people such that each person is friends with at least one other person, which is just $A_{n-2}$ ways. Thus there are a total of $\binom{n}2A_{n-2}$ total ways.

...

Case $k$ : $k$ people are alone. ( $1\le k\le n$ )

There are $\binom{n}k$ ways to choose the people. Now the problem is reduced to friending $n-k$ people such that each person is friends with at least one other person, which is just $A_{n-k}$ ways. Thus there are a total of $\binom{n}kA_{n-k}$ total ways.

...

Case $n$ : $n$ people are alone.

There is $1$ way to do this.

Thus, $A_n=2^\binom{n}2-\binom{n}1A_{n-1}-\binom{n}2A_{n-2}-\cdots-\binom{n}nA_1.$

We can easily compute $A_5$ by the above formula: $\begin{aligned} A_0&=1\\ A_1&=1\\ A_2&=1\\ A_3&=4\\ A_4&=41\\ A_5&=\boxed{768}. \end{aligned}$ $\square$

Ryan Soedjak - 7 years, 7 months ago

I did the same thing - probably should have seen PIE though.

Michael Tang - 7 years, 7 months ago

Hi! This solution is really awesome!! But may i ask is there any typo in your solution? We shouldn't have $A_{1}$ in the expression to find $A_{n}$ right? $A_{3}=2^{{3 \choose 2}} - {3 \choose 1}A_{2} - {3 \choose 2}A_{1} - {3 \choose 3}A_{0}$ = 1 not 4?

Siyu Ren - 7 years, 7 months ago

We can complete the following matrix of friendship (up to diagonal line) with 1 for 'friends' and 0 for 'no friends'. We can do this in 2^10 = 1024 ways. Now, we have to eliminate the cases when a person have 'no friends' 4* 2^6 = 256. So, we obtain * 768 * ways.

ff 1 2 3 4 5

1 - * * * *

2 * - * * *

3 * * - * *

4 * * * - *

5 * * * * -

Virgilius Teodorescu - 7 years, 7 months ago

Join In the Party

The answer is 768.

2 solutions

0 pending reports