Berapa banyak kata dengan panjang

DIedit UNTUK MENAMBAH : Pertanyaan ini sekarang pada dasarnya dijawab; silakan lihat entri blog ini untuk lebih jelasnya. Terima kasih kepada semua orang yang mengirim komentar dan jawaban di sini.

---

PERTANYAAN ASLI

Mudah-mudahan ini adalah versi pertanyaan yang lebih cerdas dan lebih baik dari pertanyaan yang saya ajukan di MathOverflow. Ketika saya mengajukan pertanyaan itu, saya bahkan tidak tahu nama bidang matematika dari masalah saya. Sekarang saya cukup yakin itu terletak pada Algoritma Combinatorics pada Partial Words. (Buku terbaru tentang subjek di sini .)

Saya ingin membuat daftar kata pada huruf . Setiap kata memiliki panjang tepat . Kesepakatannya adalah, jika ada dalam daftar, di mana adalah simbol wildcard / tidak peduli, maka tidak akan pernah muncul lagi dalam daftar. (Hal yang sama berlaku jika , atau jika dan karenanya kata kunci yang dilarang adalah .)k a ◊ j b ◊ sebuah ◊ j b a = b j = 0 a $l$$k$$a \lozenge ^j b$$\lozenge$$a \lozenge ^j b$$a=b$$j=0$$ab$

Contoh di mana dan :l = $k=4$$l=5$

b d c e d c b a d c a e e d a ◊ ◊ $abcd$
$bdce$
$dcba$ <- dilarang karena muncul di baris di atas <- dilarang karena muncul di baris pertama$dc$
$aeed$$a \lozenge \lozenge d$

Literatur tentang "kata-kata parsial yang dapat dihindari" yang saya temukan semuanya bersifat infinitary - pada akhirnya beberapa pola kata tidak dapat dihindari jika ukuran kata cukup besar. Saya ingin menemukan versi teoretis dari teorema semacam itu. Jadi, pertanyaan:

Mengingat kata parsial bentuk dalam alfabet l huruf, berapa banyak kata-kata panjang k menghindari hal itu, dan mereka dapat secara eksplisit diproduksi dalam waktu polinomial?$a \lozenge^j b$$l$$k$

Saya tidak berharap pertanyaan di atas menjadi sulit, dan, kecuali ada kehalusan saya hilang, saya bisa menghitungnya sendiri. Alasan sebenarnya saya memposting di situs ini adalah karena saya perlu tahu lebih banyak tentang properti dari daftar kata tersebut untuk aplikasi saya, jadi saya berharap seseorang dapat menjawab pertanyaan tindak lanjut:

Apakah ini telah dipelajari secara umum? Apa beberapa makalah yang mempertimbangkan, bukan hanya apakah sebagian kata pada akhirnya tidak dapat dihindari, tetapi "berapa lama" sebelum menjadi tidak dapat dihindari?

Terima kasih.

Berikut adalah kasus khusus: jumlah kata biner panjang sehingga tidak ada dua yang muncul berturut-turut adalah F ( k + 3 ) , di mana F ( n ) adalah n t h nomor Fibonacci (dimulai dengan F ( 1 ) = 1 , F ( 2 ) = 1 ). Buktinya adalah melalui representasi Zeckendorf .$k$$F(k+3)$$F(n)$$n^{th}$$F(1)=1, F(2)=1$

EDIT: Kami dapat memperpanjang kasus khusus awal ini ke dalam kasus khusus yang sedikit lebih besar dari . Pertimbangkan string dengan panjang k di atas alfabet ukuran l + 1 sehingga huruf a tidak muncul dua kali secara berurutan. Biarkan f ( k ) menjadi jumlah string seperti itu (yang akan kita sebut "valid"). Kami mengklaim bahwa: f ( k ) = l ∗ f ( k - 1 ) + l ∗ f ( k - 2 $a\lozenge^0a$$k$$l+1$$a$$f(k)$

$$f(k) = l*f(k-1) + l*f(k-2)$$ Intuisi adalah bahwa kita dapat membuat string panjang k yang validdengan: a) menyatukan salah satuhuruf l yang bukan a ke string dengan panjang k yang valid - 1 , atau b) bersebelahan dengan huruf a dan kemudian huruf lain selain a dengan panjang k k - 2 yang valid. $$f(0) = 1, f(1) = l+1$$ $k$$l$$a$$k-1$$a$$a$$k-2$

Anda dapat memverifikasi bahwa berikut ini adalah bentuk tertutup untuk kambuh di atas: mana kita memahamisaat.

$$f(k) = \sum_{i=0}^{k} {{k+1-i}\choose{i}} l^{k-i}$$ i>${{n}\choose{i}} = 0$$i>n$

EDIT # 2: Mari kita lepaskan satu case lagi - a . Kami akan memanggil string melalui alfabet elemen- yang tidak mengandung substring , "valid" dan biarkan menunjukkan set string panjang yang valid . Selanjutnya, mari kita mendefinisikan menjadi subset dari terdiri dari string yang dimulai dengan dan menjadi yang tidak dimulai dengan . Akhirnya, biarkan,,.l a b S k k T k S k b U k b f ( k ) = | S k | g ( k ) = | T k | h ( k ) = | U k $\lozenge^0 b, a \neq b$$l$$ab$$S_k$$k$$T_k$$S_k$$b$$U_k$$b$$f(k) = |S_k|$$g(k) = |T_k|$$h(k) = |U_k|$

Kami mengamati bahwa dan . Selanjutnya, kami menyimpulkan rekurensi berikut: Yang pertama berasal dari fakta bahwa menambahkan ke awal setiap elemen menghasilkan elemen . Yang kedua berasal dari pengamatan bahwa kita dapat membangun elemen dengan menambahkan karakter apa pun tetapi ke depan elemen atau dengan menambahkan karakter apa pun kecuali atau ke bagian depan elemen apa pun di .g ( 1 ) = 1 , h ( 1 ) = l - 1 , f ( 1 ) = l g ( k + 1 $g(0)=0, h(0)=1, f(0)=1$$g(1)=1, h(1)=l-1, f(1)=l$ bSkTk+1Uk+1bUkabT

$$\begin{eqnarray} g(k+1) &=& f(k) \\ h(k+1) &=&(l-1)*h(k) + (l-2)*g(k) \end{eqnarray}$$ $b$$S_k$$T_{k+1}$$U_{k+1}$$b$$U_{k}$$a$$b$$T_k$

Selanjutnya, kami mengatur ulang persamaan perulangan untuk memperoleh:

$$\begin{eqnarray} f(k+1) &=& g(k+1) + h(k+1) \\ &=& f(k) + (l-1)*h(k) + (l-2)*g(k) \\ &=& f(k) + (l-1)*f(k) - g(k) \\ &=& l*f(k) - f(k-1) \end{eqnarray}$$

Kita bisa mendapatkan solusi bentuk-tertutup yang agak buram untuk pengulangan ini dengan sedikit campur aduk dengan menghasilkan hal-hal fungsi atau, jika kita malas, langsung menuju ke Wolfram Alpha . Namun, dengan sedikit googling dan mengaduk-aduk di OEIS , kami menemukan bahwa kami sebenarnya memiliki: mana adalah Chebyshev dari jenis kedua (!) .U k k t

$$f(k) = U_k(l/2)$$ $U_k$$k^{th}$

Pendekatan yang sama sekali berbeda untuk pertanyaan pertama menggunakan kembali jawaban untuk pertanyaan terakhir tentang menghasilkan kata-kata dalam bahasa reguler : cukup untuk menerapkan algoritma ini untuk panjang pada bahasa biasa dimana adalah alfabet.Σ * a Σ j b Σ *$k$$\Sigma^\ast a\Sigma^j b\Sigma^\ast$$\Sigma$

Diperbarui: jawaban ini salah :

dengan asumsi adalah tetap, kita bisa menghitung jumlah cara pola a ◊ j b dapat dicocokkan: pertama sebuah simbol dapat dicocokkan di beberapa posisi 1 ≤ i ≤ k - j - 1 , dan kami memiliki l i - 1 kemungkinan sebelum titik itu, l j antara a dan b , dan l k - j - i - 1 untuk sisa string, sehingga total $j$$a\lozenge^j b$$a$$1\leq i\leq k-j-1$$l^{i-1}$$l^j$$a$$b$$l^{k-j-i-1}$kasing. Sebagaimana dicatat oleh Tsuyoshi Ito di komentar, jumlah initidakjumlah kata yang berbeda pencocokansebuah◊jbsejak satu kata bisa cocok dengan pola yang sama dengan cara yang berbeda. Misalnyasebuah

$$\sum_{i=1}^{k-j-1}l^{i-1}\cdot l^{j}\cdot l^{k-j-i-1}=(k-j-1)l^{k-2}$$ $a\lozenge^j b$$aa$cocok tiga kali dalam , sebuah b dua kali dalam satu b a b , dan a ◊ b dua kali di sebuah a b b . Kita dapat mencoba menghitung jumlah cara pencocokan pola beberapa kali dan menunjukkan ekspresi "inklusi-pengecualian", tetapi cara-cara pola yang mungkin tumpang tindih membuat ini terlalu lama.$aaaa$$ab$$abab$$a\lozenge b$$aabb$

---

Untuk pertanyaan pertama, di bawah pemahaman bahwa tidak tetap, yaitu bahwa kita ingin menghindari embedding kata a b :$j$$ab$

• baik simbol pertama tidak pernah muncul, yang menyumbang ( l - 1 ) k kata mungkin,$a$$(l-1)^k$
• atau muncul pertama kali pada beberapa posisi 1 ≤ i ≤ k , maka kita tidak dapat menggunakan b pada sisa kata: ada ( l - 1 ) i - 1 pilihan untuk faktor hingga a , dan ( l - 1 ) k - i pilihan untuk sisanya, memberikan total ∑ k i = 1 ( l - 1 ) i - 1 ⋅ ( l - $a$$1\leq i\leq k$$b$$(l-1)^{i-1}$$a$$(l-1)^{k-i}$ kata yang mungkin. Apakah a = b tidak relevan.$\sum_{i=1}^k(l-1)^{i-1}\cdot(l-1)^{k-i}=k(l-1)^{k-1}$$a=b$

Untuk pertanyaan kedua, saya tidak punya banyak saran; ada hubungan dengan embeddings kata, tetapi hasil yang saya tahu tentang urutan buruk untuk Higman Lemma tidak segera berlaku.