|
%I #101 Jul 02 2021 16:47:43
%S 2,3,5,8,14,23,41,70,125,218,395,697,1273,2279,4185,7568,13997,25500,
%T 47414,87024,162456,299947,562345,1043212,1962589,3657530,6900717,
%U 12910042,24427486,45850670,86970163,163756708,311283363,587739559,1119581278,2119042830
%N Number of prefix normal words of length n.
%C A binary word of length n is prefix normal if for all 1 <= k <= n, no factor of length k has more a's than the prefix of length k. That is, abbabab is not prefix normal because aba has more a's than abb. - _Zsuzsanna Liptak_, Oct 12 2011
%C a(n) <= A062692(n): every prefix normal word is a pre-necklace, but the converse is not true, see the Fici/Lipták reference. - _Joerg Arndt_, Jul 20 2013
%H Zsuzsanna Liptak, <a href="/A194850/b194850.txt">Table of n, a(n) for n = 1..50</a>
%H Paul Balister and Stefanie Gerke, <a href="https://arxiv.org/abs/1903.07957">The asymptotic number of prefix normal words</a>, arXiv:1903.07957 [math.CO], 2019.
%H P. Burcsi, G. Fici, Zs. Lipták, F. Ruskey, and J. Sawada, <a href="http://arxiv.org/abs/1401.6346">On Combinatorial Generation of Prefix Normal Words</a>, arXiv:1401.6346 [cs.DS], 2014.
%H P. Burcsi, G. Fici, Z. Lipták, F. Ruskey, and J. Sawada, <a href="http://arxiv.org/abs/1404.2824">Normal, Abby Normal, Prefix Normal</a>, arXiv preprint arXiv:1404.2824 [cs.FL], 2014.
%H P. Burcsi, G. Fici, Z. Lipták, F. Ruskey, and J. Sawada, <a href="http://www.cis.uoguelph.ca/~sawada/papers/pnf.pdf">On prefix normal words and prefix normal forms</a>, Preprint, 2016.
%H Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Rajeev Raman, and Joe Sawada, <a href="https://arxiv.org/abs/2003.03222">Generating a Gray code for prefix normal words in amortized polylogarithmic time per word</a>, arXiv:2003.03222 [cs.DS], 2020.
%H Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Frank Ruskey, and Joe Sawada, <a href="https://arxiv.org/abs/1611.09017">On Prefix Normal Words and Prefix Normal Forms</a>, arXiv:1611.09017 [cs.DM], 2016.
%H Ferdinando Cicalese, Zsuzsanna Lipták, and Massimiliano Rossi, <a href="https://arxiv.org/abs/1712.05876">Bubble-Flip—A new generation algorithm for prefix normal words</a>, arXiv:1712.05876 [cs.DS], 2017-2018; Theoretical Computer Science, Volume 743, 26 September 2018, Pages 38-52.
%H Ferdinando Cicalese, Zsuzsanna Lipták, and Massimiliano Rossi, <a href="https://arxiv.org/abs/1811.06273">On Infinite Prefix Normal Words</a>, arXiv:1811.06273 [math.CO], 2018.
%H G. Fici and Zs. Lipták, <a href="http://www.i3s.unice.fr/~mh/RR/2011/RR-11-03-G.FICI.pdf">On Prefix Normal Words</a>
%H G. Fici and Zs. Lipták, <a href="http://dx.doi.org/10.1007/978-3-642-22321-1_20">On Prefix Normal Words</a>, Developments in Language Theory 2011, Lecture Notes in Computer Science 6795, 228-238.
%H Pamela Fleischmann, <a href="https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/macau_derivate_00002273/diss.pdf">On Special k-Spectra, k-Locality, and Collapsing Prefix Normal Words</a>, Ph.D. Dissertation, Kiel University (Germany, 2021).
%H Pamela Fleischmann, Mitja Kulczynski, and Dirk Nowotka, <a href="https://arxiv.org/abs/1905.11847">On Collapsing Prefix Normal Words</a>, arXiv:1905.11847 [cs.FL], 2019.
%H Pamela Fleischmann, Mitja Kulczynski, Dirk Nowotka, and Danny Bøgsted Poulsen, <a href="https://doi.org/10.1007/978-3-030-40608-0_29">On Collapsing Prefix Normal Words</a>, Language and Automata Theory and Applications (LATA 2020) LNCS Vol. 12038, Springer, Cham, 412-424.
%H Zsuzsanna Lipták, <a href="http://profs.scienze.univr.it/~liptak/files/OpenProblemsPNW.pdf">Open problems on prefix normal words</a>, also in <a href="http://drops.dagstuhl.de/opus/volltexte/2019/10178/">Dagstuhl Reports</a> (2018) Vol. 8, Issue 7, 59-61.
%e For n=3: aaa, aab, abb, aba, bbb are all prefix normal words. - _Zsuzsanna Liptak_, Oct 12 2011
%o (Python)
%o from itertools import product
%o def is_prefix_normal(w):
%o for k in range(1, len(w)+1):
%o weight0 = w[:k].count("1")
%o for j in range(1, len(w)-k+1):
%o weightj = w[j:j+k].count("1")
%o if weightj > weight0: return False
%o return True
%o def a(n):
%o return sum(is_prefix_normal(w) for w in product("01", repeat=n))
%o print([a(n) for n in range(1, 20)]) # _Michael S. Branicky_, Dec 19 2020
%Y Cf. A062692 (binary pre-necklaces).
%Y See A238109 for a list of the prefix-normal words.
%K nonn
%O 1,1
%A _Gabriele Fici_, Sep 04 2011
%E More terms added by _Zsuzsanna Liptak_, Oct 12 2011
%E Further terms added by _Zsuzsanna Liptak_, Jan 29 2014
|
