Finding total unique combination for character deletion in a string
$begingroup$
Is there any general formula to determine a unique combination for character deletion in a string comprised of 4 characters? Let's say that I have $str1 = {ABCDA}$ and I want to delete from one up to four position in that string. Thus all the combination for deletion up to four position of str1 would be:
$$
s(1, str1) = BCDA, ACDA, ABDA, ABCA, ABCD = 5
$$
$$
s(2, str1) = CDA, BDA, BCA, BCD, ADA, ACA, ACD, ABA, ABD, ABC = 10
$$
$$
s(3, str1) = DA, CA, CD, BA, BD, BC, AA, AD, AC, AB = 10
$$
$$
s(4, str1) = A, D, C, B, A = 5
$$
and gives 30 in total, and only 29 unique strings. In general, the total combination could be solved using the formula $sum_{k=1}^{r} {{n}choose{k}}$. However I could not find a formula to calculate total unique combination from a given string since the relative position of characters determine the total unique combination. Let's say that another 5-character long string is str2 = {AAABC}, then the number of unique sequences will be different:
$$
s(1, str2) = AABC, AABC, AABC, AAAC, AAAB
$$
$$
s(2, str2) = ABC, ABC, AAC, AAB, ABC, AAC, AAB, AAC, AAB, AAA
$$
$$
s(3, str2) = BCA, AC, AB, AC, AB, AA, AC, AB, AA, AA
$$
$$
s(4, str3) = C, B, A, A, A
$$
The total combinations is still 30, but the unique combinations reduce to 14. Is there any way to count such unique combination for any string with length n composed of four characters (A, B, C, and D)?
combinatorics
asked Jan 10 at 7:21
Vic BrownVic Brown
213
$endgroup$
add a comment |
$begingroup$
Is there any general formula to determine a unique combination for character deletion in a string comprised of 4 characters? Let's say that I have $str1 = {ABCDA}$ and I want to delete from one up to four position in that string. Thus all the combination for deletion up to four position of str1 would be:
$$
s(1, str1) = BCDA, ACDA, ABDA, ABCA, ABCD = 5
$$
$$
s(2, str1) = CDA, BDA, BCA, BCD, ADA, ACA, ACD, ABA, ABD, ABC = 10
$$
$$
s(3, str1) = DA, CA, CD, BA, BD, BC, AA, AD, AC, AB = 10
$$
$$
s(4, str1) = A, D, C, B, A = 5
$$
and gives 30 in total, and only 29 unique strings. In general, the total combination could be solved using the formula $sum_{k=1}^{r} {{n}choose{k}}$. However I could not find a formula to calculate total unique combination from a given string since the relative position of characters determine the total unique combination. Let's say that another 5-character long string is str2 = {AAABC}, then the number of unique sequences will be different:
$$
s(1, str2) = AABC, AABC, AABC, AAAC, AAAB
$$
$$
s(2, str2) = ABC, ABC, AAC, AAB, ABC, AAC, AAB, AAC, AAB, AAA
$$
$$
s(3, str2) = BCA, AC, AB, AC, AB, AA, AC, AB, AA, AA
$$
$$
s(4, str3) = C, B, A, A, A
$$
The total combinations is still 30, but the unique combinations reduce to 14. Is there any way to count such unique combination for any string with length n composed of four characters (A, B, C, and D)?
combinatorics
asked Jan 10 at 7:21
Vic BrownVic Brown
213
$endgroup$
$begingroup$
Answered on stackoverflow: stackoverflow.com/questions/50702755/…, stackoverflow.com/questions/5151483/….
$endgroup$
– Yuval Filmus
Jan 11 at 9:08
$begingroup$
Thanks for the above link @YuvalFilmus. However, I need the mathematical formula which could be applied to a general problem of string deletion.
$endgroup$
– Vic Brown
Jan 14 at 2:23
add a comment |
$begingroup$
Is there any general formula to determine a unique combination for character deletion in a string comprised of 4 characters? Let's say that I have $str1 = {ABCDA}$ and I want to delete from one up to four position in that string. Thus all the combination for deletion up to four position of str1 would be:
$$
s(1, str1) = BCDA, ACDA, ABDA, ABCA, ABCD = 5
$$
$$
s(2, str1) = CDA, BDA, BCA, BCD, ADA, ACA, ACD, ABA, ABD, ABC = 10
$$
$$
s(3, str1) = DA, CA, CD, BA, BD, BC, AA, AD, AC, AB = 10
$$
$$
s(4, str1) = A, D, C, B, A = 5
$$
and gives 30 in total, and only 29 unique strings. In general, the total combination could be solved using the formula $sum_{k=1}^{r} {{n}choose{k}}$. However I could not find a formula to calculate total unique combination from a given string since the relative position of characters determine the total unique combination. Let's say that another 5-character long string is str2 = {AAABC}, then the number of unique sequences will be different:
$$
s(1, str2) = AABC, AABC, AABC, AAAC, AAAB
$$
$$
s(2, str2) = ABC, ABC, AAC, AAB, ABC, AAC, AAB, AAC, AAB, AAA
$$
$$
s(3, str2) = BCA, AC, AB, AC, AB, AA, AC, AB, AA, AA
$$
$$
s(4, str3) = C, B, A, A, A
$$
The total combinations is still 30, but the unique combinations reduce to 14. Is there any way to count such unique combination for any string with length n composed of four characters (A, B, C, and D)?
combinatorics
asked Jan 10 at 7:21
Vic BrownVic Brown
213
$endgroup$
Is there any general formula to determine a unique combination for character deletion in a string comprised of 4 characters? Let's say that I have $str1 = {ABCDA}$ and I want to delete from one up to four position in that string. Thus all the combination for deletion up to four position of str1 would be:
$$
s(1, str1) = BCDA, ACDA, ABDA, ABCA, ABCD = 5
$$
$$
s(2, str1) = CDA, BDA, BCA, BCD, ADA, ACA, ACD, ABA, ABD, ABC = 10
$$
$$
s(3, str1) = DA, CA, CD, BA, BD, BC, AA, AD, AC, AB = 10
$$
$$
s(4, str1) = A, D, C, B, A = 5
$$
and gives 30 in total, and only 29 unique strings. In general, the total combination could be solved using the formula $sum_{k=1}^{r} {{n}choose{k}}$. However I could not find a formula to calculate total unique combination from a given string since the relative position of characters determine the total unique combination. Let's say that another 5-character long string is str2 = {AAABC}, then the number of unique sequences will be different:
$$
s(1, str2) = AABC, AABC, AABC, AAAC, AAAB
$$
$$
s(2, str2) = ABC, ABC, AAC, AAB, ABC, AAC, AAB, AAC, AAB, AAA
$$
$$
s(3, str2) = BCA, AC, AB, AC, AB, AA, AC, AB, AA, AA
$$
$$
s(4, str3) = C, B, A, A, A
$$
The total combinations is still 30, but the unique combinations reduce to 14. Is there any way to count such unique combination for any string with length n composed of four characters (A, B, C, and D)?
combinatorics
combinatorics
asked Jan 10 at 7:21
Vic BrownVic Brown
213
asked Jan 10 at 7:21
Vic BrownVic Brown
213
asked Jan 10 at 7:21
Vic BrownVic Brown
213
asked Jan 10 at 7:21
Vic BrownVic Brown
213
asked Jan 10 at 7:21
Vic BrownVic Brown
213
213
$begingroup$
Answered on stackoverflow: stackoverflow.com/questions/50702755/…, stackoverflow.com/questions/5151483/….
$endgroup$
– Yuval Filmus
Jan 11 at 9:08
$begingroup$
Thanks for the above link @YuvalFilmus. However, I need the mathematical formula which could be applied to a general problem of string deletion.
$endgroup$
– Vic Brown
Jan 14 at 2:23
add a comment |
$begingroup$
Answered on stackoverflow: stackoverflow.com/questions/50702755/…, stackoverflow.com/questions/5151483/….
$endgroup$
– Yuval Filmus
Jan 11 at 9:08
$begingroup$
Thanks for the above link @YuvalFilmus. However, I need the mathematical formula which could be applied to a general problem of string deletion.
$endgroup$
– Vic Brown
Jan 14 at 2:23
$begingroup$
Answered on stackoverflow: stackoverflow.com/questions/50702755/…, stackoverflow.com/questions/5151483/….
$endgroup$
– Yuval Filmus
Jan 11 at 9:08
$begingroup$
Answered on stackoverflow: stackoverflow.com/questions/50702755/…, stackoverflow.com/questions/5151483/….
$endgroup$
– Yuval Filmus
Jan 11 at 9:08
$begingroup$
Thanks for the above link @YuvalFilmus. However, I need the mathematical formula which could be applied to a general problem of string deletion.
$endgroup$
– Vic Brown
Jan 14 at 2:23
$begingroup$
Thanks for the above link @YuvalFilmus. However, I need the mathematical formula which could be applied to a general problem of string deletion.
$endgroup$
– Vic Brown
Jan 14 at 2:23
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I found a hint for calculating unique combination for one character deletion such that the unique combination is equal to total combination as long as there is no consecutive character repeat:
$$
s(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
$$
s_{U}(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
When repeats of characters occur, then the unique combination will be reduced:
$$
s(1, AABCD) = ABCD, ABCD, AACD, AABD, AABC
$$
$$
s_{U}(1, AABCD) = ABCD, AABD, AACD, AABC
$$
from this observation I conclude that the unique combination of any string of length n depends on the occurrence of runs, such that:
$$
s_{U}(1, AABCD) = s(1, AABCD) - (rtimes d)
$$
$$
= {{5}choose{1}} - (1 . 1) = 4
$$
I find it also true for string containing multiple runs, such as AAABBCD, where: $s_{U} = {{7}choose{1}} - ((1times 2)+(1times 1)) = 4$. However I find difficulties when I try the same formula for 2, 3, or four character deletion. My hypothesis is that the unique combination can be obtained by subtracting the total combination with some factors. I presumed that these factors involve the occurrence of repeats.
Any help for this problem?
answered Jan 14 at 3:02
Vic BrownVic Brown
213
$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%2f3068344%2ffinding-total-unique-combination-for-character-deletion-in-a-string%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$
I found a hint for calculating unique combination for one character deletion such that the unique combination is equal to total combination as long as there is no consecutive character repeat:
$$
s(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
$$
s_{U}(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
When repeats of characters occur, then the unique combination will be reduced:
$$
s(1, AABCD) = ABCD, ABCD, AACD, AABD, AABC
$$
$$
s_{U}(1, AABCD) = ABCD, AABD, AACD, AABC
$$
from this observation I conclude that the unique combination of any string of length n depends on the occurrence of runs, such that:
$$
s_{U}(1, AABCD) = s(1, AABCD) - (rtimes d)
$$
$$
= {{5}choose{1}} - (1 . 1) = 4
$$
I find it also true for string containing multiple runs, such as AAABBCD, where: $s_{U} = {{7}choose{1}} - ((1times 2)+(1times 1)) = 4$. However I find difficulties when I try the same formula for 2, 3, or four character deletion. My hypothesis is that the unique combination can be obtained by subtracting the total combination with some factors. I presumed that these factors involve the occurrence of repeats.
Any help for this problem?
answered Jan 14 at 3:02
Vic BrownVic Brown
213
$endgroup$
add a comment |
$begingroup$
I found a hint for calculating unique combination for one character deletion such that the unique combination is equal to total combination as long as there is no consecutive character repeat:
$$
s(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
$$
s_{U}(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
When repeats of characters occur, then the unique combination will be reduced:
$$
s(1, AABCD) = ABCD, ABCD, AACD, AABD, AABC
$$
$$
s_{U}(1, AABCD) = ABCD, AABD, AACD, AABC
$$
from this observation I conclude that the unique combination of any string of length n depends on the occurrence of runs, such that:
$$
s_{U}(1, AABCD) = s(1, AABCD) - (rtimes d)
$$
$$
= {{5}choose{1}} - (1 . 1) = 4
$$
I find it also true for string containing multiple runs, such as AAABBCD, where: $s_{U} = {{7}choose{1}} - ((1times 2)+(1times 1)) = 4$. However I find difficulties when I try the same formula for 2, 3, or four character deletion. My hypothesis is that the unique combination can be obtained by subtracting the total combination with some factors. I presumed that these factors involve the occurrence of repeats.
Any help for this problem?
answered Jan 14 at 3:02
Vic BrownVic Brown
213
$endgroup$
add a comment |
$begingroup$
I found a hint for calculating unique combination for one character deletion such that the unique combination is equal to total combination as long as there is no consecutive character repeat:
$$
s(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
$$
s_{U}(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
When repeats of characters occur, then the unique combination will be reduced:
$$
s(1, AABCD) = ABCD, ABCD, AACD, AABD, AABC
$$
$$
s_{U}(1, AABCD) = ABCD, AABD, AACD, AABC
$$
from this observation I conclude that the unique combination of any string of length n depends on the occurrence of runs, such that:
$$
s_{U}(1, AABCD) = s(1, AABCD) - (rtimes d)
$$
$$
= {{5}choose{1}} - (1 . 1) = 4
$$
I find it also true for string containing multiple runs, such as AAABBCD, where: $s_{U} = {{7}choose{1}} - ((1times 2)+(1times 1)) = 4$. However I find difficulties when I try the same formula for 2, 3, or four character deletion. My hypothesis is that the unique combination can be obtained by subtracting the total combination with some factors. I presumed that these factors involve the occurrence of repeats.
Any help for this problem?
answered Jan 14 at 3:02
Vic BrownVic Brown
213
$endgroup$
I found a hint for calculating unique combination for one character deletion such that the unique combination is equal to total combination as long as there is no consecutive character repeat:
$$
s(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
$$
s_{U}(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
When repeats of characters occur, then the unique combination will be reduced:
$$
s(1, AABCD) = ABCD, ABCD, AACD, AABD, AABC
$$
$$
s_{U}(1, AABCD) = ABCD, AABD, AACD, AABC
$$
from this observation I conclude that the unique combination of any string of length n depends on the occurrence of runs, such that:
$$
s_{U}(1, AABCD) = s(1, AABCD) - (rtimes d)
$$
$$
= {{5}choose{1}} - (1 . 1) = 4
$$
I find it also true for string containing multiple runs, such as AAABBCD, where: $s_{U} = {{7}choose{1}} - ((1times 2)+(1times 1)) = 4$. However I find difficulties when I try the same formula for 2, 3, or four character deletion. My hypothesis is that the unique combination can be obtained by subtracting the total combination with some factors. I presumed that these factors involve the occurrence of repeats.
Any help for this problem?
answered Jan 14 at 3:02
Vic BrownVic Brown
213
answered Jan 14 at 3:02
Vic BrownVic Brown
213
answered Jan 14 at 3:02
Vic BrownVic Brown
213
answered Jan 14 at 3:02
Vic BrownVic Brown
213
213
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%2f3068344%2ffinding-total-unique-combination-for-character-deletion-in-a-string%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
$begingroup$
Answered on stackoverflow: stackoverflow.com/questions/50702755/…, stackoverflow.com/questions/5151483/….
$endgroup$
– Yuval Filmus
Jan 11 at 9:08
$begingroup$
Thanks for the above link @YuvalFilmus. However, I need the mathematical formula which could be applied to a general problem of string deletion.
$endgroup$
– Vic Brown
Jan 14 at 2:23