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.

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. [Different from the paper with the same name, referenced below.]

Daniel Reidenbach and Johannes C. Schneider, Morphically primitive words, Theoretical Computer Science, 410 (2009), 2148-2161. (alternative link) See Table 1.

Daniel Reidenbach, Home Page [dead link]

Johannes C. Schneider, Home Page [dead link]

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