fibonacci kelimesinin alt sözcükleri

Fibonacci kelimesi , "0" ile başlayan ve $ 0 \ - 01, 1 0'a. Başlangıç ​​koşullarının $ S_0 = 0, S_1 = 01 $ olması ve sonra tekrarı $ S_n = S_ {n-1} S_ {n-2} $ olması eşdeğerdir.

Hangi kelimelerin $ S_ \ infty $ sınırında alt kelime olarak görünemediğini bilmek istiyorum. İlk başta, 000 ve 11'in görünmeyen tek iki olduğunu düşündüm. Daha sonra 010101'i farkettim. Hangi kelimelerin Fibonacci kelimesinin alt kelimeleri olarak görünebileceği veya görünmeyeceği konusunda herhangi bir özellik var mı?

Gevşek bir şekilde ilişkili olan bu kelime, kaynak olsa da $ \ phi = (1 + \ sqrt {5})/2 $ eğim çizgisinin kesim dizisi olarak görünür.

17
@İşaret. Hedlund, Haglund değil.
katma yazar Nathan Baulch, kaynak
@Joel: Haklısın. $ N + 2 $ yerine $ n + 3 $ idi. Sanırım doğru hatırlayamadım.
katma yazar Jesper Kihlberg, kaynak
@Denis: Haklısın. Teşekkürler!
katma yazar Jesper Kihlberg, kaynak
Bkz. Berstel, "Sturmian kelimelerin dizini" ve Mignosi tarafından daha önce burada belirtilen bir yazı. Fibonacci sözcüğü için endeks gerçekten 4'tür, 3 değil, genel olarak endeks sonludur, kısmi kesirler sınırlanırsa (hatırladığım gibi), ancak kesin endeksin hesaplanması kolay değildir, bu yüzden $ n + 2 $ yanlış olur. Ama bir yerlerde $ n + 2 $ gördüğümü hatırlıyorum. Hedlund ve Morse'da kanıt olmadan mıydı? Garip.
katma yazar Jesper Kihlberg, kaynak
Fibonacci sözcüğü küp içermez. Bu, orijinal makalesinde Hedlund ve Morse tarafından fark edildi. Bunun nedeni, altın ortalamanın devam eden fraksiyonunun ayrışmasında, tüm sayıların 1 olmasıdır. Genel olarak, devam edilen kısımdaki sayılar $ n $ ile sınırlanırsa, Sturmian kelimesi $ n + 2 $ güçleri içermez.
katma yazar Jesper Kihlberg, kaynak
Yorumlarımda "Haglund" ı "Hedlund" ile değiştirdim, ama şimdi yorumlar sıra dışı. Yine de, yanlış sonucu yanlış bir matematikçiye atfetmekten daha iyidir.
katma yazar Jesper Kihlberg, kaynak
Bazı ek bilgiler: Fibonacci sözcüğü küp içermez. Örneğin, "10010 10010 10010" alt sözcüğünü içerir. (Başka bir yorum: Belki de birileri "sözcükler üzerine kombinasyon" etiketini yazmalıdır.)
katma yazar wogsland, kaynak
oeis.org/A003849 'a göre, ilk 24 terim "010010100 10010 10010 10010 100" dir. Ancak 10. ila 24. terimler bir küptür.
katma yazar wogsland, kaynak
TD Noe'nin ilk 1652 alt listesinin bir listesi ( oeis.org/A003849 'a göre) < a href = "http://oeis.org/A003849/a003849.txt" rel = "nofollow noreferrer"> oeis.org/A003849/a003849.txt
katma yazar wogsland, kaynak
@İşaret. Referanslar ve bilgiler için teşekkürler.
katma yazar wogsland, kaynak

6 cevap

Fibonacci kelimesi Sturmian kelimelerden biridir, bu nedenle karmaşıklığı $ n + 1 $ , $ n $ uzunluğundaki farklı alt anahtarların sayısı $ n + 1 $ 'dır. Yani çoğu kelime Fibonacci kelimesinin alt yazıları değildir. Sturmian kelimelerin 12 farklı ama eşdeğer tanımını hatırladığım kadarıyla var. Bazıları olası alt kelimelerle ilgili kısıtlamalar getirmektedir (Lothaire tarafından yazılan kelimelerle ilgili cebirsel birleştiricilere ve orada Berstel'in bir makalesine bakınız).

25
katma
Fibonacci kelimesinin alt kelime karmaşıklığının bir kanıtı p_f (n) = n + 1, Allouche ve Shallit'in Otomatik Dizileri (10, 2003, Cambridge University Press) 'te bulunabilir.
katma yazar wogsland, kaynak

$ W $ sonlu bir sözcüğün Fibonacci sözcüğü $ S_ \ infty $ 'in bir faktörü (alt kelime) olup olmadığını belirlemenin en kolay yolu (doğrusal-zaman, hesaplamalı):

  • Varsa, izini 0 $ $ 'dan çıkar, varsa (yalnızca biri); $ w $ 1 ile başlıyorsa, baştaki 0 ​​ekleyin;
  • Bu şekilde elde edilen kelime benzersiz bir şekilde ayrıştırılmalıdır (bir birleştirme olarak yazılır) 0 ve 01; değilse, o zaman $ w $ $ S_ \ infty $ faktörü değildir ve bitirdiniz. $ W = x_1x_2 \ cdots x_k $ böyle bir ayrıştırma ise, $ y_i = 0 $ tüm $ i $ için olsun, $ x_i = 01 $ olsun ).
  • Aynı algoritmayı $ w '= y_1 \ cdots y_k $
  • yeni sözcüğüne uygulayın
  • Orijinal $ w $, $ S_ \ infty $ 'nin bir faktörüdür ve yalnızca ve nihayetinde yukarıdaki yordamı tekrarlayarak 0 veya 1 kelimesine ulaşırsanız

Fibonacci sözcüğü $ 0 \ - 01 $, $ 1 \ ila 0 $ (folklor, orjinal, bakınız örn. fr/~ berstel/Lothaire/AlgCWContents.html "> Sözcüklerde Cebirsel Birleştirici ). Örneğin, $ w = 1010010010100 $, yukarıdaki algoritma tarafından oluşturulan sözcüklerin sırası olduğundan, bir faktördür: $$ w, \: 00101001, \: 10010, \: 010, \: 0 \.

If you need a more dynamical point of view, Sturmian shifts (such as Fibonacci) are neither of finite type nor sofic. However, it is not hard to get the list of minimal forbidden factors of the Fibonacci word, as follows. Let $S_i'$ be the $i$-th palindromic prefix of $S_\infty$, which you can obtain by removing the last two characters in $S_i$. Then a finite word $w$ is a factor of the Fibonacci word if and only if it does not contain any of the following as factors, for all $k\geq 1$: $$1S_{2k-1}'1,\quad 0S_{2k}'0\;.$$ In other terms, the sequence of minimal forbidden factors is 11, 000, 10101, 00100100, 1010010100101, … See for instance Mignosi et al., Words and forbidden factors

13
katma

I don't know if there is a simple characterization, but it seems there is a simple algorithm. See Bartosz Walczak, A simple representation of subwords of the Fibonacci word, available at http://tcs.uj.edu.pl/~walczak/fibonacci.pdf

4
katma

Fibonacci dizisi bir quasiperiodic dizisidir. Quasiperiodic sekanslar (ve daha genel olarak: quasiperiodic menfezler); "şerit projeksiyon yöntemi" ile. Kabaca konuşma: Kafes $ \ mathbb {Z} ^ 2 $ alın ve birim küp $ [0,1] ^ 2 $ 'ı çevreleyen irrasyonel menşe boyunca çizgi boyunca çevirerek bir şerit elde edin. Şeridin içinde kalan $ \ mathbb {Z} ^ 2 $ 'nin tüm kenarlarını göz önünde bulundurun. Daha sonra dikey ve yatay kenarların dizisi, bir quasiperiodic dizisidir. Lütfen cf. Örneğin. http://arxiv.org/pdf/cond-mat/9903010v1.pdf , bir Fibonacci sekansı için Şekil 4.2, (eğim = altın oran 0.618 ...).

Bu nedenle, bir kelimenin Fibonacci kelimesinin bir alt sözcüğü olup olmadığını test etmek için, onu $ \ mathbb {Z} ^ 2 $ 'nin kenar grafiğindeki bir yola “kaldırın” ve altın rasyon eğim şeridinde olup olmadığını test edin. ve karşılık gelen genişlikler (örneğin dik olarak çıkıntı yaparak).

Fibonacci sözcüğündeki alt kelimenin (asimptotik) sıklığını elde etmek için bile bu yöntemi genişletebilirsiniz; bu, alt kelimenin dikey çıkıntısının uzunluğunun, şeridin çıkıntısının uzunluğuyla (yani, = uzunluk) birim kare izdüşümünün tanımı). Elbette en kolay durum, düşey bir bölgeye yükselen sekanstaki iki bina alanıdır. kafesin yatay kenarı. Dolayısıyla, oluşma sıklığının rasyonları yine altın rasyondur. Ancak hemen herhangi bir alt kelimenin sıklığı ile aynı şekilde hesaplayabilirsiniz.

2
katma

Bu soruya zaten bazı mükemmel cevaplar var, ancak şimdi Fibonacci kelimesini takdir edebileceğiniz gibi, çok iyi yapılandırılmış ve alt sınıflarını sınırlayan ilginç özelliklere sahip. Şu ana kadarki cevapların hiçbirinin doğrudan Fibonacci kelimesinin - tüm Sturmian kelimeler gibi - dengeli olduğu gerçeğini ele almadığını fark ettim. Bir kelimenin dengeli olduğunu söylemek, eşit uzunlukta herhangi bir alt çift çifti için, her bir alt kelimedeki sıfır sayısının ya birbirine eşit olması ya da tam olarak birbirinden farklı olması gerektiği anlamına gelir. En basit dengesiz kelime 0011'dir, çünkü 00 ve 11 alt-maddelerinde sıfır sayısı sırasıyla iki ve sıfırdır. Yalnızca $ O (n ^ 3) $ dengelenmiş $ $ kelime uzunluğuna sahip kelimeler olduğundan, bu özellik izin verilen alt anahtarların sayısını oldukça kısıtlar.

Listelediğiniz yasak sözcüklerin örnekleri - 000, 11 ve 010101 - kendileri dengeli sözcüklerdir, ancak yine de denge kuralı, Fibonacci kelimesinde gerçekleşmelerini önler. Bunu görmek için şu şekilde tartışabiliriz. 101 Fibonacci kelimesinde gerçekleştiği için 000 içeremez, çünkü bu iki alt sözcükteki sıfır sayısı iki farklı olacaktır. Benzer şekilde 00 içerdiğinden 11 içeremez ve 00100 içerdiğinden 10101 içeremez.

Sonsuz bir sözcük dengelenmişse, sıfırın $ n $ uzunluğundaki alt para birimlerinde sıfır olanlara oranı, limitinde $ n \ - \ infty $ arasındaki sabit bir orana hızlı ve düzgün bir şekilde birleşir. Fibonacci sözcüğü söz konusu olduğunda bu sınır altın orandır. Dinamik bir perspektiften bakıldığında bu yakınlaşma, ilişkili sembolik dinamik sistemin benzersiz ergodikliği nedeniyledir, ancak aynı zamanda sürekli kesirlerle güçlü bağlantıları vardır: devam eden kesir oranlarının altın orana oranının, sıfır oranların belirli oranlarda sıfırlar olarak ortaya çıktığını fark edeceksiniz. Fibonacci kelimesinin alt sözcükleri. Lothaire ( Kelimelerle ilgili cebirsel kombinasyonlar , yukarıda belirtilenler) ve Fogg ( Dinamik, aritmetik ve kombinasyonlar yer değiştirmeleri) ile mükemmel kitaplar Fibonacci kelimesi ve Sturmi dili için iyi referanslardır. ve daha genel olarak dengeli kelimeler.

2
katma

Fibonacci kelimesinde $ f $ (esasen sorusunda dikkat çektiği karakterizasyonundan gelir) kelimesinde Fibonacci kelimesinde faktör olarak görünmeyen kelime kümesini belirlemek için basit bir algoritma vardır.

Fibonacci dizisini $ (F_n) _ {n \ geq 0} = 1,1,2,3,5,8, \ ldots $ alın. $ 1 $ 'dan daha büyük her $ $ için Fibonacci kelimesinin başında $ f $ ($, $ f_n -2 $). Bu size $ \ lambda, 0,010,010010, \ ldots $ kelimelerinin sırasını verir. Şimdi, bu kelimelerin her biri için $ v $, eğer $ v $ ve ardından $ 1 $ sonra $ 0v0 $ alır; Aksi takdirde, $ v $ ve ardından $ 0 $ sembolü gelirse, $ 1v1 $ alın. Bu size $ f $ 'da, yani $ f $' nın en düşük yasaklı faktörleri olarak görünmeyen en az uzunlukta kelimeler dizisini verir: $ 11,000,10101,00100100, \ ldots $

Fibonacci kelimesinde $ f $ kelimesi alt kelimesi olarak görünmeyen kelimeler, kesinlikle yasaklanmış bir faktörü içeren $ \ {0,1 \} $ kelimesidir.

2
katma