Need help with this combinatorics problem i made up

46 Views Asked by At

We are $8$ friends and want to make group chats on a messaging app which allows you to join as many group chats as you want. Now there’s $1$ group chat with all of us $8$ in it, and then $8$ more group chats with $7$ of us in it and $1$ missing. Like this there are group chats with $2$ of us missing, and then $3$ missing and so on. Until we have $2$ of the people in a personal chat (so $28$ personal chats included in this).

Like this it turned out the total number of chats would be $247$ inclusive of the personal chats $$\sum^8 _{i=2} \binom{8}{i}$$ Now the real question is that I want to find out how many chats would $1$ of the friends see? Because they wouldn’t be included in a lot of them, so how many chats per person (including the $7$ personal chats they have)? I have tried counting them but they’re way too many and confusing, is there a neat way to find it out?

3

There are 3 best solutions below

0
On

HINT:

A given friend is in a chat with each nonempty subset of the set of the other $7$ friends. Can you count those?

2
On

As @saulspatz suggested, you assume your friend is already part of chat group and calculate the other members. Start with chats of two. So one person is already your friend and we have to choose the other guy from a possible selection of seven. This can be done in

$$N_2 = {7\choose1}=7$$

Similarly in group of three, you have to choose the other two guys (as the third guy is your friend). This can be done in

$$N_3 = {7\choose2}=21$$

Similarly in group of four, you have to choose the other three guys. This can be done in

$$N_4 = {7\choose23}=35$$

Calculating in a similar way all the way to the last chat where everyone is there, you can do so in

$$N_8 = {7\choose7}=1$$

Summing them all up

$$N=\sum_{i=1}^7{7\choose i}=127$$

0
On

$\sum_\limits{i=0}^n {n\choose i} = 2^n$

$\sum_\limits{i=2}^8 {8\choose i} = 2^8 - {8\choose 1}- {8\choose 0} = 256 - 8 - 1 = 247$

Low look at all the chats that do not include the one friend

$\sum_\limits{i=2}^7 {7\choose i} = 2^7 - {7\choose 1}- {7\choose 0} = 128 - 7 - 1 = 120$

$247-120 = 127$ chats include the one friend.