Mixing
Combinatorics problem regarding two kinds of elements
$begingroup$
I'm trying to understand this problem as exposed in William Feller's An introduction to probability theory and its applications:
(d) Flags of one or two colors. In example (1.f) it was shown that r flags can be displayed on n poles in N = n(n+ 1) ... (n+r-1) different ways. We now consider the same problem for flags of one
color (considered indistinguishable). Numbering the flags of such a
display yields exactly r! displays of r distinguishable flags and
hence r flags of the same color can be displayed in N/r! ways.
I understand that a group of r distinguishable elements yield r! ordered samples of size r. But I do not understand why is it that r
undistinguished flags can be displayed in N/r! ways. As I think about it, since they are supposed to be undistinguished, shouldn't there be only one way to order them? Does N/r! always yield 1? If so, why?
Many thanks
probability combinatorics
asked Jan 7 at 12:59
César D. VázquezCésar D. Vázquez
1767
$endgroup$
add a comment |
$begingroup$
I'm trying to understand this problem as exposed in William Feller's An introduction to probability theory and its applications:
(d) Flags of one or two colors. In example (1.f) it was shown that r flags can be displayed on n poles in N = n(n+ 1) ... (n+r-1) different ways. We now consider the same problem for flags of one
color (considered indistinguishable). Numbering the flags of such a
display yields exactly r! displays of r distinguishable flags and
hence r flags of the same color can be displayed in N/r! ways.
I understand that a group of r distinguishable elements yield r! ordered samples of size r. But I do not understand why is it that r
undistinguished flags can be displayed in N/r! ways. As I think about it, since they are supposed to be undistinguished, shouldn't there be only one way to order them? Does N/r! always yield 1? If so, why?
Many thanks
probability combinatorics
asked Jan 7 at 12:59
César D. VázquezCésar D. Vázquez
1767
$endgroup$
add a comment |
$begingroup$
I'm trying to understand this problem as exposed in William Feller's An introduction to probability theory and its applications:
(d) Flags of one or two colors. In example (1.f) it was shown that r flags can be displayed on n poles in N = n(n+ 1) ... (n+r-1) different ways. We now consider the same problem for flags of one
color (considered indistinguishable). Numbering the flags of such a
display yields exactly r! displays of r distinguishable flags and
hence r flags of the same color can be displayed in N/r! ways.
I understand that a group of r distinguishable elements yield r! ordered samples of size r. But I do not understand why is it that r
undistinguished flags can be displayed in N/r! ways. As I think about it, since they are supposed to be undistinguished, shouldn't there be only one way to order them? Does N/r! always yield 1? If so, why?
Many thanks
probability combinatorics
asked Jan 7 at 12:59
César D. VázquezCésar D. Vázquez
1767
$endgroup$
I'm trying to understand this problem as exposed in William Feller's An introduction to probability theory and its applications:
(d) Flags of one or two colors. In example (1.f) it was shown that r flags can be displayed on n poles in N = n(n+ 1) ... (n+r-1) different ways. We now consider the same problem for flags of one
color (considered indistinguishable). Numbering the flags of such a
display yields exactly r! displays of r distinguishable flags and
hence r flags of the same color can be displayed in N/r! ways.
I understand that a group of r distinguishable elements yield r! ordered samples of size r. But I do not understand why is it that r
undistinguished flags can be displayed in N/r! ways. As I think about it, since they are supposed to be undistinguished, shouldn't there be only one way to order them? Does N/r! always yield 1? If so, why?
Many thanks
probability combinatorics
probability combinatorics
asked Jan 7 at 12:59
César D. VázquezCésar D. Vázquez
1767
asked Jan 7 at 12:59
César D. VázquezCésar D. Vázquez
1767
asked Jan 7 at 12:59
César D. VázquezCésar D. Vázquez
1767
asked Jan 7 at 12:59
César D. VázquezCésar D. Vázquez
1767
asked Jan 7 at 12:59
César D. VázquezCésar D. Vázquez
1767
1767
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Put stickers with numbers $1$ to $r$ on the flags. Now after displaying the $r$ flags on $n$ poles, you can rearrange the stickers in $r!$ ways. That is, $r!$ different ways to display distinguishable flags correspond to $1$ way to display indistinguishable flags. Hence, if there are $N$ ways to display distinguishable flags, then there are $N/r!$ ways to display indistinguishable flags. The number $N/r!$ is not always $1$. For example if there are $n=2$ poles and $r=3$ indistinguishable flags there are $4$ ways to display them (indexed by the number of flags on the first pole). In fact displaying $r$ indistinguishable flags on $n$ poles counts the number of ordered number partitions of $r$ into $n$ non-negative parts, in the example with $n=2$, $r=3$ the displays correspond to the $4$ partitions
$$
0+3, 1+2, 2+1, 3+0.
$$
answered Jan 7 at 13:59
ChristophChristoph
11.9k1642
$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%2f3064979%2fcombinatorics-problem-regarding-two-kinds-of-elements%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$
Put stickers with numbers $1$ to $r$ on the flags. Now after displaying the $r$ flags on $n$ poles, you can rearrange the stickers in $r!$ ways. That is, $r!$ different ways to display distinguishable flags correspond to $1$ way to display indistinguishable flags. Hence, if there are $N$ ways to display distinguishable flags, then there are $N/r!$ ways to display indistinguishable flags. The number $N/r!$ is not always $1$. For example if there are $n=2$ poles and $r=3$ indistinguishable flags there are $4$ ways to display them (indexed by the number of flags on the first pole). In fact displaying $r$ indistinguishable flags on $n$ poles counts the number of ordered number partitions of $r$ into $n$ non-negative parts, in the example with $n=2$, $r=3$ the displays correspond to the $4$ partitions
$$
0+3, 1+2, 2+1, 3+0.
$$
answered Jan 7 at 13:59
ChristophChristoph
11.9k1642
$endgroup$
add a comment |
$begingroup$
Put stickers with numbers $1$ to $r$ on the flags. Now after displaying the $r$ flags on $n$ poles, you can rearrange the stickers in $r!$ ways. That is, $r!$ different ways to display distinguishable flags correspond to $1$ way to display indistinguishable flags. Hence, if there are $N$ ways to display distinguishable flags, then there are $N/r!$ ways to display indistinguishable flags. The number $N/r!$ is not always $1$. For example if there are $n=2$ poles and $r=3$ indistinguishable flags there are $4$ ways to display them (indexed by the number of flags on the first pole). In fact displaying $r$ indistinguishable flags on $n$ poles counts the number of ordered number partitions of $r$ into $n$ non-negative parts, in the example with $n=2$, $r=3$ the displays correspond to the $4$ partitions
$$
0+3, 1+2, 2+1, 3+0.
$$
answered Jan 7 at 13:59
ChristophChristoph
11.9k1642
$endgroup$
add a comment |
$begingroup$
Put stickers with numbers $1$ to $r$ on the flags. Now after displaying the $r$ flags on $n$ poles, you can rearrange the stickers in $r!$ ways. That is, $r!$ different ways to display distinguishable flags correspond to $1$ way to display indistinguishable flags. Hence, if there are $N$ ways to display distinguishable flags, then there are $N/r!$ ways to display indistinguishable flags. The number $N/r!$ is not always $1$. For example if there are $n=2$ poles and $r=3$ indistinguishable flags there are $4$ ways to display them (indexed by the number of flags on the first pole). In fact displaying $r$ indistinguishable flags on $n$ poles counts the number of ordered number partitions of $r$ into $n$ non-negative parts, in the example with $n=2$, $r=3$ the displays correspond to the $4$ partitions
$$
0+3, 1+2, 2+1, 3+0.
$$
answered Jan 7 at 13:59
ChristophChristoph
11.9k1642
$endgroup$
Put stickers with numbers $1$ to $r$ on the flags. Now after displaying the $r$ flags on $n$ poles, you can rearrange the stickers in $r!$ ways. That is, $r!$ different ways to display distinguishable flags correspond to $1$ way to display indistinguishable flags. Hence, if there are $N$ ways to display distinguishable flags, then there are $N/r!$ ways to display indistinguishable flags. The number $N/r!$ is not always $1$. For example if there are $n=2$ poles and $r=3$ indistinguishable flags there are $4$ ways to display them (indexed by the number of flags on the first pole). In fact displaying $r$ indistinguishable flags on $n$ poles counts the number of ordered number partitions of $r$ into $n$ non-negative parts, in the example with $n=2$, $r=3$ the displays correspond to the $4$ partitions
$$
0+3, 1+2, 2+1, 3+0.
$$
answered Jan 7 at 13:59
ChristophChristoph
11.9k1642
answered Jan 7 at 13:59
ChristophChristoph
11.9k1642
answered Jan 7 at 13:59
ChristophChristoph
11.9k1642
answered Jan 7 at 13:59
ChristophChristoph
11.9k1642
11.9k1642
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%2f3064979%2fcombinatorics-problem-regarding-two-kinds-of-elements%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
