Mixing
How to get number of all unique permutations of lengh k out of string of length n?
$begingroup$
Suppose we are given string s = "aba" and k = 2. Then the permutations we can make using string characters are
aa ab ba
So the answer is 3.
If s = "aabb" and k = 2 then possible permutations are
aa ab ba bb
So answer is 4.
We can use a character only as many as times it is appeared in string or less than that but not more than that.
Is there any formula or some way to find it out quickly?
Note: K is not the number of unique charcters, for eg. s=aabbcdd the value of k may be k=3.
combinatorics permutations
asked Jan 26 at 22:49
Harish kushwahaHarish kushwaha
11
$endgroup$
add a comment |
$begingroup$
Suppose we are given string s = "aba" and k = 2. Then the permutations we can make using string characters are
aa ab ba
So the answer is 3.
If s = "aabb" and k = 2 then possible permutations are
aa ab ba bb
So answer is 4.
We can use a character only as many as times it is appeared in string or less than that but not more than that.
Is there any formula or some way to find it out quickly?
Note: K is not the number of unique charcters, for eg. s=aabbcdd the value of k may be k=3.
combinatorics permutations
asked Jan 26 at 22:49
Harish kushwahaHarish kushwaha
11
$endgroup$
add a comment |
$begingroup$
Suppose we are given string s = "aba" and k = 2. Then the permutations we can make using string characters are
aa ab ba
So the answer is 3.
If s = "aabb" and k = 2 then possible permutations are
aa ab ba bb
So answer is 4.
We can use a character only as many as times it is appeared in string or less than that but not more than that.
Is there any formula or some way to find it out quickly?
Note: K is not the number of unique charcters, for eg. s=aabbcdd the value of k may be k=3.
combinatorics permutations
asked Jan 26 at 22:49
Harish kushwahaHarish kushwaha
11
$endgroup$
Suppose we are given string s = "aba" and k = 2. Then the permutations we can make using string characters are
aa ab ba
So the answer is 3.
If s = "aabb" and k = 2 then possible permutations are
aa ab ba bb
So answer is 4.
We can use a character only as many as times it is appeared in string or less than that but not more than that.
Is there any formula or some way to find it out quickly?
Note: K is not the number of unique charcters, for eg. s=aabbcdd the value of k may be k=3.
combinatorics permutations
combinatorics permutations
asked Jan 26 at 22:49
Harish kushwahaHarish kushwaha
11
asked Jan 26 at 22:49
Harish kushwahaHarish kushwaha
11
edited Jan 26 at 22:56
Harish kushwaha
asked Jan 26 at 22:49
Harish kushwahaHarish kushwaha
11
asked Jan 26 at 22:49
Harish kushwahaHarish kushwaha
11
asked Jan 26 at 22:49
Harish kushwahaHarish kushwaha
11
11
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This isn't particularly useful for a pen-paper approach, but you can use generating functions. Look at the coefficient of $x^k$ in the expansion of
$$k!(1+x+frac{x^2}{2!}+frac{x^3}{3!}+dots + frac{x^a}{a!})(1+x+frac{x^2}{2!}+dots+frac{x^b}{b!})cdots (1+x+dots+frac{x^z}{z!})$$ where $a,b,dots,z$ are the number of occurrences of the letters a,b,...,z respectively in your original string.
In your example of aabbcdd and $k=3$ this would be the coefficient of $x^3$ in the expansion of:
$3!(1+x+frac{x^2}{2})(1+x+frac{x^2}{2})(1+x)(1+x+frac{x^2}{2})$
which comes out to be $51$ after plugging it into a calculator.
Somewhere buried in my answers from the past (on a possibly now deleted question which might be why I can't find it) I know I had taken the time to write out another expression for it using inclusion-exclusion, but that is even worse to try to implement in most scenarios and I do not recommend it.
For small scenarios, you could approach directly via breaking into cases. Looking at the aabbcdd and $k=3$ example again, you have the following two cases:
- All letters used are distinct: pick first, pick second, pick third for $4cdot 3cdot 2 = 24$ outcomes here
- A letter is used twice: pick which was used twice, pick remaining letter, pick location of remaining letter for $3cdot 3cdot 3 = 27$ outcomes here.
Adding gives $24+27=51$ outcomes, same as what was found earlier.
This will get very tedious to do very quickly as numbers get larger however and is not recommended beyond simple examples.
answered Jan 26 at 23:16
JMoravitzJMoravitz
48.8k43988
$endgroup$
$begingroup$
Is there any single line formula to do that?
$endgroup$
– Harish kushwaha
Feb 1 at 17:57
$begingroup$
Any proof or formula can be written in one-line if your paper is large enough and you use small enough font. Even without sarcasm I would consider both of these to be as compact of expressions as you could hope to achieve for this problem. The inclusion-exclusion answer I alluded to is incredibly difficult to parse and would require as much if not more computation as the generating function approach I gave initially. TLDR: this is as good as it gets.
$endgroup$
– JMoravitz
Feb 1 at 18:50
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%2f3088882%2fhow-to-get-number-of-all-unique-permutations-of-lengh-k-out-of-string-of-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
$begingroup$
This isn't particularly useful for a pen-paper approach, but you can use generating functions. Look at the coefficient of $x^k$ in the expansion of
$$k!(1+x+frac{x^2}{2!}+frac{x^3}{3!}+dots + frac{x^a}{a!})(1+x+frac{x^2}{2!}+dots+frac{x^b}{b!})cdots (1+x+dots+frac{x^z}{z!})$$ where $a,b,dots,z$ are the number of occurrences of the letters a,b,...,z respectively in your original string.
In your example of aabbcdd and $k=3$ this would be the coefficient of $x^3$ in the expansion of:
$3!(1+x+frac{x^2}{2})(1+x+frac{x^2}{2})(1+x)(1+x+frac{x^2}{2})$
which comes out to be $51$ after plugging it into a calculator.
Somewhere buried in my answers from the past (on a possibly now deleted question which might be why I can't find it) I know I had taken the time to write out another expression for it using inclusion-exclusion, but that is even worse to try to implement in most scenarios and I do not recommend it.
For small scenarios, you could approach directly via breaking into cases. Looking at the aabbcdd and $k=3$ example again, you have the following two cases:
- All letters used are distinct: pick first, pick second, pick third for $4cdot 3cdot 2 = 24$ outcomes here
- A letter is used twice: pick which was used twice, pick remaining letter, pick location of remaining letter for $3cdot 3cdot 3 = 27$ outcomes here.
Adding gives $24+27=51$ outcomes, same as what was found earlier.
This will get very tedious to do very quickly as numbers get larger however and is not recommended beyond simple examples.
answered Jan 26 at 23:16
JMoravitzJMoravitz
48.8k43988
$endgroup$
$begingroup$
Is there any single line formula to do that?
$endgroup$
– Harish kushwaha
Feb 1 at 17:57
$begingroup$
Any proof or formula can be written in one-line if your paper is large enough and you use small enough font. Even without sarcasm I would consider both of these to be as compact of expressions as you could hope to achieve for this problem. The inclusion-exclusion answer I alluded to is incredibly difficult to parse and would require as much if not more computation as the generating function approach I gave initially. TLDR: this is as good as it gets.
$endgroup$
– JMoravitz
Feb 1 at 18:50
add a comment |
$begingroup$
This isn't particularly useful for a pen-paper approach, but you can use generating functions. Look at the coefficient of $x^k$ in the expansion of
$$k!(1+x+frac{x^2}{2!}+frac{x^3}{3!}+dots + frac{x^a}{a!})(1+x+frac{x^2}{2!}+dots+frac{x^b}{b!})cdots (1+x+dots+frac{x^z}{z!})$$ where $a,b,dots,z$ are the number of occurrences of the letters a,b,...,z respectively in your original string.
In your example of aabbcdd and $k=3$ this would be the coefficient of $x^3$ in the expansion of:
$3!(1+x+frac{x^2}{2})(1+x+frac{x^2}{2})(1+x)(1+x+frac{x^2}{2})$
which comes out to be $51$ after plugging it into a calculator.
Somewhere buried in my answers from the past (on a possibly now deleted question which might be why I can't find it) I know I had taken the time to write out another expression for it using inclusion-exclusion, but that is even worse to try to implement in most scenarios and I do not recommend it.
For small scenarios, you could approach directly via breaking into cases. Looking at the aabbcdd and $k=3$ example again, you have the following two cases:
- All letters used are distinct: pick first, pick second, pick third for $4cdot 3cdot 2 = 24$ outcomes here
- A letter is used twice: pick which was used twice, pick remaining letter, pick location of remaining letter for $3cdot 3cdot 3 = 27$ outcomes here.
Adding gives $24+27=51$ outcomes, same as what was found earlier.
This will get very tedious to do very quickly as numbers get larger however and is not recommended beyond simple examples.
answered Jan 26 at 23:16
JMoravitzJMoravitz
48.8k43988
$endgroup$
$begingroup$
Is there any single line formula to do that?
$endgroup$
– Harish kushwaha
Feb 1 at 17:57
$begingroup$
Any proof or formula can be written in one-line if your paper is large enough and you use small enough font. Even without sarcasm I would consider both of these to be as compact of expressions as you could hope to achieve for this problem. The inclusion-exclusion answer I alluded to is incredibly difficult to parse and would require as much if not more computation as the generating function approach I gave initially. TLDR: this is as good as it gets.
$endgroup$
– JMoravitz
Feb 1 at 18:50
add a comment |
$begingroup$
This isn't particularly useful for a pen-paper approach, but you can use generating functions. Look at the coefficient of $x^k$ in the expansion of
$$k!(1+x+frac{x^2}{2!}+frac{x^3}{3!}+dots + frac{x^a}{a!})(1+x+frac{x^2}{2!}+dots+frac{x^b}{b!})cdots (1+x+dots+frac{x^z}{z!})$$ where $a,b,dots,z$ are the number of occurrences of the letters a,b,...,z respectively in your original string.
In your example of aabbcdd and $k=3$ this would be the coefficient of $x^3$ in the expansion of:
$3!(1+x+frac{x^2}{2})(1+x+frac{x^2}{2})(1+x)(1+x+frac{x^2}{2})$
which comes out to be $51$ after plugging it into a calculator.
Somewhere buried in my answers from the past (on a possibly now deleted question which might be why I can't find it) I know I had taken the time to write out another expression for it using inclusion-exclusion, but that is even worse to try to implement in most scenarios and I do not recommend it.
For small scenarios, you could approach directly via breaking into cases. Looking at the aabbcdd and $k=3$ example again, you have the following two cases:
- All letters used are distinct: pick first, pick second, pick third for $4cdot 3cdot 2 = 24$ outcomes here
- A letter is used twice: pick which was used twice, pick remaining letter, pick location of remaining letter for $3cdot 3cdot 3 = 27$ outcomes here.
Adding gives $24+27=51$ outcomes, same as what was found earlier.
This will get very tedious to do very quickly as numbers get larger however and is not recommended beyond simple examples.
answered Jan 26 at 23:16
JMoravitzJMoravitz
48.8k43988
$endgroup$
This isn't particularly useful for a pen-paper approach, but you can use generating functions. Look at the coefficient of $x^k$ in the expansion of
$$k!(1+x+frac{x^2}{2!}+frac{x^3}{3!}+dots + frac{x^a}{a!})(1+x+frac{x^2}{2!}+dots+frac{x^b}{b!})cdots (1+x+dots+frac{x^z}{z!})$$ where $a,b,dots,z$ are the number of occurrences of the letters a,b,...,z respectively in your original string.
In your example of aabbcdd and $k=3$ this would be the coefficient of $x^3$ in the expansion of:
$3!(1+x+frac{x^2}{2})(1+x+frac{x^2}{2})(1+x)(1+x+frac{x^2}{2})$
which comes out to be $51$ after plugging it into a calculator.
Somewhere buried in my answers from the past (on a possibly now deleted question which might be why I can't find it) I know I had taken the time to write out another expression for it using inclusion-exclusion, but that is even worse to try to implement in most scenarios and I do not recommend it.
For small scenarios, you could approach directly via breaking into cases. Looking at the aabbcdd and $k=3$ example again, you have the following two cases:
- All letters used are distinct: pick first, pick second, pick third for $4cdot 3cdot 2 = 24$ outcomes here
- A letter is used twice: pick which was used twice, pick remaining letter, pick location of remaining letter for $3cdot 3cdot 3 = 27$ outcomes here.
Adding gives $24+27=51$ outcomes, same as what was found earlier.
This will get very tedious to do very quickly as numbers get larger however and is not recommended beyond simple examples.
answered Jan 26 at 23:16
JMoravitzJMoravitz
48.8k43988
edited Jan 26 at 23:29
answered Jan 26 at 23:16
JMoravitzJMoravitz
48.8k43988
answered Jan 26 at 23:16
JMoravitzJMoravitz
48.8k43988
answered Jan 26 at 23:16
JMoravitzJMoravitz
48.8k43988
48.8k43988
$begingroup$
Is there any single line formula to do that?
$endgroup$
– Harish kushwaha
Feb 1 at 17:57
$begingroup$
Any proof or formula can be written in one-line if your paper is large enough and you use small enough font. Even without sarcasm I would consider both of these to be as compact of expressions as you could hope to achieve for this problem. The inclusion-exclusion answer I alluded to is incredibly difficult to parse and would require as much if not more computation as the generating function approach I gave initially. TLDR: this is as good as it gets.
$endgroup$
– JMoravitz
Feb 1 at 18:50
add a comment |
$begingroup$
Is there any single line formula to do that?
$endgroup$
– Harish kushwaha
Feb 1 at 17:57
$begingroup$
Any proof or formula can be written in one-line if your paper is large enough and you use small enough font. Even without sarcasm I would consider both of these to be as compact of expressions as you could hope to achieve for this problem. The inclusion-exclusion answer I alluded to is incredibly difficult to parse and would require as much if not more computation as the generating function approach I gave initially. TLDR: this is as good as it gets.
$endgroup$
– JMoravitz
Feb 1 at 18:50
$begingroup$
Is there any single line formula to do that?
$endgroup$
– Harish kushwaha
Feb 1 at 17:57
$begingroup$
Is there any single line formula to do that?
$endgroup$
– Harish kushwaha
Feb 1 at 17:57
$begingroup$
Any proof or formula can be written in one-line if your paper is large enough and you use small enough font. Even without sarcasm I would consider both of these to be as compact of expressions as you could hope to achieve for this problem. The inclusion-exclusion answer I alluded to is incredibly difficult to parse and would require as much if not more computation as the generating function approach I gave initially. TLDR: this is as good as it gets.
$endgroup$
– JMoravitz
Feb 1 at 18:50
$begingroup$
Any proof or formula can be written in one-line if your paper is large enough and you use small enough font. Even without sarcasm I would consider both of these to be as compact of expressions as you could hope to achieve for this problem. The inclusion-exclusion answer I alluded to is incredibly difficult to parse and would require as much if not more computation as the generating function approach I gave initially. TLDR: this is as good as it gets.
$endgroup$
– JMoravitz
Feb 1 at 18:50
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%2f3088882%2fhow-to-get-number-of-all-unique-permutations-of-lengh-k-out-of-string-of-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
