A131747 Number of morphically primitive words w in {1,2,3,...}^* of length n (modulo renaming), also the number of words (length n) which are fixed points of nontrivial morphisms, also the number of succinct patterns of length n in canonical form, also the number of words which have an unambiguous morphic image in {a,b}^*.

1, 1, 1, 3, 11, 32, 152, 625, 3152, 16154, 90993, 539181, 3398803, 22561791, 157493522, 1151863409, 8803760900, 70149141443, 581461668973, 5004153572628

Offset

1,4

Comments

A word v is called morphically primitive iff there is no shorter word v' such that there exist a morphism mapping v onto v' and a morphism mapping v' onto v (the morphisms may erase symbols).

So far, no formula is known to calculate this number for any given n. Note that the number of all words w in {1,2,3,...}^* of length n modulo renaming corresponds to the Bell number of n (see A000110).

It would be interesting to know the limit of the ratio of morphically primitive words and all words (modulo renaming). For n = 15, this ratio is approx. 0.1139. Moreover, note that the terms "primitive (or aperiodic) words" and "morphically primitive words" are incomparable.

References

Reidenbach, Daniel, and Johannes C. Schneider. "Morphically primitive words." (2009). See Table 1. Available from https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4561/1/Reidenbach_Schneider_TCS_Morphically_primitive_words_Final_version.pdf [Do not delete this reference, because I do not know if the similar link below (which does not seem to work) refers to an identical version of the article. - N. J. A. Sloane, Jul 14 2018]

Links

Table of n, a(n) for n=1..20.

D. D. Freydenberger, D. Reidenbach and J. C. Schneider, Unambiguous Morphic Images of Strings. International Journal of Foundations of Computer Science 17 (2006), pp. 601-628.

D. Hamm and J. Shallit, Characterization of finite and one-sided infinite fixed points of morphisms on free monoids. Technical Report CS-99-17, Dep. of Computer Science, University of Waterloo, 1999.

D. Reidenbach, Discontinuities in pattern inference. Theoretical Computer Science 397(1-3) (2008), pp. 166-193. doi:10.1016/j.tcs.2008.02.029

D. Reidenbach and J. C. Schneider, Morphically Primitive Words. In Pierre Arnoux, Nicolas Bedaride and Julien Cassaigne, editors, Proc. 6th International Conference on Words, WORDS 2007, pages 262-272. 2007.

Daniel Reidenbach, Home Page

Johannes C. Schneider, Home Page

Example

For length n = 4, the following words w in {1,2,3,...}^* are morphically primitive:
1 1 1 1
1 1 2 2
1 2 2 1
All other words of length 4 are either renamings of those words (e.g. 3 4 4 3 is a renaming of 1 2 2 1) or morphically imprimitive (e.g. 1 2 2 2).

Crossrefs

Cf. A000110.

Sequence in context: A296315 A125671 A034561 * A295626 A079996 A288038

Adjacent sequences: A131744 A131745 A131746 * A131748 A131749 A131750

Keyword

nonn,more

Author

Johannes C. Schneider (jschneider(AT)informatik.uni-kl.de), Oct 04 2007

Extensions

a(16)-a(19) from Gary Bennett, Apr 06 2015

a(20) from Gary Bennett, Aug 25 2015

Status

approved