Need help with this combinatorics problem i made up
$begingroup$
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?
combinatorics problem-solving
edited Dec 20 '18 at 18:38
Prakhar Nagpal
752318
asked Dec 20 '18 at 18:01
user628227user628227
61
$endgroup$
add a comment |
$begingroup$
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?
combinatorics problem-solving
edited Dec 20 '18 at 18:38
Prakhar Nagpal
752318
asked Dec 20 '18 at 18:01
user628227user628227
61
$endgroup$
add a comment |
$begingroup$
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?
combinatorics problem-solving
edited Dec 20 '18 at 18:38
Prakhar Nagpal
752318
asked Dec 20 '18 at 18:01
user628227user628227
61
$endgroup$
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?
combinatorics problem-solving
combinatorics problem-solving
edited Dec 20 '18 at 18:38
Prakhar Nagpal
752318
asked Dec 20 '18 at 18:01
user628227user628227
61
edited Dec 20 '18 at 18:38
Prakhar Nagpal
752318
asked Dec 20 '18 at 18:01
user628227user628227
61
edited Dec 20 '18 at 18:38
Prakhar Nagpal
752318
edited Dec 20 '18 at 18:38
Prakhar Nagpal
752318
edited Dec 20 '18 at 18:38
Prakhar Nagpal
752318
752318
asked Dec 20 '18 at 18:01
user628227user628227
61
asked Dec 20 '18 at 18:01
user628227user628227
61
asked Dec 20 '18 at 18:01
user628227user628227
61
61
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
HINT:
A given friend is in a chat with each nonempty subset of the set of the other $7$ friends. Can you count those?
answered Dec 20 '18 at 18:06
saulspatzsaulspatz
15.9k31331
$endgroup$
add a comment |
$begingroup$
$sum_limits{i=0}^n {nchoose i} = 2^n$
$sum_limits{i=2}^8 {8choose i} = 2^8 - {8choose 1}- {8choose 0} = 256 - 8 - 1 = 247$
Low look at all the chats that do not include the one friend
$sum_limits{i=2}^7 {7choose i} = 2^7 - {7choose 1}- {7choose 0} = 128 - 7 - 1 = 120$
$247-120 = 127$ chats include the one friend.
answered Dec 20 '18 at 19:03
Doug MDoug M
45.3k31954
$endgroup$
add a comment |
$begingroup$
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 = {7choose1}=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 = {7choose2}=21$$
Similarly in group of four, you have to choose the other three guys. This can be done in
$$N_4 = {7choose23}=35$$
Calculating in a similar way all the way to the last chat where everyone is there, you can do so in
$$N_8 = {7choose7}=1$$
Summing them all up
$$N=sum_{i=1}^7{7choose i}=127$$
answered Dec 20 '18 at 18:55
Sauhard SharmaSauhard Sharma
953318
$endgroup$
$begingroup$
There are $2^7=128$ subsets, $127$ of which are nonempty.
$endgroup$
– saulspatz
Dec 20 '18 at 20:54
$begingroup$
Absolutely, I just expanded on that a bit
$endgroup$
– Sauhard Sharma
Dec 21 '18 at 3:14
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047812%2fneed-help-with-this-combinatorics-problem-i-made-up%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
HINT:
A given friend is in a chat with each nonempty subset of the set of the other $7$ friends. Can you count those?
answered Dec 20 '18 at 18:06
saulspatzsaulspatz
15.9k31331
$endgroup$
add a comment |
$begingroup$
HINT:
A given friend is in a chat with each nonempty subset of the set of the other $7$ friends. Can you count those?
answered Dec 20 '18 at 18:06
saulspatzsaulspatz
15.9k31331
$endgroup$
add a comment |
$begingroup$
HINT:
A given friend is in a chat with each nonempty subset of the set of the other $7$ friends. Can you count those?
answered Dec 20 '18 at 18:06
saulspatzsaulspatz
15.9k31331
$endgroup$
HINT:
A given friend is in a chat with each nonempty subset of the set of the other $7$ friends. Can you count those?
answered Dec 20 '18 at 18:06
saulspatzsaulspatz
15.9k31331
answered Dec 20 '18 at 18:06
saulspatzsaulspatz
15.9k31331
answered Dec 20 '18 at 18:06
saulspatzsaulspatz
15.9k31331
answered Dec 20 '18 at 18:06
saulspatzsaulspatz
15.9k31331
15.9k31331
add a comment |
add a comment |
$begingroup$
$sum_limits{i=0}^n {nchoose i} = 2^n$
$sum_limits{i=2}^8 {8choose i} = 2^8 - {8choose 1}- {8choose 0} = 256 - 8 - 1 = 247$
Low look at all the chats that do not include the one friend
$sum_limits{i=2}^7 {7choose i} = 2^7 - {7choose 1}- {7choose 0} = 128 - 7 - 1 = 120$
$247-120 = 127$ chats include the one friend.
answered Dec 20 '18 at 19:03
Doug MDoug M
45.3k31954
$endgroup$
add a comment |
$begingroup$
$sum_limits{i=0}^n {nchoose i} = 2^n$
$sum_limits{i=2}^8 {8choose i} = 2^8 - {8choose 1}- {8choose 0} = 256 - 8 - 1 = 247$
Low look at all the chats that do not include the one friend
$sum_limits{i=2}^7 {7choose i} = 2^7 - {7choose 1}- {7choose 0} = 128 - 7 - 1 = 120$
$247-120 = 127$ chats include the one friend.
answered Dec 20 '18 at 19:03
Doug MDoug M
45.3k31954
$endgroup$
add a comment |
$begingroup$
$sum_limits{i=0}^n {nchoose i} = 2^n$
$sum_limits{i=2}^8 {8choose i} = 2^8 - {8choose 1}- {8choose 0} = 256 - 8 - 1 = 247$
Low look at all the chats that do not include the one friend
$sum_limits{i=2}^7 {7choose i} = 2^7 - {7choose 1}- {7choose 0} = 128 - 7 - 1 = 120$
$247-120 = 127$ chats include the one friend.
answered Dec 20 '18 at 19:03
Doug MDoug M
45.3k31954
$endgroup$
$sum_limits{i=0}^n {nchoose i} = 2^n$
$sum_limits{i=2}^8 {8choose i} = 2^8 - {8choose 1}- {8choose 0} = 256 - 8 - 1 = 247$
Low look at all the chats that do not include the one friend
$sum_limits{i=2}^7 {7choose i} = 2^7 - {7choose 1}- {7choose 0} = 128 - 7 - 1 = 120$
$247-120 = 127$ chats include the one friend.
answered Dec 20 '18 at 19:03
Doug MDoug M
45.3k31954
answered Dec 20 '18 at 19:03
Doug MDoug M
45.3k31954
answered Dec 20 '18 at 19:03
Doug MDoug M
45.3k31954
answered Dec 20 '18 at 19:03
Doug MDoug M
45.3k31954
45.3k31954
add a comment |
add a comment |
$begingroup$
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 = {7choose1}=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 = {7choose2}=21$$
Similarly in group of four, you have to choose the other three guys. This can be done in
$$N_4 = {7choose23}=35$$
Calculating in a similar way all the way to the last chat where everyone is there, you can do so in
$$N_8 = {7choose7}=1$$
Summing them all up
$$N=sum_{i=1}^7{7choose i}=127$$
answered Dec 20 '18 at 18:55
Sauhard SharmaSauhard Sharma
953318
$endgroup$
$begingroup$
There are $2^7=128$ subsets, $127$ of which are nonempty.
$endgroup$
– saulspatz
Dec 20 '18 at 20:54
$begingroup$
Absolutely, I just expanded on that a bit
$endgroup$
– Sauhard Sharma
Dec 21 '18 at 3:14
add a comment |
$begingroup$
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 = {7choose1}=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 = {7choose2}=21$$
Similarly in group of four, you have to choose the other three guys. This can be done in
$$N_4 = {7choose23}=35$$
Calculating in a similar way all the way to the last chat where everyone is there, you can do so in
$$N_8 = {7choose7}=1$$
Summing them all up
$$N=sum_{i=1}^7{7choose i}=127$$
answered Dec 20 '18 at 18:55
Sauhard SharmaSauhard Sharma
953318
$endgroup$
$begingroup$
There are $2^7=128$ subsets, $127$ of which are nonempty.
$endgroup$
– saulspatz
Dec 20 '18 at 20:54
$begingroup$
Absolutely, I just expanded on that a bit
$endgroup$
– Sauhard Sharma
Dec 21 '18 at 3:14
add a comment |
$begingroup$
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 = {7choose1}=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 = {7choose2}=21$$
Similarly in group of four, you have to choose the other three guys. This can be done in
$$N_4 = {7choose23}=35$$
Calculating in a similar way all the way to the last chat where everyone is there, you can do so in
$$N_8 = {7choose7}=1$$
Summing them all up
$$N=sum_{i=1}^7{7choose i}=127$$
answered Dec 20 '18 at 18:55
Sauhard SharmaSauhard Sharma
953318
$endgroup$
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 = {7choose1}=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 = {7choose2}=21$$
Similarly in group of four, you have to choose the other three guys. This can be done in
$$N_4 = {7choose23}=35$$
Calculating in a similar way all the way to the last chat where everyone is there, you can do so in
$$N_8 = {7choose7}=1$$
Summing them all up
$$N=sum_{i=1}^7{7choose i}=127$$
answered Dec 20 '18 at 18:55
Sauhard SharmaSauhard Sharma
953318
answered Dec 20 '18 at 18:55
Sauhard SharmaSauhard Sharma
953318
answered Dec 20 '18 at 18:55
Sauhard SharmaSauhard Sharma
953318
answered Dec 20 '18 at 18:55
Sauhard SharmaSauhard Sharma
953318
953318
$begingroup$
There are $2^7=128$ subsets, $127$ of which are nonempty.
$endgroup$
– saulspatz
Dec 20 '18 at 20:54
$begingroup$
Absolutely, I just expanded on that a bit
$endgroup$
– Sauhard Sharma
Dec 21 '18 at 3:14
add a comment |
$begingroup$
There are $2^7=128$ subsets, $127$ of which are nonempty.
$endgroup$
– saulspatz
Dec 20 '18 at 20:54
$begingroup$
Absolutely, I just expanded on that a bit
$endgroup$
– Sauhard Sharma
Dec 21 '18 at 3:14
$begingroup$
There are $2^7=128$ subsets, $127$ of which are nonempty.
$endgroup$
– saulspatz
Dec 20 '18 at 20:54
$begingroup$
There are $2^7=128$ subsets, $127$ of which are nonempty.
$endgroup$
– saulspatz
Dec 20 '18 at 20:54
$begingroup$
Absolutely, I just expanded on that a bit
$endgroup$
– Sauhard Sharma
Dec 21 '18 at 3:14
$begingroup$
Absolutely, I just expanded on that a bit
$endgroup$
– Sauhard Sharma
Dec 21 '18 at 3:14
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047812%2fneed-help-with-this-combinatorics-problem-i-made-up%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
