Number of ways to pick an equal number of elements from two sets?
$begingroup$
There are two groups such that one group contains $m$ elements and another group contains $n$ elements. We have to find number of ways to pick same number of elements from both the groups.
My approach is
$1+dbinom m1.dbinom n1+dbinom m2 . dbinom n2 +.... $upto $dbinom mm$ or $dbinom nn$ whatever is smaller.
Is there any faster way to do the same?
Example:
$3$ and $2$
$1+dbinom 31.dbinom 21+dbinom 32 . dbinom 22=10$ ways
combinatorics permutations
edited Nov 19 '18 at 14:25
SmarthBansal
36412
asked Nov 19 '18 at 14:09
Sagar SharmaSagar Sharma
143
$endgroup$
add a comment |
$begingroup$
There are two groups such that one group contains $m$ elements and another group contains $n$ elements. We have to find number of ways to pick same number of elements from both the groups.
My approach is
$1+dbinom m1.dbinom n1+dbinom m2 . dbinom n2 +.... $upto $dbinom mm$ or $dbinom nn$ whatever is smaller.
Is there any faster way to do the same?
Example:
$3$ and $2$
$1+dbinom 31.dbinom 21+dbinom 32 . dbinom 22=10$ ways
combinatorics permutations
edited Nov 19 '18 at 14:25
SmarthBansal
36412
asked Nov 19 '18 at 14:09
Sagar SharmaSagar Sharma
143
$endgroup$
add a comment |
$begingroup$
There are two groups such that one group contains $m$ elements and another group contains $n$ elements. We have to find number of ways to pick same number of elements from both the groups.
My approach is
$1+dbinom m1.dbinom n1+dbinom m2 . dbinom n2 +.... $upto $dbinom mm$ or $dbinom nn$ whatever is smaller.
Is there any faster way to do the same?
Example:
$3$ and $2$
$1+dbinom 31.dbinom 21+dbinom 32 . dbinom 22=10$ ways
combinatorics permutations
edited Nov 19 '18 at 14:25
SmarthBansal
36412
asked Nov 19 '18 at 14:09
Sagar SharmaSagar Sharma
143
$endgroup$
There are two groups such that one group contains $m$ elements and another group contains $n$ elements. We have to find number of ways to pick same number of elements from both the groups.
My approach is
$1+dbinom m1.dbinom n1+dbinom m2 . dbinom n2 +.... $upto $dbinom mm$ or $dbinom nn$ whatever is smaller.
Is there any faster way to do the same?
Example:
$3$ and $2$
$1+dbinom 31.dbinom 21+dbinom 32 . dbinom 22=10$ ways
combinatorics permutations
combinatorics permutations
edited Nov 19 '18 at 14:25
SmarthBansal
36412
asked Nov 19 '18 at 14:09
Sagar SharmaSagar Sharma
143
edited Nov 19 '18 at 14:25
SmarthBansal
36412
asked Nov 19 '18 at 14:09
Sagar SharmaSagar Sharma
143
edited Nov 19 '18 at 14:25
SmarthBansal
36412
edited Nov 19 '18 at 14:25
SmarthBansal
36412
edited Nov 19 '18 at 14:25
SmarthBansal
36412
36412
asked Nov 19 '18 at 14:09
Sagar SharmaSagar Sharma
143
asked Nov 19 '18 at 14:09
Sagar SharmaSagar Sharma
143
asked Nov 19 '18 at 14:09
Sagar SharmaSagar Sharma
143
143
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Yes, you can do better! The number of objects as you've described can be written as:
$$ sum_{k=0}^{min(m,n)} binom{n}{k}binom{m}{k}. $$
Notice that we could choose to stop the sum at either $m$ or $n$, regardless of which one is larger. For instance, even if $m>n$, whenever $k>n$ the first factor vanishes. We'll choose to stop the summation at $m$, and then apply the symmetry of binomial coefficients to get
$$ sum_{k=0}^m binom{n}{k}binom{m}{m-k} $$
I claim that this can simplify in the following way:
Proposition: $qquadqquaddisplaystyle sum_{k=0}^m binom{n}{k}binom{m}{m-k} = binom{m+n}{m}$.
The right-hand side clearly counts the number of ways to choose $m$ objects from $m+n$. The left-hand side also counts this because you must choose some number of the first $n$; call that $k$. By definition, the other $m-k$ must be chosen from the remaining $m$. Apply the product principle and we're done.
answered Dec 30 '18 at 4:23
aleph_twoaleph_two
22412
$endgroup$
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%2f3004976%2fnumber-of-ways-to-pick-an-equal-number-of-elements-from-two-sets%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$
Yes, you can do better! The number of objects as you've described can be written as:
$$ sum_{k=0}^{min(m,n)} binom{n}{k}binom{m}{k}. $$
Notice that we could choose to stop the sum at either $m$ or $n$, regardless of which one is larger. For instance, even if $m>n$, whenever $k>n$ the first factor vanishes. We'll choose to stop the summation at $m$, and then apply the symmetry of binomial coefficients to get
$$ sum_{k=0}^m binom{n}{k}binom{m}{m-k} $$
I claim that this can simplify in the following way:
Proposition: $qquadqquaddisplaystyle sum_{k=0}^m binom{n}{k}binom{m}{m-k} = binom{m+n}{m}$.
The right-hand side clearly counts the number of ways to choose $m$ objects from $m+n$. The left-hand side also counts this because you must choose some number of the first $n$; call that $k$. By definition, the other $m-k$ must be chosen from the remaining $m$. Apply the product principle and we're done.
answered Dec 30 '18 at 4:23
aleph_twoaleph_two
22412
$endgroup$
add a comment |
$begingroup$
Yes, you can do better! The number of objects as you've described can be written as:
$$ sum_{k=0}^{min(m,n)} binom{n}{k}binom{m}{k}. $$
Notice that we could choose to stop the sum at either $m$ or $n$, regardless of which one is larger. For instance, even if $m>n$, whenever $k>n$ the first factor vanishes. We'll choose to stop the summation at $m$, and then apply the symmetry of binomial coefficients to get
$$ sum_{k=0}^m binom{n}{k}binom{m}{m-k} $$
I claim that this can simplify in the following way:
Proposition: $qquadqquaddisplaystyle sum_{k=0}^m binom{n}{k}binom{m}{m-k} = binom{m+n}{m}$.
The right-hand side clearly counts the number of ways to choose $m$ objects from $m+n$. The left-hand side also counts this because you must choose some number of the first $n$; call that $k$. By definition, the other $m-k$ must be chosen from the remaining $m$. Apply the product principle and we're done.
answered Dec 30 '18 at 4:23
aleph_twoaleph_two
22412
$endgroup$
add a comment |
$begingroup$
Yes, you can do better! The number of objects as you've described can be written as:
$$ sum_{k=0}^{min(m,n)} binom{n}{k}binom{m}{k}. $$
Notice that we could choose to stop the sum at either $m$ or $n$, regardless of which one is larger. For instance, even if $m>n$, whenever $k>n$ the first factor vanishes. We'll choose to stop the summation at $m$, and then apply the symmetry of binomial coefficients to get
$$ sum_{k=0}^m binom{n}{k}binom{m}{m-k} $$
I claim that this can simplify in the following way:
Proposition: $qquadqquaddisplaystyle sum_{k=0}^m binom{n}{k}binom{m}{m-k} = binom{m+n}{m}$.
The right-hand side clearly counts the number of ways to choose $m$ objects from $m+n$. The left-hand side also counts this because you must choose some number of the first $n$; call that $k$. By definition, the other $m-k$ must be chosen from the remaining $m$. Apply the product principle and we're done.
answered Dec 30 '18 at 4:23
aleph_twoaleph_two
22412
$endgroup$
Yes, you can do better! The number of objects as you've described can be written as:
$$ sum_{k=0}^{min(m,n)} binom{n}{k}binom{m}{k}. $$
Notice that we could choose to stop the sum at either $m$ or $n$, regardless of which one is larger. For instance, even if $m>n$, whenever $k>n$ the first factor vanishes. We'll choose to stop the summation at $m$, and then apply the symmetry of binomial coefficients to get
$$ sum_{k=0}^m binom{n}{k}binom{m}{m-k} $$
I claim that this can simplify in the following way:
Proposition: $qquadqquaddisplaystyle sum_{k=0}^m binom{n}{k}binom{m}{m-k} = binom{m+n}{m}$.
The right-hand side clearly counts the number of ways to choose $m$ objects from $m+n$. The left-hand side also counts this because you must choose some number of the first $n$; call that $k$. By definition, the other $m-k$ must be chosen from the remaining $m$. Apply the product principle and we're done.
answered Dec 30 '18 at 4:23
aleph_twoaleph_two
22412
answered Dec 30 '18 at 4:23
aleph_twoaleph_two
22412
answered Dec 30 '18 at 4:23
aleph_twoaleph_two
22412
answered Dec 30 '18 at 4:23
aleph_twoaleph_two
22412
22412
add a comment |
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%2f3004976%2fnumber-of-ways-to-pick-an-equal-number-of-elements-from-two-sets%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
