Mixing
Product-of-combinations and Combination-of-sums
$begingroup$
Conjecture:
$prod _{i=1}^N binom{n_i}{r_i} < binom{sum_{i=1}^N n_i}{sum_{i=1}^N r_i}$,
where $r_i,n_i$ are positive integers such that $forall i, r_i leq n_i$; and $exists i, r_i < n_i $.
Is it true? If yes, is there any theorem and proof on it?
I have performed lots of experiments with random integers to generate the LHS and RHS and the result that no counterexamples have yet been found tend to support the conjecture.
combinatorics
asked Jan 29 at 8:24
AmateurAmateur
164
$endgroup$
add a comment |
$begingroup$
Conjecture:
$prod _{i=1}^N binom{n_i}{r_i} < binom{sum_{i=1}^N n_i}{sum_{i=1}^N r_i}$,
where $r_i,n_i$ are positive integers such that $forall i, r_i leq n_i$; and $exists i, r_i < n_i $.
Is it true? If yes, is there any theorem and proof on it?
I have performed lots of experiments with random integers to generate the LHS and RHS and the result that no counterexamples have yet been found tend to support the conjecture.
combinatorics
asked Jan 29 at 8:24
AmateurAmateur
164
$endgroup$
add a comment |
$begingroup$
Conjecture:
$prod _{i=1}^N binom{n_i}{r_i} < binom{sum_{i=1}^N n_i}{sum_{i=1}^N r_i}$,
where $r_i,n_i$ are positive integers such that $forall i, r_i leq n_i$; and $exists i, r_i < n_i $.
Is it true? If yes, is there any theorem and proof on it?
I have performed lots of experiments with random integers to generate the LHS and RHS and the result that no counterexamples have yet been found tend to support the conjecture.
combinatorics
asked Jan 29 at 8:24
AmateurAmateur
164
$endgroup$
Conjecture:
$prod _{i=1}^N binom{n_i}{r_i} < binom{sum_{i=1}^N n_i}{sum_{i=1}^N r_i}$,
where $r_i,n_i$ are positive integers such that $forall i, r_i leq n_i$; and $exists i, r_i < n_i $.
Is it true? If yes, is there any theorem and proof on it?
I have performed lots of experiments with random integers to generate the LHS and RHS and the result that no counterexamples have yet been found tend to support the conjecture.
combinatorics
combinatorics
asked Jan 29 at 8:24
AmateurAmateur
164
asked Jan 29 at 8:24
AmateurAmateur
164
asked Jan 29 at 8:24
AmateurAmateur
164
asked Jan 29 at 8:24
AmateurAmateur
164
asked Jan 29 at 8:24
AmateurAmateur
164
164
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
It is true indeed. Let's try to interpret the LHS and the RHS combinatorially.
LHS: You have N sets. Set $i$ has $n_i$ objects. You want to choose $r_i$ objects from the $i$th set. The LHS answers many ways can you do that.
RHS: Now imagine you grouped all the sets together. Now you have one set of $sum n_i$ objects that you want to select $sum r_i$ objects from.
Clearly, any selection while the objects are grouped into $N$ sets works as a selection when they're grouped together. The opposite is not true. When you group them together, you can select more than $r_i$ items from set $i$, and less from some other set to compensate. So LHS < RHS.
answered Jan 29 at 8:32
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
Thinking combinatorially is really powerful! My takeaway is that I should interpret objects combinatorially in the first place, instead of writing out the formulae explicitly as what I tried.
$endgroup$
– Amateur
Jan 29 at 16:11
add a comment |
$begingroup$
Assuming $0le k_jle n_j$ for all $1le jle m$,
$$
begin{align}
binom{n_1+n_2}{k_1+k_2}
&=sum_{j=0}^{k_1+k_2}binom{n_1}{j}binom{n_2}{k_1+k_2-j}tag1\
&gebinom{n_1}{k_1}binom{n_2}{k_2}tag2
end{align}
$$
Explanation:
$(1)$: Vandermonde Identity
$(2)$: one term ($j=k_1$) in a sum of non-negative numbers is no greater than the entire sum
Note that if $0lt k_1+k_2lt n_1+n_2$, there are at least two positive terms in $(1)$, so the inequality is strict.
Induction and $(2)$ show that
$$
binom{sum_{j=1}^mn_j}{sum_{j=1}^mk_j}geprod_{j=1}^mbinom{n_j}{k_j}tag3
$$
and if $0ltsum_{j=1}^mk_jltsum_{j=1}^mn_j$, the inequality in $(3)$ is strict.
answered Jan 30 at 7:59
robjohn♦robjohn
270k27312640
$endgroup$
$begingroup$
This proof using Vandermonde's identity is beautiful. Furthermore, Step (2) also makes it clear to me why the RHS (in my question) is far greater than the LHS in a bunch of experiments.
$endgroup$
– Amateur
Jan 31 at 20:07
add a comment |
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%2f3091914%2fproduct-of-combinations-and-combination-of-sums%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It is true indeed. Let's try to interpret the LHS and the RHS combinatorially.
LHS: You have N sets. Set $i$ has $n_i$ objects. You want to choose $r_i$ objects from the $i$th set. The LHS answers many ways can you do that.
RHS: Now imagine you grouped all the sets together. Now you have one set of $sum n_i$ objects that you want to select $sum r_i$ objects from.
Clearly, any selection while the objects are grouped into $N$ sets works as a selection when they're grouped together. The opposite is not true. When you group them together, you can select more than $r_i$ items from set $i$, and less from some other set to compensate. So LHS < RHS.
answered Jan 29 at 8:32
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
Thinking combinatorially is really powerful! My takeaway is that I should interpret objects combinatorially in the first place, instead of writing out the formulae explicitly as what I tried.
$endgroup$
– Amateur
Jan 29 at 16:11
add a comment |
$begingroup$
It is true indeed. Let's try to interpret the LHS and the RHS combinatorially.
LHS: You have N sets. Set $i$ has $n_i$ objects. You want to choose $r_i$ objects from the $i$th set. The LHS answers many ways can you do that.
RHS: Now imagine you grouped all the sets together. Now you have one set of $sum n_i$ objects that you want to select $sum r_i$ objects from.
Clearly, any selection while the objects are grouped into $N$ sets works as a selection when they're grouped together. The opposite is not true. When you group them together, you can select more than $r_i$ items from set $i$, and less from some other set to compensate. So LHS < RHS.
answered Jan 29 at 8:32
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
Thinking combinatorially is really powerful! My takeaway is that I should interpret objects combinatorially in the first place, instead of writing out the formulae explicitly as what I tried.
$endgroup$
– Amateur
Jan 29 at 16:11
add a comment |
$begingroup$
It is true indeed. Let's try to interpret the LHS and the RHS combinatorially.
LHS: You have N sets. Set $i$ has $n_i$ objects. You want to choose $r_i$ objects from the $i$th set. The LHS answers many ways can you do that.
RHS: Now imagine you grouped all the sets together. Now you have one set of $sum n_i$ objects that you want to select $sum r_i$ objects from.
Clearly, any selection while the objects are grouped into $N$ sets works as a selection when they're grouped together. The opposite is not true. When you group them together, you can select more than $r_i$ items from set $i$, and less from some other set to compensate. So LHS < RHS.
answered Jan 29 at 8:32
Todor MarkovTodor Markov
2,420412
$endgroup$
It is true indeed. Let's try to interpret the LHS and the RHS combinatorially.
LHS: You have N sets. Set $i$ has $n_i$ objects. You want to choose $r_i$ objects from the $i$th set. The LHS answers many ways can you do that.
RHS: Now imagine you grouped all the sets together. Now you have one set of $sum n_i$ objects that you want to select $sum r_i$ objects from.
Clearly, any selection while the objects are grouped into $N$ sets works as a selection when they're grouped together. The opposite is not true. When you group them together, you can select more than $r_i$ items from set $i$, and less from some other set to compensate. So LHS < RHS.
answered Jan 29 at 8:32
Todor MarkovTodor Markov
2,420412
answered Jan 29 at 8:32
Todor MarkovTodor Markov
2,420412
answered Jan 29 at 8:32
Todor MarkovTodor Markov
2,420412
answered Jan 29 at 8:32
Todor MarkovTodor Markov
2,420412
2,420412
$begingroup$
Thinking combinatorially is really powerful! My takeaway is that I should interpret objects combinatorially in the first place, instead of writing out the formulae explicitly as what I tried.
$endgroup$
– Amateur
Jan 29 at 16:11
add a comment |
$begingroup$
Thinking combinatorially is really powerful! My takeaway is that I should interpret objects combinatorially in the first place, instead of writing out the formulae explicitly as what I tried.
$endgroup$
– Amateur
Jan 29 at 16:11
$begingroup$
Thinking combinatorially is really powerful! My takeaway is that I should interpret objects combinatorially in the first place, instead of writing out the formulae explicitly as what I tried.
$endgroup$
– Amateur
Jan 29 at 16:11
$begingroup$
Thinking combinatorially is really powerful! My takeaway is that I should interpret objects combinatorially in the first place, instead of writing out the formulae explicitly as what I tried.
$endgroup$
– Amateur
Jan 29 at 16:11
add a comment |
$begingroup$
Assuming $0le k_jle n_j$ for all $1le jle m$,
$$
begin{align}
binom{n_1+n_2}{k_1+k_2}
&=sum_{j=0}^{k_1+k_2}binom{n_1}{j}binom{n_2}{k_1+k_2-j}tag1\
&gebinom{n_1}{k_1}binom{n_2}{k_2}tag2
end{align}
$$
Explanation:
$(1)$: Vandermonde Identity
$(2)$: one term ($j=k_1$) in a sum of non-negative numbers is no greater than the entire sum
Note that if $0lt k_1+k_2lt n_1+n_2$, there are at least two positive terms in $(1)$, so the inequality is strict.
Induction and $(2)$ show that
$$
binom{sum_{j=1}^mn_j}{sum_{j=1}^mk_j}geprod_{j=1}^mbinom{n_j}{k_j}tag3
$$
and if $0ltsum_{j=1}^mk_jltsum_{j=1}^mn_j$, the inequality in $(3)$ is strict.
answered Jan 30 at 7:59
robjohn♦robjohn
270k27312640
$endgroup$
$begingroup$
This proof using Vandermonde's identity is beautiful. Furthermore, Step (2) also makes it clear to me why the RHS (in my question) is far greater than the LHS in a bunch of experiments.
$endgroup$
– Amateur
Jan 31 at 20:07
add a comment |
$begingroup$
Assuming $0le k_jle n_j$ for all $1le jle m$,
$$
begin{align}
binom{n_1+n_2}{k_1+k_2}
&=sum_{j=0}^{k_1+k_2}binom{n_1}{j}binom{n_2}{k_1+k_2-j}tag1\
&gebinom{n_1}{k_1}binom{n_2}{k_2}tag2
end{align}
$$
Explanation:
$(1)$: Vandermonde Identity
$(2)$: one term ($j=k_1$) in a sum of non-negative numbers is no greater than the entire sum
Note that if $0lt k_1+k_2lt n_1+n_2$, there are at least two positive terms in $(1)$, so the inequality is strict.
Induction and $(2)$ show that
$$
binom{sum_{j=1}^mn_j}{sum_{j=1}^mk_j}geprod_{j=1}^mbinom{n_j}{k_j}tag3
$$
and if $0ltsum_{j=1}^mk_jltsum_{j=1}^mn_j$, the inequality in $(3)$ is strict.
answered Jan 30 at 7:59
robjohn♦robjohn
270k27312640
$endgroup$
$begingroup$
This proof using Vandermonde's identity is beautiful. Furthermore, Step (2) also makes it clear to me why the RHS (in my question) is far greater than the LHS in a bunch of experiments.
$endgroup$
– Amateur
Jan 31 at 20:07
add a comment |
$begingroup$
Assuming $0le k_jle n_j$ for all $1le jle m$,
$$
begin{align}
binom{n_1+n_2}{k_1+k_2}
&=sum_{j=0}^{k_1+k_2}binom{n_1}{j}binom{n_2}{k_1+k_2-j}tag1\
&gebinom{n_1}{k_1}binom{n_2}{k_2}tag2
end{align}
$$
Explanation:
$(1)$: Vandermonde Identity
$(2)$: one term ($j=k_1$) in a sum of non-negative numbers is no greater than the entire sum
Note that if $0lt k_1+k_2lt n_1+n_2$, there are at least two positive terms in $(1)$, so the inequality is strict.
Induction and $(2)$ show that
$$
binom{sum_{j=1}^mn_j}{sum_{j=1}^mk_j}geprod_{j=1}^mbinom{n_j}{k_j}tag3
$$
and if $0ltsum_{j=1}^mk_jltsum_{j=1}^mn_j$, the inequality in $(3)$ is strict.
answered Jan 30 at 7:59
robjohn♦robjohn
270k27312640
$endgroup$
Assuming $0le k_jle n_j$ for all $1le jle m$,
$$
begin{align}
binom{n_1+n_2}{k_1+k_2}
&=sum_{j=0}^{k_1+k_2}binom{n_1}{j}binom{n_2}{k_1+k_2-j}tag1\
&gebinom{n_1}{k_1}binom{n_2}{k_2}tag2
end{align}
$$
Explanation:
$(1)$: Vandermonde Identity
$(2)$: one term ($j=k_1$) in a sum of non-negative numbers is no greater than the entire sum
Note that if $0lt k_1+k_2lt n_1+n_2$, there are at least two positive terms in $(1)$, so the inequality is strict.
Induction and $(2)$ show that
$$
binom{sum_{j=1}^mn_j}{sum_{j=1}^mk_j}geprod_{j=1}^mbinom{n_j}{k_j}tag3
$$
and if $0ltsum_{j=1}^mk_jltsum_{j=1}^mn_j$, the inequality in $(3)$ is strict.
answered Jan 30 at 7:59
robjohn♦robjohn
270k27312640
answered Jan 30 at 7:59
robjohn♦robjohn
270k27312640
answered Jan 30 at 7:59
robjohn♦robjohn
270k27312640
answered Jan 30 at 7:59
robjohn♦robjohn
270k27312640
270k27312640
$begingroup$
This proof using Vandermonde's identity is beautiful. Furthermore, Step (2) also makes it clear to me why the RHS (in my question) is far greater than the LHS in a bunch of experiments.
$endgroup$
– Amateur
Jan 31 at 20:07
add a comment |
$begingroup$
This proof using Vandermonde's identity is beautiful. Furthermore, Step (2) also makes it clear to me why the RHS (in my question) is far greater than the LHS in a bunch of experiments.
$endgroup$
– Amateur
Jan 31 at 20:07
$begingroup$
This proof using Vandermonde's identity is beautiful. Furthermore, Step (2) also makes it clear to me why the RHS (in my question) is far greater than the LHS in a bunch of experiments.
$endgroup$
– Amateur
Jan 31 at 20:07
$begingroup$
This proof using Vandermonde's identity is beautiful. Furthermore, Step (2) also makes it clear to me why the RHS (in my question) is far greater than the LHS in a bunch of experiments.
$endgroup$
– Amateur
Jan 31 at 20:07
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%2f3091914%2fproduct-of-combinations-and-combination-of-sums%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
