Find the number of words recursively such that there is no palindromic suffix
$begingroup$
Given a set of distinct characters ${a_1, a_2, cdots , a_S}$ and a number $N$, find the number of words of length $N$ that can be formed using these letters (repetition allowed) such that there is no palindromic suffix in the word. In other words find the number of words such that for any $1<k leq N$ the last $k$ letters of the word shouldn't form a palindrome.
This is certainly recursion.
My initial idea was to consider last $k$ integers (for $k>1$) and make it a palindrome and ensure that any $j>k$ do not form a palindrome. Finally the answer would be $S^N - text{sum of our considerations}$.
But this way out seems to be quite tough.
combinatorics recursion formal-languages palindrome
edited Dec 9 '18 at 6:35
Jack D'Aurizio
289k33281660
asked Dec 9 '18 at 4:45
MathejuniorMathejunior
1,585423
$endgroup$
add a comment |
$begingroup$
Given a set of distinct characters ${a_1, a_2, cdots , a_S}$ and a number $N$, find the number of words of length $N$ that can be formed using these letters (repetition allowed) such that there is no palindromic suffix in the word. In other words find the number of words such that for any $1<k leq N$ the last $k$ letters of the word shouldn't form a palindrome.
This is certainly recursion.
My initial idea was to consider last $k$ integers (for $k>1$) and make it a palindrome and ensure that any $j>k$ do not form a palindrome. Finally the answer would be $S^N - text{sum of our considerations}$.
But this way out seems to be quite tough.
combinatorics recursion formal-languages palindrome
edited Dec 9 '18 at 6:35
Jack D'Aurizio
289k33281660
asked Dec 9 '18 at 4:45
MathejuniorMathejunior
1,585423
$endgroup$
$begingroup$
I believe the only non-trivial part is to manage the words with a palindromic suffix which are also words with a palindromic suffix of different length: for instance $7010010010$ has three palindromic suffixes, namely $010,010010,010010010$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 4:59
$begingroup$
Also, single characters are, strictly speaking, palindromic, so I guess we want to count the number of words with a maximal palindromic suffix of length $geq 2$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 5:03
1
$begingroup$
@JackD'Aurizio yes, see I wrote $1< k leq N$ which conveys the fact that $Ngeq 2$.
$endgroup$
– Mathejunior
Dec 9 '18 at 5:06
add a comment |
$begingroup$
Given a set of distinct characters ${a_1, a_2, cdots , a_S}$ and a number $N$, find the number of words of length $N$ that can be formed using these letters (repetition allowed) such that there is no palindromic suffix in the word. In other words find the number of words such that for any $1<k leq N$ the last $k$ letters of the word shouldn't form a palindrome.
This is certainly recursion.
My initial idea was to consider last $k$ integers (for $k>1$) and make it a palindrome and ensure that any $j>k$ do not form a palindrome. Finally the answer would be $S^N - text{sum of our considerations}$.
But this way out seems to be quite tough.
combinatorics recursion formal-languages palindrome
edited Dec 9 '18 at 6:35
Jack D'Aurizio
289k33281660
asked Dec 9 '18 at 4:45
MathejuniorMathejunior
1,585423
$endgroup$
Given a set of distinct characters ${a_1, a_2, cdots , a_S}$ and a number $N$, find the number of words of length $N$ that can be formed using these letters (repetition allowed) such that there is no palindromic suffix in the word. In other words find the number of words such that for any $1<k leq N$ the last $k$ letters of the word shouldn't form a palindrome.
This is certainly recursion.
My initial idea was to consider last $k$ integers (for $k>1$) and make it a palindrome and ensure that any $j>k$ do not form a palindrome. Finally the answer would be $S^N - text{sum of our considerations}$.
But this way out seems to be quite tough.
combinatorics recursion formal-languages palindrome
combinatorics recursion formal-languages palindrome
edited Dec 9 '18 at 6:35
Jack D'Aurizio
289k33281660
asked Dec 9 '18 at 4:45
MathejuniorMathejunior
1,585423
edited Dec 9 '18 at 6:35
Jack D'Aurizio
289k33281660
asked Dec 9 '18 at 4:45
MathejuniorMathejunior
1,585423
edited Dec 9 '18 at 6:35
Jack D'Aurizio
289k33281660
edited Dec 9 '18 at 6:35
Jack D'Aurizio
289k33281660
edited Dec 9 '18 at 6:35
Jack D'Aurizio
289k33281660
289k33281660
asked Dec 9 '18 at 4:45
MathejuniorMathejunior
1,585423
asked Dec 9 '18 at 4:45
MathejuniorMathejunior
1,585423
asked Dec 9 '18 at 4:45
MathejuniorMathejunior
1,585423
1,585423
$begingroup$
I believe the only non-trivial part is to manage the words with a palindromic suffix which are also words with a palindromic suffix of different length: for instance $7010010010$ has three palindromic suffixes, namely $010,010010,010010010$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 4:59
$begingroup$
Also, single characters are, strictly speaking, palindromic, so I guess we want to count the number of words with a maximal palindromic suffix of length $geq 2$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 5:03
1
$begingroup$
@JackD'Aurizio yes, see I wrote $1< k leq N$ which conveys the fact that $Ngeq 2$.
$endgroup$
– Mathejunior
Dec 9 '18 at 5:06
add a comment |
$begingroup$
I believe the only non-trivial part is to manage the words with a palindromic suffix which are also words with a palindromic suffix of different length: for instance $7010010010$ has three palindromic suffixes, namely $010,010010,010010010$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 4:59
$begingroup$
Also, single characters are, strictly speaking, palindromic, so I guess we want to count the number of words with a maximal palindromic suffix of length $geq 2$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 5:03
1
$begingroup$
@JackD'Aurizio yes, see I wrote $1< k leq N$ which conveys the fact that $Ngeq 2$.
$endgroup$
– Mathejunior
Dec 9 '18 at 5:06
$begingroup$
I believe the only non-trivial part is to manage the words with a palindromic suffix which are also words with a palindromic suffix of different length: for instance $7010010010$ has three palindromic suffixes, namely $010,010010,010010010$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 4:59
$begingroup$
I believe the only non-trivial part is to manage the words with a palindromic suffix which are also words with a palindromic suffix of different length: for instance $7010010010$ has three palindromic suffixes, namely $010,010010,010010010$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 4:59
$begingroup$
Also, single characters are, strictly speaking, palindromic, so I guess we want to count the number of words with a maximal palindromic suffix of length $geq 2$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 5:03
$begingroup$
Also, single characters are, strictly speaking, palindromic, so I guess we want to count the number of words with a maximal palindromic suffix of length $geq 2$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 5:03
1
1
$begingroup$
@JackD'Aurizio yes, see I wrote $1< k leq N$ which conveys the fact that $Ngeq 2$.
$endgroup$
– Mathejunior
Dec 9 '18 at 5:06
$begingroup$
@JackD'Aurizio yes, see I wrote $1< k leq N$ which conveys the fact that $Ngeq 2$.
$endgroup$
– Mathejunior
Dec 9 '18 at 5:06
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $overline{q}$ denote the reversal of a string $q$. Given a word $w$ with a palindromic suffix, we may define $text{LPS}(w)$ as the longest palindromic suffix. If $text{LPS}(w)$ is not periodic, it has the structure $overline{q}q$ or the structure $overline{q}q$ ($|q|geq 2$) with one of the central characters being removed (let us denote this as $overline{q}q^{*}$), where $q$ is an aperiodic word. From the theory of necklace polynomials / Moebius inversion we know that the number of aperiodic words with length $ell$ over an alphabet with $S$ symbols is given by
$$A_{ell,S}=sum_{dmid ell}muleft(frac{ell}{d}right)S^d $$
hence we have an explicit way of counting the strings with a $text{LPS}$, according to it being a $(overline{q}q)^m$ or a $(overline{q}q^*)^m$. On the other hand we may also consider that
- If $text{LPS}(w)$ has odd length, by removing or duplicating the central character of the $text{LPS}$ we get a string with a palindromic suffix whose length is $|w|mp 1$;
- If $text{LPS}(w)$ has even length, by inserting a character in the middle of such $text{LPS}$ the string $w$ with a periodic suffix is mapped into a string with a periodic suffix and length $|w|+1$.
This leads to a much simpler recursion for counting the strings with an $text{LPS}$:
$$ left{begin{array}{rcl}P_ell &=& S^{ell-2}(S-1)+S P_{ell-2}\
D_ell &=& S P_{ell-1}end{array}right.$$
If my computation are correct, we have that the strings with length $n$ and a palindromic suffix are $ 2 S^{n-1} - S^{lfloor n/2rfloor}$.
answered Dec 9 '18 at 5:57
Jack D'AurizioJack D'Aurizio
289k33281660
$endgroup$
$begingroup$
Okay, can you please tell me what you meant by $D_l$ and $P_l$? Thank you
$endgroup$
– Mathejunior
Dec 9 '18 at 10:27
$begingroup$
@Mathejunior: $P_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of even length, $D_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of odd length.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 10:29
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%2f3032023%2ffind-the-number-of-words-recursively-such-that-there-is-no-palindromic-suffix%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$
Let $overline{q}$ denote the reversal of a string $q$. Given a word $w$ with a palindromic suffix, we may define $text{LPS}(w)$ as the longest palindromic suffix. If $text{LPS}(w)$ is not periodic, it has the structure $overline{q}q$ or the structure $overline{q}q$ ($|q|geq 2$) with one of the central characters being removed (let us denote this as $overline{q}q^{*}$), where $q$ is an aperiodic word. From the theory of necklace polynomials / Moebius inversion we know that the number of aperiodic words with length $ell$ over an alphabet with $S$ symbols is given by
$$A_{ell,S}=sum_{dmid ell}muleft(frac{ell}{d}right)S^d $$
hence we have an explicit way of counting the strings with a $text{LPS}$, according to it being a $(overline{q}q)^m$ or a $(overline{q}q^*)^m$. On the other hand we may also consider that
- If $text{LPS}(w)$ has odd length, by removing or duplicating the central character of the $text{LPS}$ we get a string with a palindromic suffix whose length is $|w|mp 1$;
- If $text{LPS}(w)$ has even length, by inserting a character in the middle of such $text{LPS}$ the string $w$ with a periodic suffix is mapped into a string with a periodic suffix and length $|w|+1$.
This leads to a much simpler recursion for counting the strings with an $text{LPS}$:
$$ left{begin{array}{rcl}P_ell &=& S^{ell-2}(S-1)+S P_{ell-2}\
D_ell &=& S P_{ell-1}end{array}right.$$
If my computation are correct, we have that the strings with length $n$ and a palindromic suffix are $ 2 S^{n-1} - S^{lfloor n/2rfloor}$.
answered Dec 9 '18 at 5:57
Jack D'AurizioJack D'Aurizio
289k33281660
$endgroup$
$begingroup$
Okay, can you please tell me what you meant by $D_l$ and $P_l$? Thank you
$endgroup$
– Mathejunior
Dec 9 '18 at 10:27
$begingroup$
@Mathejunior: $P_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of even length, $D_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of odd length.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 10:29
add a comment |
$begingroup$
Let $overline{q}$ denote the reversal of a string $q$. Given a word $w$ with a palindromic suffix, we may define $text{LPS}(w)$ as the longest palindromic suffix. If $text{LPS}(w)$ is not periodic, it has the structure $overline{q}q$ or the structure $overline{q}q$ ($|q|geq 2$) with one of the central characters being removed (let us denote this as $overline{q}q^{*}$), where $q$ is an aperiodic word. From the theory of necklace polynomials / Moebius inversion we know that the number of aperiodic words with length $ell$ over an alphabet with $S$ symbols is given by
$$A_{ell,S}=sum_{dmid ell}muleft(frac{ell}{d}right)S^d $$
hence we have an explicit way of counting the strings with a $text{LPS}$, according to it being a $(overline{q}q)^m$ or a $(overline{q}q^*)^m$. On the other hand we may also consider that
- If $text{LPS}(w)$ has odd length, by removing or duplicating the central character of the $text{LPS}$ we get a string with a palindromic suffix whose length is $|w|mp 1$;
- If $text{LPS}(w)$ has even length, by inserting a character in the middle of such $text{LPS}$ the string $w$ with a periodic suffix is mapped into a string with a periodic suffix and length $|w|+1$.
This leads to a much simpler recursion for counting the strings with an $text{LPS}$:
$$ left{begin{array}{rcl}P_ell &=& S^{ell-2}(S-1)+S P_{ell-2}\
D_ell &=& S P_{ell-1}end{array}right.$$
If my computation are correct, we have that the strings with length $n$ and a palindromic suffix are $ 2 S^{n-1} - S^{lfloor n/2rfloor}$.
answered Dec 9 '18 at 5:57
Jack D'AurizioJack D'Aurizio
289k33281660
$endgroup$
$begingroup$
Okay, can you please tell me what you meant by $D_l$ and $P_l$? Thank you
$endgroup$
– Mathejunior
Dec 9 '18 at 10:27
$begingroup$
@Mathejunior: $P_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of even length, $D_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of odd length.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 10:29
add a comment |
$begingroup$
Let $overline{q}$ denote the reversal of a string $q$. Given a word $w$ with a palindromic suffix, we may define $text{LPS}(w)$ as the longest palindromic suffix. If $text{LPS}(w)$ is not periodic, it has the structure $overline{q}q$ or the structure $overline{q}q$ ($|q|geq 2$) with one of the central characters being removed (let us denote this as $overline{q}q^{*}$), where $q$ is an aperiodic word. From the theory of necklace polynomials / Moebius inversion we know that the number of aperiodic words with length $ell$ over an alphabet with $S$ symbols is given by
$$A_{ell,S}=sum_{dmid ell}muleft(frac{ell}{d}right)S^d $$
hence we have an explicit way of counting the strings with a $text{LPS}$, according to it being a $(overline{q}q)^m$ or a $(overline{q}q^*)^m$. On the other hand we may also consider that
- If $text{LPS}(w)$ has odd length, by removing or duplicating the central character of the $text{LPS}$ we get a string with a palindromic suffix whose length is $|w|mp 1$;
- If $text{LPS}(w)$ has even length, by inserting a character in the middle of such $text{LPS}$ the string $w$ with a periodic suffix is mapped into a string with a periodic suffix and length $|w|+1$.
This leads to a much simpler recursion for counting the strings with an $text{LPS}$:
$$ left{begin{array}{rcl}P_ell &=& S^{ell-2}(S-1)+S P_{ell-2}\
D_ell &=& S P_{ell-1}end{array}right.$$
If my computation are correct, we have that the strings with length $n$ and a palindromic suffix are $ 2 S^{n-1} - S^{lfloor n/2rfloor}$.
answered Dec 9 '18 at 5:57
Jack D'AurizioJack D'Aurizio
289k33281660
$endgroup$
Let $overline{q}$ denote the reversal of a string $q$. Given a word $w$ with a palindromic suffix, we may define $text{LPS}(w)$ as the longest palindromic suffix. If $text{LPS}(w)$ is not periodic, it has the structure $overline{q}q$ or the structure $overline{q}q$ ($|q|geq 2$) with one of the central characters being removed (let us denote this as $overline{q}q^{*}$), where $q$ is an aperiodic word. From the theory of necklace polynomials / Moebius inversion we know that the number of aperiodic words with length $ell$ over an alphabet with $S$ symbols is given by
$$A_{ell,S}=sum_{dmid ell}muleft(frac{ell}{d}right)S^d $$
hence we have an explicit way of counting the strings with a $text{LPS}$, according to it being a $(overline{q}q)^m$ or a $(overline{q}q^*)^m$. On the other hand we may also consider that
- If $text{LPS}(w)$ has odd length, by removing or duplicating the central character of the $text{LPS}$ we get a string with a palindromic suffix whose length is $|w|mp 1$;
- If $text{LPS}(w)$ has even length, by inserting a character in the middle of such $text{LPS}$ the string $w$ with a periodic suffix is mapped into a string with a periodic suffix and length $|w|+1$.
This leads to a much simpler recursion for counting the strings with an $text{LPS}$:
$$ left{begin{array}{rcl}P_ell &=& S^{ell-2}(S-1)+S P_{ell-2}\
D_ell &=& S P_{ell-1}end{array}right.$$
If my computation are correct, we have that the strings with length $n$ and a palindromic suffix are $ 2 S^{n-1} - S^{lfloor n/2rfloor}$.
answered Dec 9 '18 at 5:57
Jack D'AurizioJack D'Aurizio
289k33281660
edited Dec 9 '18 at 6:30
answered Dec 9 '18 at 5:57
Jack D'AurizioJack D'Aurizio
289k33281660
answered Dec 9 '18 at 5:57
Jack D'AurizioJack D'Aurizio
289k33281660
answered Dec 9 '18 at 5:57
Jack D'AurizioJack D'Aurizio
289k33281660
289k33281660
$begingroup$
Okay, can you please tell me what you meant by $D_l$ and $P_l$? Thank you
$endgroup$
– Mathejunior
Dec 9 '18 at 10:27
$begingroup$
@Mathejunior: $P_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of even length, $D_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of odd length.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 10:29
add a comment |
$begingroup$
Okay, can you please tell me what you meant by $D_l$ and $P_l$? Thank you
$endgroup$
– Mathejunior
Dec 9 '18 at 10:27
$begingroup$
@Mathejunior: $P_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of even length, $D_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of odd length.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 10:29
$begingroup$
Okay, can you please tell me what you meant by $D_l$ and $P_l$? Thank you
$endgroup$
– Mathejunior
Dec 9 '18 at 10:27
$begingroup$
Okay, can you please tell me what you meant by $D_l$ and $P_l$? Thank you
$endgroup$
– Mathejunior
Dec 9 '18 at 10:27
$begingroup$
@Mathejunior: $P_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of even length, $D_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of odd length.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 10:29
$begingroup$
@Mathejunior: $P_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of even length, $D_ell$ stands for the number of strings with length $ell$ with an $text{LPS}$ of odd length.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 10:29
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%2f3032023%2ffind-the-number-of-words-recursively-such-that-there-is-no-palindromic-suffix%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$
I believe the only non-trivial part is to manage the words with a palindromic suffix which are also words with a palindromic suffix of different length: for instance $7010010010$ has three palindromic suffixes, namely $010,010010,010010010$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 4:59
$begingroup$
Also, single characters are, strictly speaking, palindromic, so I guess we want to count the number of words with a maximal palindromic suffix of length $geq 2$.
$endgroup$
– Jack D'Aurizio
Dec 9 '18 at 5:03
1
$begingroup$
@JackD'Aurizio yes, see I wrote $1< k leq N$ which conveys the fact that $Ngeq 2$.
$endgroup$
– Mathejunior
Dec 9 '18 at 5:06