|
%I #26 Jul 14 2018 17:37:34
%S 1,1,1,3,11,32,152,625,3152,16154,90993,539181,3398803,22561791,
%T 157493522,1151863409,8803760900,70149141443,581461668973,
%U 5004153572628
%N 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}^*.
%C 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).
%C 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).
%C 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.
%D 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]
%H D. D. Freydenberger, D. Reidenbach and J. C. Schneider, <a href="http://dx.doi.org/10.1007/11505877_22">Unambiguous Morphic Images of Strings</a>. International Journal of Foundations of Computer Science 17 (2006), pp. 601-628.
%H D. Hamm and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/hamm2.ps">Characterization of finite and one-sided infinite fixed points of morphisms on free monoids</a>. Technical Report CS-99-17, Dep. of Computer Science, University of Waterloo, 1999.
%H D. Reidenbach, <a href="https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/3469/3/Reidenbach_TCS_Discontinuities_Pattern_Inference.pdf">Discontinuities in pattern inference</a>. Theoretical Computer Science 397(1-3) (2008), pp. 166-193. doi:10.1016/j.tcs.2008.02.029
%H D. Reidenbach and J. C. Schneider, <a href="http://www-agrw.informatik.uni-kl.de/~schneide/files/reidenbach_schneider_morphically_primitive_words.pdf">Morphically Primitive Words</a>. In Pierre Arnoux, Nicolas Bedaride and Julien Cassaigne, editors, Proc. 6th International Conference on Words, WORDS 2007, pages 262-272. 2007.
%H Daniel Reidenbach, <a href="http://www-staff.lboro.ac.uk/~codr2/">Home Page</a>
%H Johannes C. Schneider, <a href="http://www-agrw.informatik.uni-kl.de/~schneide/">Home Page</a>
%e For length n = 4, the following words w in {1,2,3,...}^* are morphically primitive:
%e 1 1 1 1
%e 1 1 2 2
%e 1 2 2 1
%e 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).
%Y Cf. A000110.
%K nonn,more
%O 1,4
%A Johannes C. Schneider (jschneider(AT)informatik.uni-kl.de), Oct 04 2007
%E a(16)-a(19) from _Gary Bennett_, Apr 06 2015
%E a(20) from _Gary Bennett_, Aug 25 2015
| 