Permutations with simultaneous repetition and restriction(subset length)
up vote
2
down vote
favorite
I'm trying to figure out a problem, but I'm unable to find the formula to use, and not knowledgeable enough to try to derive it myself.
The problem is that I have a string of between 10-15 characters, which may contain duplicates. I want to calculate how many 10 character strings I can make from it that are unique. The strings are random text snippets, for ex lets say i have:
$$(parallelfoods)$$
The math as I've understood it: I have a multiset of $n$ items with $n_1$ of kind 1, $n_2$ of kind 2. I want to calculate the number of length $k$ tuples from this multiset (where $k<n$).
So in the example it's:
$$n=13$$
$$n_p=1, n_a=2, n_r=1, n_l=3ldots$$
$$k=10$$
My progress: I have been able to learn from several sites how to calculate these two cases separately. The duplicate items is solved by: $$frac{n!}{(n_1!n_2!ldots)}$$
Similarly I understand that the limiting to $k$ items is solved using:
$$frac{n!}{(n-k)!}$$
Where I've come to a halt is when I need to combine the two as the problem most often will require both of them.
In the example the multiset $(parallelfoods)$ has $n=13$ (that is $n>k$) as well as several items that are duplicate.
How can I calculate the number of possible unique $k$ length tuples of the multiset without having to generate all of them?
combinatorics permutations
|
show 1 more comment
up vote
2
down vote
favorite
I'm trying to figure out a problem, but I'm unable to find the formula to use, and not knowledgeable enough to try to derive it myself.
The problem is that I have a string of between 10-15 characters, which may contain duplicates. I want to calculate how many 10 character strings I can make from it that are unique. The strings are random text snippets, for ex lets say i have:
$$(parallelfoods)$$
The math as I've understood it: I have a multiset of $n$ items with $n_1$ of kind 1, $n_2$ of kind 2. I want to calculate the number of length $k$ tuples from this multiset (where $k<n$).
So in the example it's:
$$n=13$$
$$n_p=1, n_a=2, n_r=1, n_l=3ldots$$
$$k=10$$
My progress: I have been able to learn from several sites how to calculate these two cases separately. The duplicate items is solved by: $$frac{n!}{(n_1!n_2!ldots)}$$
Similarly I understand that the limiting to $k$ items is solved using:
$$frac{n!}{(n-k)!}$$
Where I've come to a halt is when I need to combine the two as the problem most often will require both of them.
In the example the multiset $(parallelfoods)$ has $n=13$ (that is $n>k$) as well as several items that are duplicate.
How can I calculate the number of possible unique $k$ length tuples of the multiset without having to generate all of them?
combinatorics permutations
Welcome to MathSE. The answer to your question will depend on the exact composition of the multiset. You may want to consider a concrete example so that you can learn a technique for solving this type of problem. If you choose to do so, please show your own attempt and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site.
– N. F. Taussig
Nov 23 at 12:07
Thanks for you comments. I've tried to use the formula code and also added an example input to discuss.
– Erik
Nov 23 at 14:54
It's best not to call your "set" a "set", since it is a multiset, and also not to call your "permutations" "permutations", since they may contain fewer than all elements of the multiset. So you are looking for the number of $k$-tuples of letters, where each letter appears at most a given number of times (namely, how often it appears in the original "set"). You can get an alternating-sign-sum expression for the answer using Inclusion-Exclusion (by first counting arbitrary $k$-tuples, and then excluding the ones where a letter appears too frequently), ...
– darij grinberg
Nov 23 at 18:26
... but I don't think there is anything like a closed form for this problem.
– darij grinberg
Nov 23 at 18:27
Ok, I think I get the gist of your comment. Sorry for the naming, only used what I understood from all I've read to reach the point were I wrote my question; that permutations with duplicate items was called permutations with repetition, and the k-tuple was called permutation with item restriction. Apparently I am mistaken.
– Erik
Nov 23 at 19:42
|
show 1 more comment
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I'm trying to figure out a problem, but I'm unable to find the formula to use, and not knowledgeable enough to try to derive it myself.
The problem is that I have a string of between 10-15 characters, which may contain duplicates. I want to calculate how many 10 character strings I can make from it that are unique. The strings are random text snippets, for ex lets say i have:
$$(parallelfoods)$$
The math as I've understood it: I have a multiset of $n$ items with $n_1$ of kind 1, $n_2$ of kind 2. I want to calculate the number of length $k$ tuples from this multiset (where $k<n$).
So in the example it's:
$$n=13$$
$$n_p=1, n_a=2, n_r=1, n_l=3ldots$$
$$k=10$$
My progress: I have been able to learn from several sites how to calculate these two cases separately. The duplicate items is solved by: $$frac{n!}{(n_1!n_2!ldots)}$$
Similarly I understand that the limiting to $k$ items is solved using:
$$frac{n!}{(n-k)!}$$
Where I've come to a halt is when I need to combine the two as the problem most often will require both of them.
In the example the multiset $(parallelfoods)$ has $n=13$ (that is $n>k$) as well as several items that are duplicate.
How can I calculate the number of possible unique $k$ length tuples of the multiset without having to generate all of them?
combinatorics permutations
I'm trying to figure out a problem, but I'm unable to find the formula to use, and not knowledgeable enough to try to derive it myself.
The problem is that I have a string of between 10-15 characters, which may contain duplicates. I want to calculate how many 10 character strings I can make from it that are unique. The strings are random text snippets, for ex lets say i have:
$$(parallelfoods)$$
The math as I've understood it: I have a multiset of $n$ items with $n_1$ of kind 1, $n_2$ of kind 2. I want to calculate the number of length $k$ tuples from this multiset (where $k<n$).
So in the example it's:
$$n=13$$
$$n_p=1, n_a=2, n_r=1, n_l=3ldots$$
$$k=10$$
My progress: I have been able to learn from several sites how to calculate these two cases separately. The duplicate items is solved by: $$frac{n!}{(n_1!n_2!ldots)}$$
Similarly I understand that the limiting to $k$ items is solved using:
$$frac{n!}{(n-k)!}$$
Where I've come to a halt is when I need to combine the two as the problem most often will require both of them.
In the example the multiset $(parallelfoods)$ has $n=13$ (that is $n>k$) as well as several items that are duplicate.
How can I calculate the number of possible unique $k$ length tuples of the multiset without having to generate all of them?
combinatorics permutations
combinatorics permutations
edited Nov 23 at 19:46
asked Nov 22 at 20:35
Erik
112
112
Welcome to MathSE. The answer to your question will depend on the exact composition of the multiset. You may want to consider a concrete example so that you can learn a technique for solving this type of problem. If you choose to do so, please show your own attempt and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site.
– N. F. Taussig
Nov 23 at 12:07
Thanks for you comments. I've tried to use the formula code and also added an example input to discuss.
– Erik
Nov 23 at 14:54
It's best not to call your "set" a "set", since it is a multiset, and also not to call your "permutations" "permutations", since they may contain fewer than all elements of the multiset. So you are looking for the number of $k$-tuples of letters, where each letter appears at most a given number of times (namely, how often it appears in the original "set"). You can get an alternating-sign-sum expression for the answer using Inclusion-Exclusion (by first counting arbitrary $k$-tuples, and then excluding the ones where a letter appears too frequently), ...
– darij grinberg
Nov 23 at 18:26
... but I don't think there is anything like a closed form for this problem.
– darij grinberg
Nov 23 at 18:27
Ok, I think I get the gist of your comment. Sorry for the naming, only used what I understood from all I've read to reach the point were I wrote my question; that permutations with duplicate items was called permutations with repetition, and the k-tuple was called permutation with item restriction. Apparently I am mistaken.
– Erik
Nov 23 at 19:42
|
show 1 more comment
Welcome to MathSE. The answer to your question will depend on the exact composition of the multiset. You may want to consider a concrete example so that you can learn a technique for solving this type of problem. If you choose to do so, please show your own attempt and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site.
– N. F. Taussig
Nov 23 at 12:07
Thanks for you comments. I've tried to use the formula code and also added an example input to discuss.
– Erik
Nov 23 at 14:54
It's best not to call your "set" a "set", since it is a multiset, and also not to call your "permutations" "permutations", since they may contain fewer than all elements of the multiset. So you are looking for the number of $k$-tuples of letters, where each letter appears at most a given number of times (namely, how often it appears in the original "set"). You can get an alternating-sign-sum expression for the answer using Inclusion-Exclusion (by first counting arbitrary $k$-tuples, and then excluding the ones where a letter appears too frequently), ...
– darij grinberg
Nov 23 at 18:26
... but I don't think there is anything like a closed form for this problem.
– darij grinberg
Nov 23 at 18:27
Ok, I think I get the gist of your comment. Sorry for the naming, only used what I understood from all I've read to reach the point were I wrote my question; that permutations with duplicate items was called permutations with repetition, and the k-tuple was called permutation with item restriction. Apparently I am mistaken.
– Erik
Nov 23 at 19:42
Welcome to MathSE. The answer to your question will depend on the exact composition of the multiset. You may want to consider a concrete example so that you can learn a technique for solving this type of problem. If you choose to do so, please show your own attempt and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site.
– N. F. Taussig
Nov 23 at 12:07
Welcome to MathSE. The answer to your question will depend on the exact composition of the multiset. You may want to consider a concrete example so that you can learn a technique for solving this type of problem. If you choose to do so, please show your own attempt and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site.
– N. F. Taussig
Nov 23 at 12:07
Thanks for you comments. I've tried to use the formula code and also added an example input to discuss.
– Erik
Nov 23 at 14:54
Thanks for you comments. I've tried to use the formula code and also added an example input to discuss.
– Erik
Nov 23 at 14:54
It's best not to call your "set" a "set", since it is a multiset, and also not to call your "permutations" "permutations", since they may contain fewer than all elements of the multiset. So you are looking for the number of $k$-tuples of letters, where each letter appears at most a given number of times (namely, how often it appears in the original "set"). You can get an alternating-sign-sum expression for the answer using Inclusion-Exclusion (by first counting arbitrary $k$-tuples, and then excluding the ones where a letter appears too frequently), ...
– darij grinberg
Nov 23 at 18:26
It's best not to call your "set" a "set", since it is a multiset, and also not to call your "permutations" "permutations", since they may contain fewer than all elements of the multiset. So you are looking for the number of $k$-tuples of letters, where each letter appears at most a given number of times (namely, how often it appears in the original "set"). You can get an alternating-sign-sum expression for the answer using Inclusion-Exclusion (by first counting arbitrary $k$-tuples, and then excluding the ones where a letter appears too frequently), ...
– darij grinberg
Nov 23 at 18:26
... but I don't think there is anything like a closed form for this problem.
– darij grinberg
Nov 23 at 18:27
... but I don't think there is anything like a closed form for this problem.
– darij grinberg
Nov 23 at 18:27
Ok, I think I get the gist of your comment. Sorry for the naming, only used what I understood from all I've read to reach the point were I wrote my question; that permutations with duplicate items was called permutations with repetition, and the k-tuple was called permutation with item restriction. Apparently I am mistaken.
– Erik
Nov 23 at 19:42
Ok, I think I get the gist of your comment. Sorry for the naming, only used what I understood from all I've read to reach the point were I wrote my question; that permutations with duplicate items was called permutations with repetition, and the k-tuple was called permutation with item restriction. Apparently I am mistaken.
– Erik
Nov 23 at 19:42
|
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
0
down vote
The phrase $parallel foods$ can be viewed as the multiset
$${1 cdot p, 2 cdot a, 1 cdot r, 3 cdot l, 1 cdot e, 1 cdot f, 2 cdot o, 1 cdot d, 1 cdot s}$$
We wish to count the number of strings of length $10$ that can be formed with the letters of this multiset.
We consider cases:
- Nine distinct letters are used, including one letter that appears twice.
- Eight distinct letters are used, including one letter that appears three times.
- Eight distinct letters are used, including two letters that each appear twice.
- Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
- Seven distinct letters are used, including three letters that each appear twice.
- Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
Case 1: Nine distinct letters are used, including one letter that appears twice.
Choose which of the three letters that have multiplicity greater than one will be used twice. Choose two of the ten positions for that letter. Arrange the other eight distinct letters in the multiset in the remaining eight positions. There are
$$binom{3}{1}binom{10}{2}8!$$
such arrangements.
Case 2: Eight distinct letters are used, including one letter that appears three times.
The only letter that can appear three times is $l$. Choose three of the ten positions in the string for the $l$s. If $l$ appears three times, then one of the other eight letters must not appear in the string. Choose which letter to exclude. Arrange the remaining seven distinct letters in the multiset in the remaining seven positions. There are
$$binom{10}{3}binom{8}{1}7!$$
such arrangements.
Case 3: Eight distinct letters are used, including two letters that each appear twice.
Choose which two of the three letters with multiplicity greater than one will appear twice. Choose two of the ten positions in the string for the selected letter that appears first in an alphabetical list. Choose two of the remaining eight positions in the string for the other letter that will appear twice. If these two letters are each used twice, one of the other seven letters in the multiset will not appear in the string at all. Choose which letter will be excluded. Arrange the remaining six distinct letters in the multiset in the remaining six positions of the string. There are
$$binom{3}{2}binom{10}{2}binom{7}{1}6!$$
such arrangements.
Case 4: Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
The letter that appears three times must be $l$. Choose three of the ten positions in the string for the $l$s. Choose whether $a$ or $o$ appears twice. Choose two of the remaining seven positions in the string for that letter. If $l$ appears three times and another letter appears twice, two of the other seven letters in the multiset must not appear at all. Choose which two of them to exclude. Arrange the remaining five distinct letters of the multiset in the remaining five positions in the string. There are
$$binom{10}{3}binom{7}{2}binom{7}{2}5!$$
such arrangements.
Case 5: Seven distinct letters are used, including three letters that each appear twice.
The three letters that each appear twice must be $a$, $l$, and $o$. Choose two of the ten positions in the string for the $a$s, two of the remaining eight positions in the string for for the $l$s, and two of the remaining six positions in the string for the $o$s. Since $a$, $l$, and $o$ each appear twice, two of the other six letters in the multiset must not appear at all in the string. Choose which two letters to exclude. Arrange the remaining four distinct letters of the multiset in the remaining four positions. There are
$$binom{10}{2}binom{8}{2}binom{6}{2}binom{6}{2}4!$$
such arrangements.
Case 6: Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
The letter that appears three times must be $l$. The letters that each appear exactly twice must be $a$ and $o$. Choose three of the ten positions for the $l$s, two of the remaining seven positions for the $a$s, and two of the remaining five positions for the $o$s. Since $l$ appears three times and $a$ and $o$ each appear twice, three of the other six letters in the multiset must not appear at all. Choose which three letters to exclude. Arrange the remaining three letters of the multiset in the remaining three positions. There are
$$binom{10}{3}binom{7}{2}binom{5}{2}binom{6}{3}3!$$
such arrangements.
Total: Since the six cases outlined above are mutually exclusive and exhaustive, the number of distinguishable strings of length $10$ can be found by adding the above cases.
Note: This problem could also be approached using exponential generating functions.
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',
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%2f3009624%2fpermutations-with-simultaneous-repetition-and-restrictionsubset-length%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
up vote
0
down vote
The phrase $parallel foods$ can be viewed as the multiset
$${1 cdot p, 2 cdot a, 1 cdot r, 3 cdot l, 1 cdot e, 1 cdot f, 2 cdot o, 1 cdot d, 1 cdot s}$$
We wish to count the number of strings of length $10$ that can be formed with the letters of this multiset.
We consider cases:
- Nine distinct letters are used, including one letter that appears twice.
- Eight distinct letters are used, including one letter that appears three times.
- Eight distinct letters are used, including two letters that each appear twice.
- Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
- Seven distinct letters are used, including three letters that each appear twice.
- Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
Case 1: Nine distinct letters are used, including one letter that appears twice.
Choose which of the three letters that have multiplicity greater than one will be used twice. Choose two of the ten positions for that letter. Arrange the other eight distinct letters in the multiset in the remaining eight positions. There are
$$binom{3}{1}binom{10}{2}8!$$
such arrangements.
Case 2: Eight distinct letters are used, including one letter that appears three times.
The only letter that can appear three times is $l$. Choose three of the ten positions in the string for the $l$s. If $l$ appears three times, then one of the other eight letters must not appear in the string. Choose which letter to exclude. Arrange the remaining seven distinct letters in the multiset in the remaining seven positions. There are
$$binom{10}{3}binom{8}{1}7!$$
such arrangements.
Case 3: Eight distinct letters are used, including two letters that each appear twice.
Choose which two of the three letters with multiplicity greater than one will appear twice. Choose two of the ten positions in the string for the selected letter that appears first in an alphabetical list. Choose two of the remaining eight positions in the string for the other letter that will appear twice. If these two letters are each used twice, one of the other seven letters in the multiset will not appear in the string at all. Choose which letter will be excluded. Arrange the remaining six distinct letters in the multiset in the remaining six positions of the string. There are
$$binom{3}{2}binom{10}{2}binom{7}{1}6!$$
such arrangements.
Case 4: Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
The letter that appears three times must be $l$. Choose three of the ten positions in the string for the $l$s. Choose whether $a$ or $o$ appears twice. Choose two of the remaining seven positions in the string for that letter. If $l$ appears three times and another letter appears twice, two of the other seven letters in the multiset must not appear at all. Choose which two of them to exclude. Arrange the remaining five distinct letters of the multiset in the remaining five positions in the string. There are
$$binom{10}{3}binom{7}{2}binom{7}{2}5!$$
such arrangements.
Case 5: Seven distinct letters are used, including three letters that each appear twice.
The three letters that each appear twice must be $a$, $l$, and $o$. Choose two of the ten positions in the string for the $a$s, two of the remaining eight positions in the string for for the $l$s, and two of the remaining six positions in the string for the $o$s. Since $a$, $l$, and $o$ each appear twice, two of the other six letters in the multiset must not appear at all in the string. Choose which two letters to exclude. Arrange the remaining four distinct letters of the multiset in the remaining four positions. There are
$$binom{10}{2}binom{8}{2}binom{6}{2}binom{6}{2}4!$$
such arrangements.
Case 6: Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
The letter that appears three times must be $l$. The letters that each appear exactly twice must be $a$ and $o$. Choose three of the ten positions for the $l$s, two of the remaining seven positions for the $a$s, and two of the remaining five positions for the $o$s. Since $l$ appears three times and $a$ and $o$ each appear twice, three of the other six letters in the multiset must not appear at all. Choose which three letters to exclude. Arrange the remaining three letters of the multiset in the remaining three positions. There are
$$binom{10}{3}binom{7}{2}binom{5}{2}binom{6}{3}3!$$
such arrangements.
Total: Since the six cases outlined above are mutually exclusive and exhaustive, the number of distinguishable strings of length $10$ can be found by adding the above cases.
Note: This problem could also be approached using exponential generating functions.
add a comment |
up vote
0
down vote
The phrase $parallel foods$ can be viewed as the multiset
$${1 cdot p, 2 cdot a, 1 cdot r, 3 cdot l, 1 cdot e, 1 cdot f, 2 cdot o, 1 cdot d, 1 cdot s}$$
We wish to count the number of strings of length $10$ that can be formed with the letters of this multiset.
We consider cases:
- Nine distinct letters are used, including one letter that appears twice.
- Eight distinct letters are used, including one letter that appears three times.
- Eight distinct letters are used, including two letters that each appear twice.
- Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
- Seven distinct letters are used, including three letters that each appear twice.
- Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
Case 1: Nine distinct letters are used, including one letter that appears twice.
Choose which of the three letters that have multiplicity greater than one will be used twice. Choose two of the ten positions for that letter. Arrange the other eight distinct letters in the multiset in the remaining eight positions. There are
$$binom{3}{1}binom{10}{2}8!$$
such arrangements.
Case 2: Eight distinct letters are used, including one letter that appears three times.
The only letter that can appear three times is $l$. Choose three of the ten positions in the string for the $l$s. If $l$ appears three times, then one of the other eight letters must not appear in the string. Choose which letter to exclude. Arrange the remaining seven distinct letters in the multiset in the remaining seven positions. There are
$$binom{10}{3}binom{8}{1}7!$$
such arrangements.
Case 3: Eight distinct letters are used, including two letters that each appear twice.
Choose which two of the three letters with multiplicity greater than one will appear twice. Choose two of the ten positions in the string for the selected letter that appears first in an alphabetical list. Choose two of the remaining eight positions in the string for the other letter that will appear twice. If these two letters are each used twice, one of the other seven letters in the multiset will not appear in the string at all. Choose which letter will be excluded. Arrange the remaining six distinct letters in the multiset in the remaining six positions of the string. There are
$$binom{3}{2}binom{10}{2}binom{7}{1}6!$$
such arrangements.
Case 4: Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
The letter that appears three times must be $l$. Choose three of the ten positions in the string for the $l$s. Choose whether $a$ or $o$ appears twice. Choose two of the remaining seven positions in the string for that letter. If $l$ appears three times and another letter appears twice, two of the other seven letters in the multiset must not appear at all. Choose which two of them to exclude. Arrange the remaining five distinct letters of the multiset in the remaining five positions in the string. There are
$$binom{10}{3}binom{7}{2}binom{7}{2}5!$$
such arrangements.
Case 5: Seven distinct letters are used, including three letters that each appear twice.
The three letters that each appear twice must be $a$, $l$, and $o$. Choose two of the ten positions in the string for the $a$s, two of the remaining eight positions in the string for for the $l$s, and two of the remaining six positions in the string for the $o$s. Since $a$, $l$, and $o$ each appear twice, two of the other six letters in the multiset must not appear at all in the string. Choose which two letters to exclude. Arrange the remaining four distinct letters of the multiset in the remaining four positions. There are
$$binom{10}{2}binom{8}{2}binom{6}{2}binom{6}{2}4!$$
such arrangements.
Case 6: Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
The letter that appears three times must be $l$. The letters that each appear exactly twice must be $a$ and $o$. Choose three of the ten positions for the $l$s, two of the remaining seven positions for the $a$s, and two of the remaining five positions for the $o$s. Since $l$ appears three times and $a$ and $o$ each appear twice, three of the other six letters in the multiset must not appear at all. Choose which three letters to exclude. Arrange the remaining three letters of the multiset in the remaining three positions. There are
$$binom{10}{3}binom{7}{2}binom{5}{2}binom{6}{3}3!$$
such arrangements.
Total: Since the six cases outlined above are mutually exclusive and exhaustive, the number of distinguishable strings of length $10$ can be found by adding the above cases.
Note: This problem could also be approached using exponential generating functions.
add a comment |
up vote
0
down vote
up vote
0
down vote
The phrase $parallel foods$ can be viewed as the multiset
$${1 cdot p, 2 cdot a, 1 cdot r, 3 cdot l, 1 cdot e, 1 cdot f, 2 cdot o, 1 cdot d, 1 cdot s}$$
We wish to count the number of strings of length $10$ that can be formed with the letters of this multiset.
We consider cases:
- Nine distinct letters are used, including one letter that appears twice.
- Eight distinct letters are used, including one letter that appears three times.
- Eight distinct letters are used, including two letters that each appear twice.
- Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
- Seven distinct letters are used, including three letters that each appear twice.
- Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
Case 1: Nine distinct letters are used, including one letter that appears twice.
Choose which of the three letters that have multiplicity greater than one will be used twice. Choose two of the ten positions for that letter. Arrange the other eight distinct letters in the multiset in the remaining eight positions. There are
$$binom{3}{1}binom{10}{2}8!$$
such arrangements.
Case 2: Eight distinct letters are used, including one letter that appears three times.
The only letter that can appear three times is $l$. Choose three of the ten positions in the string for the $l$s. If $l$ appears three times, then one of the other eight letters must not appear in the string. Choose which letter to exclude. Arrange the remaining seven distinct letters in the multiset in the remaining seven positions. There are
$$binom{10}{3}binom{8}{1}7!$$
such arrangements.
Case 3: Eight distinct letters are used, including two letters that each appear twice.
Choose which two of the three letters with multiplicity greater than one will appear twice. Choose two of the ten positions in the string for the selected letter that appears first in an alphabetical list. Choose two of the remaining eight positions in the string for the other letter that will appear twice. If these two letters are each used twice, one of the other seven letters in the multiset will not appear in the string at all. Choose which letter will be excluded. Arrange the remaining six distinct letters in the multiset in the remaining six positions of the string. There are
$$binom{3}{2}binom{10}{2}binom{7}{1}6!$$
such arrangements.
Case 4: Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
The letter that appears three times must be $l$. Choose three of the ten positions in the string for the $l$s. Choose whether $a$ or $o$ appears twice. Choose two of the remaining seven positions in the string for that letter. If $l$ appears three times and another letter appears twice, two of the other seven letters in the multiset must not appear at all. Choose which two of them to exclude. Arrange the remaining five distinct letters of the multiset in the remaining five positions in the string. There are
$$binom{10}{3}binom{7}{2}binom{7}{2}5!$$
such arrangements.
Case 5: Seven distinct letters are used, including three letters that each appear twice.
The three letters that each appear twice must be $a$, $l$, and $o$. Choose two of the ten positions in the string for the $a$s, two of the remaining eight positions in the string for for the $l$s, and two of the remaining six positions in the string for the $o$s. Since $a$, $l$, and $o$ each appear twice, two of the other six letters in the multiset must not appear at all in the string. Choose which two letters to exclude. Arrange the remaining four distinct letters of the multiset in the remaining four positions. There are
$$binom{10}{2}binom{8}{2}binom{6}{2}binom{6}{2}4!$$
such arrangements.
Case 6: Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
The letter that appears three times must be $l$. The letters that each appear exactly twice must be $a$ and $o$. Choose three of the ten positions for the $l$s, two of the remaining seven positions for the $a$s, and two of the remaining five positions for the $o$s. Since $l$ appears three times and $a$ and $o$ each appear twice, three of the other six letters in the multiset must not appear at all. Choose which three letters to exclude. Arrange the remaining three letters of the multiset in the remaining three positions. There are
$$binom{10}{3}binom{7}{2}binom{5}{2}binom{6}{3}3!$$
such arrangements.
Total: Since the six cases outlined above are mutually exclusive and exhaustive, the number of distinguishable strings of length $10$ can be found by adding the above cases.
Note: This problem could also be approached using exponential generating functions.
The phrase $parallel foods$ can be viewed as the multiset
$${1 cdot p, 2 cdot a, 1 cdot r, 3 cdot l, 1 cdot e, 1 cdot f, 2 cdot o, 1 cdot d, 1 cdot s}$$
We wish to count the number of strings of length $10$ that can be formed with the letters of this multiset.
We consider cases:
- Nine distinct letters are used, including one letter that appears twice.
- Eight distinct letters are used, including one letter that appears three times.
- Eight distinct letters are used, including two letters that each appear twice.
- Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
- Seven distinct letters are used, including three letters that each appear twice.
- Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
Case 1: Nine distinct letters are used, including one letter that appears twice.
Choose which of the three letters that have multiplicity greater than one will be used twice. Choose two of the ten positions for that letter. Arrange the other eight distinct letters in the multiset in the remaining eight positions. There are
$$binom{3}{1}binom{10}{2}8!$$
such arrangements.
Case 2: Eight distinct letters are used, including one letter that appears three times.
The only letter that can appear three times is $l$. Choose three of the ten positions in the string for the $l$s. If $l$ appears three times, then one of the other eight letters must not appear in the string. Choose which letter to exclude. Arrange the remaining seven distinct letters in the multiset in the remaining seven positions. There are
$$binom{10}{3}binom{8}{1}7!$$
such arrangements.
Case 3: Eight distinct letters are used, including two letters that each appear twice.
Choose which two of the three letters with multiplicity greater than one will appear twice. Choose two of the ten positions in the string for the selected letter that appears first in an alphabetical list. Choose two of the remaining eight positions in the string for the other letter that will appear twice. If these two letters are each used twice, one of the other seven letters in the multiset will not appear in the string at all. Choose which letter will be excluded. Arrange the remaining six distinct letters in the multiset in the remaining six positions of the string. There are
$$binom{3}{2}binom{10}{2}binom{7}{1}6!$$
such arrangements.
Case 4: Seven distinct letters are used, including one letter that appears three times and one other letter that appears twice.
The letter that appears three times must be $l$. Choose three of the ten positions in the string for the $l$s. Choose whether $a$ or $o$ appears twice. Choose two of the remaining seven positions in the string for that letter. If $l$ appears three times and another letter appears twice, two of the other seven letters in the multiset must not appear at all. Choose which two of them to exclude. Arrange the remaining five distinct letters of the multiset in the remaining five positions in the string. There are
$$binom{10}{3}binom{7}{2}binom{7}{2}5!$$
such arrangements.
Case 5: Seven distinct letters are used, including three letters that each appear twice.
The three letters that each appear twice must be $a$, $l$, and $o$. Choose two of the ten positions in the string for the $a$s, two of the remaining eight positions in the string for for the $l$s, and two of the remaining six positions in the string for the $o$s. Since $a$, $l$, and $o$ each appear twice, two of the other six letters in the multiset must not appear at all in the string. Choose which two letters to exclude. Arrange the remaining four distinct letters of the multiset in the remaining four positions. There are
$$binom{10}{2}binom{8}{2}binom{6}{2}binom{6}{2}4!$$
such arrangements.
Case 6: Six distinct letters are used, including one letter that appears three times and two other letters that each appear twice.
The letter that appears three times must be $l$. The letters that each appear exactly twice must be $a$ and $o$. Choose three of the ten positions for the $l$s, two of the remaining seven positions for the $a$s, and two of the remaining five positions for the $o$s. Since $l$ appears three times and $a$ and $o$ each appear twice, three of the other six letters in the multiset must not appear at all. Choose which three letters to exclude. Arrange the remaining three letters of the multiset in the remaining three positions. There are
$$binom{10}{3}binom{7}{2}binom{5}{2}binom{6}{3}3!$$
such arrangements.
Total: Since the six cases outlined above are mutually exclusive and exhaustive, the number of distinguishable strings of length $10$ can be found by adding the above cases.
Note: This problem could also be approached using exponential generating functions.
answered Nov 23 at 22:08
N. F. Taussig
43.3k93355
43.3k93355
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3009624%2fpermutations-with-simultaneous-repetition-and-restrictionsubset-length%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
Welcome to MathSE. The answer to your question will depend on the exact composition of the multiset. You may want to consider a concrete example so that you can learn a technique for solving this type of problem. If you choose to do so, please show your own attempt and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site.
– N. F. Taussig
Nov 23 at 12:07
Thanks for you comments. I've tried to use the formula code and also added an example input to discuss.
– Erik
Nov 23 at 14:54
It's best not to call your "set" a "set", since it is a multiset, and also not to call your "permutations" "permutations", since they may contain fewer than all elements of the multiset. So you are looking for the number of $k$-tuples of letters, where each letter appears at most a given number of times (namely, how often it appears in the original "set"). You can get an alternating-sign-sum expression for the answer using Inclusion-Exclusion (by first counting arbitrary $k$-tuples, and then excluding the ones where a letter appears too frequently), ...
– darij grinberg
Nov 23 at 18:26
... but I don't think there is anything like a closed form for this problem.
– darij grinberg
Nov 23 at 18:27
Ok, I think I get the gist of your comment. Sorry for the naming, only used what I understood from all I've read to reach the point were I wrote my question; that permutations with duplicate items was called permutations with repetition, and the k-tuple was called permutation with item restriction. Apparently I am mistaken.
– Erik
Nov 23 at 19:42