Mixing
Number of ways for getting sum equal to s using inclusion-exclusion
$begingroup$
I am trying very hard to understand following inclusion-exclusion problem but can't get it. It will be very helpful if someone can provide detail explanation.
f(s) is number of ways of having sum of elements equal to s in set T
g(i,j) is number of ways to get sum upto i using j distinct numbers
from 1 to N.
Can anyone explain how
$f(n) = sum_{i ge 1} (-1)^i*g(n,i)$
This problem is actually from competitive programming if someone wants to refer to full resource and it's solution is also there.
combinatorics inclusion-exclusion dynamic-programming
asked Jan 21 at 19:34
Parth PatelParth Patel
347
$endgroup$
add a comment |
$begingroup$
I am trying very hard to understand following inclusion-exclusion problem but can't get it. It will be very helpful if someone can provide detail explanation.
f(s) is number of ways of having sum of elements equal to s in set T
g(i,j) is number of ways to get sum upto i using j distinct numbers
from 1 to N.
Can anyone explain how
$f(n) = sum_{i ge 1} (-1)^i*g(n,i)$
This problem is actually from competitive programming if someone wants to refer to full resource and it's solution is also there.
combinatorics inclusion-exclusion dynamic-programming
asked Jan 21 at 19:34
Parth PatelParth Patel
347
$endgroup$
$begingroup$
I explained the solution, but I could not answer your question directly because what your interpretation of $f(n)$ is not correct. $s(n)$ in their solution is not actually counting anything.
$endgroup$
– Mike Earnest
Jan 23 at 19:38
add a comment |
$begingroup$
I am trying very hard to understand following inclusion-exclusion problem but can't get it. It will be very helpful if someone can provide detail explanation.
f(s) is number of ways of having sum of elements equal to s in set T
g(i,j) is number of ways to get sum upto i using j distinct numbers
from 1 to N.
Can anyone explain how
$f(n) = sum_{i ge 1} (-1)^i*g(n,i)$
This problem is actually from competitive programming if someone wants to refer to full resource and it's solution is also there.
combinatorics inclusion-exclusion dynamic-programming
asked Jan 21 at 19:34
Parth PatelParth Patel
347
$endgroup$
I am trying very hard to understand following inclusion-exclusion problem but can't get it. It will be very helpful if someone can provide detail explanation.
f(s) is number of ways of having sum of elements equal to s in set T
g(i,j) is number of ways to get sum upto i using j distinct numbers
from 1 to N.
Can anyone explain how
$f(n) = sum_{i ge 1} (-1)^i*g(n,i)$
This problem is actually from competitive programming if someone wants to refer to full resource and it's solution is also there.
combinatorics inclusion-exclusion dynamic-programming
combinatorics inclusion-exclusion dynamic-programming
asked Jan 21 at 19:34
Parth PatelParth Patel
347
asked Jan 21 at 19:34
Parth PatelParth Patel
347
asked Jan 21 at 19:34
Parth PatelParth Patel
347
asked Jan 21 at 19:34
Parth PatelParth Patel
347
asked Jan 21 at 19:34
Parth PatelParth Patel
347
347
$begingroup$
I explained the solution, but I could not answer your question directly because what your interpretation of $f(n)$ is not correct. $s(n)$ in their solution is not actually counting anything.
$endgroup$
– Mike Earnest
Jan 23 at 19:38
add a comment |
$begingroup$
I explained the solution, but I could not answer your question directly because what your interpretation of $f(n)$ is not correct. $s(n)$ in their solution is not actually counting anything.
$endgroup$
– Mike Earnest
Jan 23 at 19:38
$begingroup$
I explained the solution, but I could not answer your question directly because what your interpretation of $f(n)$ is not correct. $s(n)$ in their solution is not actually counting anything.
$endgroup$
– Mike Earnest
Jan 23 at 19:38
$begingroup$
I explained the solution, but I could not answer your question directly because what your interpretation of $f(n)$ is not correct. $s(n)$ in their solution is not actually counting anything.
$endgroup$
– Mike Earnest
Jan 23 at 19:38
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You are trying to count the number of solutions to
$$
x_1+x_2+dots+x_{n} = k
$$
which satisfy $0le x_ale a-1$ for all $1le a le n$.
If we replaced this with the weaker condition $0le x_a$, the answer would be $binom{k+n-1}k$. Here is where inclusion-exclusion comes into play; you take all $binom{k+n-1}k$ solutions, subtract the "bad" solutions where one of the variables satisfies $x_age a$, then add back in the doubly subtracted solutions where two of the variables are too big, etc.
Suppose we want to count solutions where $x_age a$ for all $ain S$. That is, all of the variables in $S$ (and possibly others) are too big. Subtracting $a$ from each of the bad variables, this is the same as solving
$$
x_0+x_1+dots+x_{n-1}=k-Big(sum_{iin S}iBig)
$$
Letting $i$ be the sum in question, the number of solutions is $binom{k-i+n-1}{k-i}$. Furthermore, if this subset has size $i$, then it its sign in the inclusion exclusion sum will be $(-1)^i$.
When performing the inclusion-exclusion, we must sum over all subsets $S$. However, we can group together all of the subsets $S$ which have the same sum and size, as this is all that is needed to compute their contribution. This is where the $f(i,j)$ comes into play; it is the number of subsets with sum $i$ and size $j$. Therefore, the final answer is
$$
sum_{i=0}^k binom{n-1+(k-i)}{(k-i)}sum_{jge 0}(-1)^j f(i,j)
$$
answered Jan 23 at 19:36
Mike EarnestMike Earnest
24.3k22151
$endgroup$
$begingroup$
Thanks for the answer. I can't upvote it due to my bad reputation. Sorry for that.
$endgroup$
– Parth Patel
Jan 24 at 16:06
$begingroup$
@ParthPatel You’re welcome!
$endgroup$
– Mike Earnest
Jan 24 at 18:22
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%2f3082301%2fnumber-of-ways-for-getting-sum-equal-to-s-using-inclusion-exclusion%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You are trying to count the number of solutions to
$$
x_1+x_2+dots+x_{n} = k
$$
which satisfy $0le x_ale a-1$ for all $1le a le n$.
If we replaced this with the weaker condition $0le x_a$, the answer would be $binom{k+n-1}k$. Here is where inclusion-exclusion comes into play; you take all $binom{k+n-1}k$ solutions, subtract the "bad" solutions where one of the variables satisfies $x_age a$, then add back in the doubly subtracted solutions where two of the variables are too big, etc.
Suppose we want to count solutions where $x_age a$ for all $ain S$. That is, all of the variables in $S$ (and possibly others) are too big. Subtracting $a$ from each of the bad variables, this is the same as solving
$$
x_0+x_1+dots+x_{n-1}=k-Big(sum_{iin S}iBig)
$$
Letting $i$ be the sum in question, the number of solutions is $binom{k-i+n-1}{k-i}$. Furthermore, if this subset has size $i$, then it its sign in the inclusion exclusion sum will be $(-1)^i$.
When performing the inclusion-exclusion, we must sum over all subsets $S$. However, we can group together all of the subsets $S$ which have the same sum and size, as this is all that is needed to compute their contribution. This is where the $f(i,j)$ comes into play; it is the number of subsets with sum $i$ and size $j$. Therefore, the final answer is
$$
sum_{i=0}^k binom{n-1+(k-i)}{(k-i)}sum_{jge 0}(-1)^j f(i,j)
$$
answered Jan 23 at 19:36
Mike EarnestMike Earnest
24.3k22151
$endgroup$
$begingroup$
Thanks for the answer. I can't upvote it due to my bad reputation. Sorry for that.
$endgroup$
– Parth Patel
Jan 24 at 16:06
$begingroup$
@ParthPatel You’re welcome!
$endgroup$
– Mike Earnest
Jan 24 at 18:22
add a comment |
$begingroup$
You are trying to count the number of solutions to
$$
x_1+x_2+dots+x_{n} = k
$$
which satisfy $0le x_ale a-1$ for all $1le a le n$.
If we replaced this with the weaker condition $0le x_a$, the answer would be $binom{k+n-1}k$. Here is where inclusion-exclusion comes into play; you take all $binom{k+n-1}k$ solutions, subtract the "bad" solutions where one of the variables satisfies $x_age a$, then add back in the doubly subtracted solutions where two of the variables are too big, etc.
Suppose we want to count solutions where $x_age a$ for all $ain S$. That is, all of the variables in $S$ (and possibly others) are too big. Subtracting $a$ from each of the bad variables, this is the same as solving
$$
x_0+x_1+dots+x_{n-1}=k-Big(sum_{iin S}iBig)
$$
Letting $i$ be the sum in question, the number of solutions is $binom{k-i+n-1}{k-i}$. Furthermore, if this subset has size $i$, then it its sign in the inclusion exclusion sum will be $(-1)^i$.
When performing the inclusion-exclusion, we must sum over all subsets $S$. However, we can group together all of the subsets $S$ which have the same sum and size, as this is all that is needed to compute their contribution. This is where the $f(i,j)$ comes into play; it is the number of subsets with sum $i$ and size $j$. Therefore, the final answer is
$$
sum_{i=0}^k binom{n-1+(k-i)}{(k-i)}sum_{jge 0}(-1)^j f(i,j)
$$
answered Jan 23 at 19:36
Mike EarnestMike Earnest
24.3k22151
$endgroup$
$begingroup$
Thanks for the answer. I can't upvote it due to my bad reputation. Sorry for that.
$endgroup$
– Parth Patel
Jan 24 at 16:06
$begingroup$
@ParthPatel You’re welcome!
$endgroup$
– Mike Earnest
Jan 24 at 18:22
add a comment |
$begingroup$
You are trying to count the number of solutions to
$$
x_1+x_2+dots+x_{n} = k
$$
which satisfy $0le x_ale a-1$ for all $1le a le n$.
If we replaced this with the weaker condition $0le x_a$, the answer would be $binom{k+n-1}k$. Here is where inclusion-exclusion comes into play; you take all $binom{k+n-1}k$ solutions, subtract the "bad" solutions where one of the variables satisfies $x_age a$, then add back in the doubly subtracted solutions where two of the variables are too big, etc.
Suppose we want to count solutions where $x_age a$ for all $ain S$. That is, all of the variables in $S$ (and possibly others) are too big. Subtracting $a$ from each of the bad variables, this is the same as solving
$$
x_0+x_1+dots+x_{n-1}=k-Big(sum_{iin S}iBig)
$$
Letting $i$ be the sum in question, the number of solutions is $binom{k-i+n-1}{k-i}$. Furthermore, if this subset has size $i$, then it its sign in the inclusion exclusion sum will be $(-1)^i$.
When performing the inclusion-exclusion, we must sum over all subsets $S$. However, we can group together all of the subsets $S$ which have the same sum and size, as this is all that is needed to compute their contribution. This is where the $f(i,j)$ comes into play; it is the number of subsets with sum $i$ and size $j$. Therefore, the final answer is
$$
sum_{i=0}^k binom{n-1+(k-i)}{(k-i)}sum_{jge 0}(-1)^j f(i,j)
$$
answered Jan 23 at 19:36
Mike EarnestMike Earnest
24.3k22151
$endgroup$
You are trying to count the number of solutions to
$$
x_1+x_2+dots+x_{n} = k
$$
which satisfy $0le x_ale a-1$ for all $1le a le n$.
If we replaced this with the weaker condition $0le x_a$, the answer would be $binom{k+n-1}k$. Here is where inclusion-exclusion comes into play; you take all $binom{k+n-1}k$ solutions, subtract the "bad" solutions where one of the variables satisfies $x_age a$, then add back in the doubly subtracted solutions where two of the variables are too big, etc.
Suppose we want to count solutions where $x_age a$ for all $ain S$. That is, all of the variables in $S$ (and possibly others) are too big. Subtracting $a$ from each of the bad variables, this is the same as solving
$$
x_0+x_1+dots+x_{n-1}=k-Big(sum_{iin S}iBig)
$$
Letting $i$ be the sum in question, the number of solutions is $binom{k-i+n-1}{k-i}$. Furthermore, if this subset has size $i$, then it its sign in the inclusion exclusion sum will be $(-1)^i$.
When performing the inclusion-exclusion, we must sum over all subsets $S$. However, we can group together all of the subsets $S$ which have the same sum and size, as this is all that is needed to compute their contribution. This is where the $f(i,j)$ comes into play; it is the number of subsets with sum $i$ and size $j$. Therefore, the final answer is
$$
sum_{i=0}^k binom{n-1+(k-i)}{(k-i)}sum_{jge 0}(-1)^j f(i,j)
$$
answered Jan 23 at 19:36
Mike EarnestMike Earnest
24.3k22151
answered Jan 23 at 19:36
Mike EarnestMike Earnest
24.3k22151
answered Jan 23 at 19:36
Mike EarnestMike Earnest
24.3k22151
answered Jan 23 at 19:36
Mike EarnestMike Earnest
24.3k22151
24.3k22151
$begingroup$
Thanks for the answer. I can't upvote it due to my bad reputation. Sorry for that.
$endgroup$
– Parth Patel
Jan 24 at 16:06
$begingroup$
@ParthPatel You’re welcome!
$endgroup$
– Mike Earnest
Jan 24 at 18:22
add a comment |
$begingroup$
Thanks for the answer. I can't upvote it due to my bad reputation. Sorry for that.
$endgroup$
– Parth Patel
Jan 24 at 16:06
$begingroup$
@ParthPatel You’re welcome!
$endgroup$
– Mike Earnest
Jan 24 at 18:22
$begingroup$
Thanks for the answer. I can't upvote it due to my bad reputation. Sorry for that.
$endgroup$
– Parth Patel
Jan 24 at 16:06
$begingroup$
Thanks for the answer. I can't upvote it due to my bad reputation. Sorry for that.
$endgroup$
– Parth Patel
Jan 24 at 16:06
$begingroup$
@ParthPatel You’re welcome!
$endgroup$
– Mike Earnest
Jan 24 at 18:22
$begingroup$
@ParthPatel You’re welcome!
$endgroup$
– Mike Earnest
Jan 24 at 18:22
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%2f3082301%2fnumber-of-ways-for-getting-sum-equal-to-s-using-inclusion-exclusion%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
$begingroup$
I explained the solution, but I could not answer your question directly because what your interpretation of $f(n)$ is not correct. $s(n)$ in their solution is not actually counting anything.
$endgroup$
– Mike Earnest
Jan 23 at 19:38