Timeline for Combinatorics of palindromic decompositions
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 23, 2016 at 18:07 | history | bounty ended | CommunityBot | ||
| Oct 22, 2016 at 5:59 | comment | added | მამუკა ჯიბლაძე | (polynomial, I mean, in all three variables) | |
| Oct 22, 2016 at 5:51 | comment | added | მამუკა ჯიბლაძე | @MartinRubey Since for big enough $N$ the condition becomes "local" (that is, involving subwords of length depending on $m$ only) it seems plausible that one gets$(n-f(m))^{N-g(m)}$ times a polynomial, but I don't see the details. And many thanks for the information about the $m=2,3$ cases! | |
| Oct 19, 2016 at 19:32 | comment | added | Martin Rubey | Is it clear that $\# P_n^{(N)}(m)$ is a polynomial in $n$? | |
| Oct 19, 2016 at 19:27 | comment | added | Martin Rubey | This pattern continues as follows: for $m=2$ and $N>3$ we get $(n-2)^{N-4}(n-1)n((2N-3)n-5(N-2))$. For $m=3$ we get a quadratic factor. | |
| Oct 18, 2016 at 9:26 | comment | added | მამუკა ჯიბლაძე | The proof is actually quite simple: we are counting palindrome-free words here. These are precisely the words not containing patterns $...xx...$ and $...xyx...$. It follows that for the first letter there are $n$ possibilities (any letter), for the second - $n-1$ (any except the first) and for $k$th with each $k>2$ there are $n-2$ possibilities (any letter except $k-1$st and $k-2$nd). | |
| Oct 17, 2016 at 19:48 | comment | added | მამუკა ჯიბლაძე | Interesting. In fact it looks like $\#P_n^{(N)}(1)=n(n-1)(n-2)^{N-2}$ | |
| Oct 17, 2016 at 19:20 | history | edited | Bjørn Kjos-Hanssen | CC BY-SA 3.0 |
edited body
|
| Oct 17, 2016 at 14:55 | comment | added | Fedor Petrov | I think, $\sharp P_n^{(2)}(1)=n(n-1)$ by the very definition (we count words of length 2 which are distinct.) | |
| Oct 17, 2016 at 5:59 | history | answered | Bjørn Kjos-Hanssen | CC BY-SA 3.0 |