Gabriele Fici has authored 3 sequences.
A291365
Number of closed Sturmian words of length n.
Original entry on oeis.org
2, 2, 4, 6, 12, 16, 26, 36, 52, 64, 86, 108, 142, 170, 206, 242, 294, 340, 404, 468, 544, 610, 698, 786, 894, 990, 1104, 1218, 1360, 1494, 1658, 1822, 2006, 2174, 2366, 2558, 2786, 2996, 3230, 3464
Offset: 1
For n = 4, the closed Sturmian words of length n are "aaaa", "abab", "abba", "baab", "baba" and "bbbb".
- Michael S. Branicky, Python program
- Michelangelo Bucci, Alessandro De Luca and Gabriele Fici, Enumeration and structure of trapezoidal words, Theor. Comput. Sci. 468: 12-22 (2013).
- Gabriele Fici, Open and Closed Words, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.
- Alessandro De Luca and Gabriele Fici, Open and Closed Words, in Lecture Notes in Computer Science, vol. 8079, pp. 132-142, 2013. Available at arXiv, arXiv:1306.2254 [math.CO], 2013.
- Alessandro De Luca, Gabriele Fici and Luca Q. Zamboni. The sequence of open and closed prefixes of a Sturmian word. Advances in Applied Mathematics Volume 90, September 2017, Pages 27-45. Available at arXiv, arXiv:1701.01580 [cs.DM], 2017.
-
# see link for faster, bit-based version
from itertools import product
def is_strm(w): # w is a finite Sturmian word
for l in range(2, len(w)):
facts = set(w[j:j+l] for j in range(len(w)-l+1))
counts = set(f.count('0') for f in facts)
if max(counts) - min(counts) > 1:
return False
return True
def is_clsd(w): # w is a closed word
if len(set(w)) <= 1: return True
for l in range(1, len(w)):
if w[:l] == w[-l:] and w[:l] not in w[1:-1]:
return True
return False
def is_cs(w): # w is a closed Sturmian word
return is_clsd(w) and is_strm(w)
def a(n):
return 2*sum(is_cs("0"+"".join(b)) for b in product("01", repeat=n-1))
print([a(n) for n in range(1, 17)]) # Michael S. Branicky, Sep 27 2021
A194850
Number of prefix normal words of length n.
Original entry on oeis.org
2, 3, 5, 8, 14, 23, 41, 70, 125, 218, 395, 697, 1273, 2279, 4185, 7568, 13997, 25500, 47414, 87024, 162456, 299947, 562345, 1043212, 1962589, 3657530, 6900717, 12910042, 24427486, 45850670, 86970163, 163756708, 311283363, 587739559, 1119581278, 2119042830
Offset: 1
For n=3: aaa, aab, abb, aba, bbb are all prefix normal words. - _Zsuzsanna Liptak_, Oct 12 2011
- Zsuzsanna Liptak, Table of n, a(n) for n = 1..50
- Paul Balister and Stefanie Gerke, The asymptotic number of prefix normal words, arXiv:1903.07957 [math.CO], 2019.
- P. Burcsi, G. Fici, Zs. Lipták, F. Ruskey, and J. Sawada, On Combinatorial Generation of Prefix Normal Words, arXiv:1401.6346 [cs.DS], 2014.
- P. Burcsi, G. Fici, Z. Lipták, F. Ruskey, and J. Sawada, Normal, Abby Normal, Prefix Normal, arXiv preprint arXiv:1404.2824 [cs.FL], 2014.
- P. Burcsi, G. Fici, Z. Lipták, F. Ruskey, and J. Sawada, On prefix normal words and prefix normal forms, Preprint, 2016.
- Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Rajeev Raman, and Joe Sawada, Generating a Gray code for prefix normal words in amortized polylogarithmic time per word, arXiv:2003.03222 [cs.DS], 2020.
- Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Frank Ruskey, and Joe Sawada, On Prefix Normal Words and Prefix Normal Forms, arXiv:1611.09017 [cs.DM], 2016.
- Ferdinando Cicalese, Zsuzsanna Lipták, and Massimiliano Rossi, Bubble-Flip—A new generation algorithm for prefix normal words, arXiv:1712.05876 [cs.DS], 2017-2018; Theoretical Computer Science, Volume 743, 26 September 2018, Pages 38-52.
- Ferdinando Cicalese, Zsuzsanna Lipták, and Massimiliano Rossi, On Infinite Prefix Normal Words, arXiv:1811.06273 [math.CO], 2018.
- G. Fici and Zs. Lipták, On Prefix Normal Words
- G. Fici and Zs. Lipták, On Prefix Normal Words, Developments in Language Theory 2011, Lecture Notes in Computer Science 6795, 228-238.
- Pamela Fleischmann, On Special k-Spectra, k-Locality, and Collapsing Prefix Normal Words, Ph.D. Dissertation, Kiel University (Germany, 2021).
- Pamela Fleischmann, Mitja Kulczynski, and Dirk Nowotka, On Collapsing Prefix Normal Words, arXiv:1905.11847 [cs.FL], 2019.
- Pamela Fleischmann, Mitja Kulczynski, Dirk Nowotka, and Danny Bøgsted Poulsen, On Collapsing Prefix Normal Words, Language and Automata Theory and Applications (LATA 2020) LNCS Vol. 12038, Springer, Cham, 412-424.
- Zsuzsanna Lipták, Open problems on prefix normal words, also in Dagstuhl Reports (2018) Vol. 8, Issue 7, 59-61.
Cf.
A062692 (binary pre-necklaces).
See
A238109 for a list of the prefix-normal words.
-
from itertools import product
def is_prefix_normal(w):
for k in range(1, len(w)+1):
weight0 = w[:k].count("1")
for j in range(1, len(w)-k+1):
weightj = w[j:j+k].count("1")
if weightj > weight0: return False
return True
def a(n):
return sum(is_prefix_normal(w) for w in product("01", repeat=n))
print([a(n) for n in range(1, 20)]) # Michael S. Branicky, Dec 19 2020
Original entry on oeis.org
2, 5, 12, 30, 77, 200, 522, 1365, 3572, 9350, 24477, 64080, 167762, 439205, 1149852, 3010350, 7881197, 20633240, 54018522, 141422325, 370248452, 969323030, 2537720637, 6643838880, 17393796002, 45537549125, 119218851372, 312119004990, 817138163597, 2139295485800
Offset: 0
- Robert Israel, Table of n, a(n) for n = 0..1000
- Clark Kimberling, Lucas Representations of Positive Integers, J. Int. Seq., Vol. 23 (2020), Article 20.9.5.
- David C. Luo, Nonuniqueness Properties of Zeckendorf Related Decompositions, arXiv:2004.08316 [math.NT], 2020.
- Index entries for linear recurrences with constant coefficients, signature (4,-4,1).
-
[5*Fibonacci(n)*Fibonacci(n+1)+1+(-1)^n: n in [0..40]]; // Vincenzo Librandi, Jan 24 2016
-
f:= gfun:-rectoproc({a(n+3)-4*a(n+2)+4*a(n+1)-a(n), a(0) = 2, a(1) = 5, a(2) = 12}, a(n), remember):
map(f, [$0..60]); # Robert Israel, Feb 02 2016
-
LinearRecurrence[{4,-4,1},{2,5,12},30] (* Harvey P. Dale, Oct 05 2015 *)
Accumulate@ LucasL@ Range[0, 58, 2] (* Michael De Vlieger, Jan 24 2016 *)
-
a(n) = 5*fibonacci(n)*fibonacci(n+1) + 1 + (-1)^n; \\ Michel Marcus, Aug 26 2013
-
Vec((-2+3*x)/((x-1)*(x^2-3*x+1)) + O(x^100)) \\ Altug Alkan, Jan 24 2016
Comments