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} $$

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 Mar 30 '15 at 19:01