15
$\begingroup$

This is sort of a companion to my question Number of trivializations of a trivial word in the free group (which in turn is motivated by my earlier question here). It turns out that that question may be reduced to this one (well to a certain extent at any rate).

A $\text{palindromic decomposition}$ (paldec for short) of a word $w$ (in letters, say, $a_1,...,a_n$) is any equality $$ w=p_1\cdots p_k $$ in the free semigroup on $a_1$, ..., $a_n$ such that each of the $p_i$ is a $\text{palindrome}$, i. e. coincides with itself read backwards.

Obviously each word has at least one such decomposition since each single letter word is a palindrome according to this definition. For many words this is the only one, but for quite a few there are several others. For example, the word referee has seven paldecs:

refer·ee
refer·e·e
r·efe·r·ee
r·efe·r·e·e
r·e·f·ere·e
r·e·f·e·r·ee
r·e·f·e·r·e·e

Thus for each $n$ and $N$ the set of $n^N$ words of length $N$ in $n$ letters decomposes into classes, with the class $P_n^{(N)}(m)$ containing all such words having exactly $m$ paldecs. These may be further subdivided according to various structures, but I cannot really judge which of these structures are more significant. For example, paldecs of a given word form a poset since some paldecs are subdecompositions of some others - say, the decomposition into single word letters is obviously the smallest element of this poset.

Have the numbers $\#P_n^{(N)}(m)$ or any of those corresponding to the above further subdivisions been considered in the literature? There are all kinds of papers on palindromes, too many for me to sort them out. Maybe somebody knows? Any generating functions, or statistics, or anything at all?

Later - collected some statistics: here are some of the distributions of words according to the numbers of paldecs:

$$\frac{\#P_n^{(2)}(m)}{n^2}\\ \begin{array}{r|llllllllll} m\backslash n &1&2&3&4&5&6&7&8&9&10\\ \hline 1 & 0 & 0.5 & 0.666667 & 0.75 & 0.8 & 0.833333 & 0.857143 & 0.875 & 0.888889 & 0.9 \\ 2 & 1. & 0.5 & 0.333333 & 0.25 & 0.2 & 0.166667 & 0.142857 & 0.125 & 0.111111 & 0.1 \end{array} $$

$$\frac{\#P_n^{(3)}(m)}{n^3}\\ \begin{array}{r|lllllllll} m\backslash n &1&2&3&4&5&6&7&8&9\\ \hline 1& 0 & 0 & 0.222222 & 0.375 & 0.48 & 0.555556 & 0.612245 & 0.65625 & 0.691358 \\ 2& 0 & 0.75 & 0.666667 & 0.5625 & 0.48 & 0.416667 & 0.367347 & 0.328125 & 0.296296 \\ 3& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4& 1. & 0.25 & 0.111111 & 0.0625 & 0.04 & 0.0277778 & 0.0204082 & 0.015625 & 0.0123457 \\ \end{array} $$

$$\frac{\#P_n^{(4)}(m)}{n^4}\\ \begin{array}{r|llllllll} m\backslash n &1&2&3&4&5&6&7&8\\ \hline 1& 0 & 0 & 0.0740741 & 0.1875 & 0.288 & 0.37037 & 0.437318 & 0.492188 \\ 2& 0 & 0 & 0.37037 & 0.46875 & 0.48 & 0.462963 & 0.437318 & 0.410156\\ 3& 0 & 0.5 & 0.296296 & 0.1875 & 0.128 & 0.0925926 & 0.0699708 & 0.0546875 \\ 4& 0 & 0.375 & 0.222222 & 0.140625 & 0.096 & 0.0694444 & 0.0524781 & 0.0410156\\ 5& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 6& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 7& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 8& 1. & 0.125 & 0.037037 & 0.015625 & 0.008 & 0.00462963 & 0.00291545 & 0.00195313 \end{array} $$

$$\frac{\#P_n^{(5)}(m)}{n^5}\\ \begin{array}{r|lllllll} m\backslash n &1&2&3&4&5&6&7\\ \hline 1& 0 & 0 & 0.0246914 & 0.09375 & 0.1728 & 0.246914 & 0.31237\\ 2& 0 & 0 & 0.148148 & 0.304688 & 0.384 & 0.416667 & 0.424823\\ 3& 0 & 0 & 0.246914 & 0.234375 & 0.192 & 0.154321 & 0.124948\\ 4& 0 & 0.125 & 0.246914 & 0.210938 & 0.1664 & 0.131173 & 0.104956\\ 5& 0 & 0.375 & 0.148148 & 0.0703125 & 0.0384 & 0.0231481 & 0.0149938\\ 6& 0 & 0.1875 & 0.0740741 & 0.0351563 & 0.0192 & 0.0115741 & 0.00749688\\ 7& 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 8& 0 & 0.25 & 0.0987654 & 0.046875 & 0.0256 & 0.0154321 & 0.00999584\\ 9& 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 10& 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 11& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 12& 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 13& 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 14& 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 15& 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 16& 1. & 0.0625 & 0.0123457 & 0.00390625 & 0.0016 & 0.000771605 & 0.000416493 \end{array} $$

$$\frac{\#P_n^{(6)}(m)}{n^6}\\ \begin{array}{r|llllll} m\backslash n &1&2&3&4&5&6\\ \hline 1& 0. & 0. & 0.00823045 & 0.046875 & 0.10368 & 0.164609 \\ 2& 0. & 0. & 0.0576132 & 0.1875 & 0.288 & 0.349794 \\ 3& 0. & 0. & 0.106996 & 0.169922 & 0.1728 & 0.156893 \\ 4& 0. & 0. & 0.18107 & 0.228516 & 0.21504 & 0.187757 \\ 5& 0. & 0. & 0.17284 & 0.123047 & 0.08064 & 0.0540123 \\ 6& 0. & 0.09375 & 0.139918 & 0.0908203 & 0.0576 & 0.0379372 \\ 7& 0. & 0.15625 & 0.0411523 & 0.0146484 & 0.0064 & 0.00321502 \\ 8& 0. & 0.1875 & 0.148148 & 0.0878906 & 0.05376 & 0.0347222 \\ 9& 0. & 0.09375 & 0.0246914 & 0.00878906 & 0.00384 & 0.00192901 \\ 10& 0. & 0.15625 & 0.0411523 & 0.0146484 & 0.0064 & 0.00321502 \\ 11& 0. & 0.0625 & 0.0164609 & 0.00585938 & 0.00256 & 0.00128601 \\ 12& 0. & 0.0625 & 0.0164609 & 0.00585938 & 0.00256 & 0.00128601 \\ 13& 0. & 0. & 0. & 0. & 0. & 0. \\ 14& 0. & 0. & 0. & 0. & 0. & 0. \\ 15& 0. & 0. & 0. & 0. & 0. & 0. \\ 16& 0. & 0.15625 & 0.0411523 & 0.0146484 & 0.0064 & 0.00321502 \\ 17& 0. & 0. & 0. & 0. & 0. & 0. \\ 18& 0. & 0. & 0. & 0. & 0. & 0. \\ 19& 0. & 0. & 0. & 0. & 0. & 0. \\ 20& 0. & 0. & 0. & 0. & 0. & 0. \\ 21& 0. & 0. & 0. & 0. & 0. & 0. \\ 22& 0. & 0. & 0. & 0. & 0. & 0. \\ 23& 0. & 0. & 0. & 0. & 0. & 0. \\ 24& 0. & 0. & 0. & 0. & 0. & 0. \\ 25& 0. & 0. & 0. & 0. & 0. & 0. \\ 26& 0. & 0. & 0. & 0. & 0. & 0. \\ 27& 0. & 0. & 0. & 0. & 0. & 0. \\ 28& 0. & 0. & 0. & 0. & 0. & 0. \\ 29& 0. & 0. & 0. & 0. & 0. & 0. \\ 30& 0. & 0. & 0. & 0. & 0. & 0. \\ 31& 0. & 0. & 0. & 0. & 0. & 0. \\ 32& 1. & 0.03125 & 0.00411523 & 0.000976563 & 0.00032 & 0.000128601 \end{array} $$

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ The concept of palindromic decomposition is not new, see e.g. this paper where the authors focus on so-called palindromic length, i.e., minimal number of terms in such a decomposition. However, I don't recall anything on the number of distinct paldecs of a word, sorry. $\endgroup$
    – Ale De Luca
    Commented Mar 30, 2015 at 19:01
  • $\begingroup$ @AleDeLuca Thank you, interesting reference indeed, and with some interesting further references. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Mar 30, 2015 at 19:46

1 Answer 1

Reset to default
2
+25
$\begingroup$

To get started you can use oeis.org to investigate this. For instance, from plugging in the numerators corresponding to some of your data it seems that $$\#P_n^{(2)}(1)=n(n-1)$$ ("the oblong numbers") and $$\#P_n^{(6)}(1)=n(n-1)(n-2)^4$$ ("the number of $n$-colorings of the Triangle Graph of order 3").

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I think, $\sharp P_n^{(2)}(1)=n(n-1)$ by the very definition (we count words of length 2 which are distinct.) $\endgroup$
    – Fedor Petrov
    Commented Oct 17, 2016 at 14:55
  • 1
    $\begingroup$ Interesting. In fact it looks like $\#P_n^{(N)}(1)=n(n-1)(n-2)^{N-2}$ $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Oct 17, 2016 at 19:48
  • 2
    $\begingroup$ 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). $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Oct 18, 2016 at 9:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Martin Rubey
    Commented Oct 19, 2016 at 19:27
  • 1
    $\begingroup$ Is it clear that $\# P_n^{(N)}(m)$ is a polynomial in $n$? $\endgroup$
    – Martin Rubey
    Commented Oct 19, 2016 at 19:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .