Limite supérieure de fib (n + 2)

J'ai un problème de devoirs qui me rend perplexe parce que les mathématiques vont au-delà de ce que j'ai fait, même si on nous a dit qu'il n'était pas nécessaire de résoudre cela mathématiquement. Fournissez simplement une limite supérieure étroite et justifiez-la.

Soit Fournir une borne supérieure asymptotique sur comme .

$$f(n) = |\{w ∈ \{a, b\}^n : aa \notin w \}|.$$ $f$$n\to\infty$

Jusqu'à présent:

$$\begin{array}{c|c|c} n & \text{strings} & \text{compared to } 2^n \\\hline 1 & 2 & 2^n - 0 \\ 2 & 3 & 2^n - 1 \\ 3 & 5 & 2^n - 3 \\ 4 & 8 & 2^n - 8 \\ 5 & 13 & 2^n - 18 \\ 6 & 21 & 2^n - 43 \\ \end{array}$$

Les mathématiques qui me donneront une limite exacte me dépassent. Évidemment, est une limite supérieure, bien qu'elle ne soit pas particulièrement serrée.$O(2^n)$

Des suggestions sur ce que je devrais essayer?

Je ne suis donc pas complètement sûr, mais je pense que vous demandez de compter le nombre de chaînes de taille (sur l'alphabet ) où le facteur / sous-chaîne n'apparaît pas non?$n$$\{a, b\}$$aa$

Dans ce cas, vous pouvez adopter quelques approches combinatoires. Yuval et ADG ont tous deux donné des arguments plus simples et plus intuitifs, je suggère donc de vérifier leurs réponses! Voici l'un de mes favoris, c'est un peu étrange, mais c'est une approche très générale (et plutôt amusante).

Commençons par un langage plus simple, celui des mots qui commence et se termine par (également sans sous-chaîne de ). Nous pouvons regarder une chaîne admissible (par exemple ) comme une liste de séquences de s séparées par singulier s. Cela donne la construction: Maintenant, comment comptons-nous les phrases qui appartiennent à cette langue?$b$$aa$$bbb\textbf{a}b\textbf{a}bbbb$$b$$a$

$$w = (b^+a)^*b^+$$

Imaginons que nous développons ces expressions. Que signifie ? Eh bien, c'est simplement Maintenant, cela n'aura que très peu de sens, mais imaginons que soit une variable sur un champ numérique. En particulier, nous traiterons , et . Cela dit alors que Essayons de voir la motivation derrière cette étrange interprétation. Il s'agit presque d' une transformation bijective. En particulier, nous voulons conserver le nombre de chaque$e^*$

$$e^* = \epsilon \mid e \mid ee \mid eee \mid eeee \mid \dots$$ $e$$\epsilon \to 1$$a \mid b \to a + b$$abc \to a \times b \times c$ $$e^* \to 1 + e + ee + eee + \dots$$ $e^n$mot, comme vous pouvez facilement le voir, nous le faisons. Cependant, il existe une différence cruciale entre les expressions de chaîne et les expressions numériques: la multiplication (concaténation en chaînes, en expressions numériques) est désormais commutative! Intuitivement, la commutativité nous permet de traiter toutes les permutations du même mot comme les mêmes; c'est-à-dire que nous ne faisons pas de entre l'expression et ; ils représentent tous les deux une chaîne avec 4 s et une . Par conséquent, cette transformation nous permet de conserver le décompte de chaque mot d'un certain nombre de et s, mais elle nous permet désormais de fermer les yeux sur les détails superflus dont nous ne nous soucions pas.$\times$$bbbab$$bbabb$$b$$a$$a$$b$

Si vous revenez au précalcul, vous pourriez reconnaître cette série comme $\frac{1}{1 - e}$. Je sais que cela n'a aucun sens de réécrire cette expression régulière en tant que fonction à valeur numérique, mais juste à nu avec moi pendant un moment.

De même, $e^+ = ee^* \to \frac{e}{1 - e}$. Ce qui signifie que nous pouvons traduire$w$ dans

$$w \to \frac{1}{1 - (\frac{b}{1 - b} \times a)} \times \frac{b}{1 - b}$$

À son tour, nous pouvons simplifier cela jusqu'à

$$w(a, b) = b \times \frac{1}{1 - (b + ba)}$$

Cela nous dit que la langue $w$est isomorphe à la langue (dont la traduction directe est déjà ) sans jamais avoir recours à des outils théoriques de la langue! C'est l'un des pouvoirs de traiter ces séries comme des fonctions de forme fermée: nous pouvons y effectuer des simplifications qui sont presque impossibles à réaliser autrement, ce qui les réduit à un problème plus simple.$b(b \mid ab)^*$$\frac{b}{1 - b - ba}$

Maintenant, si vous vous souvenez encore de l'un de vos cours de calcul, vous vous souviendrez que certains types de fonctions (qui se comportent assez bien) admettent ces représentations en série appelées extensions de Taylor. Ne vous inquiétez pas, nous n'aurons pas vraiment à nous soucier de ces embêtants problèmes Calc 1; Je souligne simplement que ces fonctions peuvent être représentées comme la somme pour que donne le nombre de mots satisfaisant tel qu'il ait exactement occurrences de et occurrences de

$$\begin{align*} w(a, b) &= \sum_{i,j} w_{ij} a^i b^j \end{align*}$$ $w_{ij}$$w$$i$$a$$j$$b$ . Cependant, nous ne nous soucions pas particulièrement de savoir si quelque chose est un$a$ ou un $b$. Nous nous soucions plutôt du nombre total de caractères dans la chaîne. Pour fermer les yeux entre$a$ et $b$, nous pouvons juste (littéralement) les traiter de la même façon, par exemple $z = a = b$ et obtenir $$w(z) = w(z, z) = \frac{z}{1 - z - z^2} = \sum_k w_k z^k$$

où $w_k$ compte le nombre de mots de longueur satisfaisable $k$.

Il ne reste plus qu'à trouver $w_k$. L'approche combinatoire habituelle ici serait de décomposer cette fonction rationnelle en sa fraction partielle: c'est-à-dire, étant donné le dénominateur$1 - z - z^2 = (z - \phi)(z - \psi)$, nous pouvons réécrire $\frac{z}{(z - \phi)(z - \psi)} = \frac{A}{z - \phi} + \frac{B}{z - \psi}$(Il y a un peu d'algèbre impliqué ici, mais c'est une propriété universelle des fonctions rationnelles (un polynôme en divisant un autre)). Pour résoudre ce problème, vous pouvez refactoriser

$$\frac{A}{z - \phi} + \frac{B}{z - \psi} = \frac{z}{(z - \phi)(z - \psi)}$$ qui génère les contraintes $A + B = 1, A\psi + B\phi = 0$. Indépendamment de quoi$A$ et $B$ sont, rappelez-vous que $\frac{1}{1 - x} = 1 + x + x^2 + \dots$on peut réorganiser $$\begin{align*} w(z) &= \frac{-A}{\phi - z} + \frac{-B}{\psi - z} \\ &= (-A\phi)\frac{1}{1 - \frac{z}{\phi}} + (-B\psi) \frac{1}{1 - \frac{z}{\psi}} \\ &= (-A\phi)\left(1 + \phi^{-1} z + \phi^{-2} z^2 + \dots\right) + (-B\psi)\left(1 + \psi^{-1} z + \psi^{-2} z^2 + \dots\right) \end{align*}$$ par conséquent $$w_k = (-A\phi)\phi^{-k} + (-B\psi)\psi^{-k}$$ Ici, $\phi$ est le nombre d'or $\frac{1 + \sqrt{5}}{2}$ et $\psi = -\phi^{-1}$est son conjugué. Nous avons alors une description facile du comportement asymptotique du$w$ langue: il s'exécute dans $\Theta(\phi^n)$. En fait, si vous développez tout, vous constaterez que $$w_k = \frac{\phi^{k} - \psi^{k}}{\sqrt{5}} = \left\lceil \frac{\phi^{k}}{\sqrt{5}} \right\rceil$$ Il existe également une connexion complexe à une autre classe combinatoire commune. Ce ne sont que les chiffres de Fibonacci!

Maintenant, supposons que vous ayez $w_k$, qui compte le nombre de chaînes de taille $k$ qui commence et se termine par $k$ (et ne contient pas non plus $aa$ sous-chaînes), comment pouvons-nous construire une chaîne qui peut commencer ou se terminer par un $a$? Eh bien, c'est simple: une chaîne admissible est soit dans$w$ (commence et se termine par $b$), ou c'est $a w$ (commence avec $a$), ou c'est $w a$ (se termine par $a$), ou c'est $a w a$ (commence et se termine par $a$). Donc:

$$f(n) = w_n + w_{n-2} + 2 * w_{n - 1}$$ Rappeler que $w_n$ est la séquence fibonacci, donc $w_{n-1} + w_{n-2} = w_n$, ce qui signifie que $$\begin{align*} f(n) &= (w_n + w_{n-1}) + (w_{n-2} + w_{n-1}) \\ &= w_{n+1} + w_{n} \\ &= w_{n+2} \end{align*}$$ Donc, $f(n) = \text{fib}(n + 2) = \left\lceil \frac{\phi^{n+2}}{\sqrt{5}} \right\rceil$

Maintenant, vous n'avez probablement pas besoin de faire cette analyse, mais le simple fait de savoir que cette séquence est une séquence de Fibonacci décalée devrait vous donner une idée d'autres interprétations combinatoires que vous pouvez essayer.

La réponse de Lee Gao est excellente. Voici un compte différent. Considérez l'automate suivant:

Il s'agit d'un automate fini sans ambiguïté (UFA) sans$\epsilon$transitions: un NFA tel que chaque mot a exactement un chemin d'acceptation. Le nombre de mots de longueur$n$ est donc le nombre de chemins de longueur $n$ de l’état de départ à l’état d’acceptation (car il n’existe pas de $\epsilon$ transitions).

Nous pouvons compter le nombre de chemins dans un graphe en utilisant l'algèbre linéaire. Laisser$M$être la matrice de transition de l'automate:$M(q_i,q_j)$ est le nombre de flèches de $q_j$ à $q_i$(chaque flèche est associée à un seul symbole). alors

$$M^2(q_i,q_j) = \sum_k M(q_i,q_k) M(q_k,q_j),$$ qui est exactement le nombre de chemins de longueur 2 à partir de $q_j$ à $q_i$. De même,$M^n(q_i,q_j)$ est le nombre de chemins de longueur $n$ de $q_j$ à $q_i$. Dans notre cas, nous voulons compter le nombre de chemins de longueur$n$ de $q_0$ à $\{q_0,q_1\}$, et donc $$f(n) = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} \, .$$ La façon standard de calculer une telle expression est de diagonaliser $M$ (ou, plus généralement, en calculant la forme jordanienne de $M$). Les valeurs propres de$M$ sont facilement calculés pour être $\frac{1 \pm \sqrt{5}}{2}$, et donc pour une matrice $P$, $$\begin{align*} f(n) &= \begin{pmatrix} 1 & 1 \end{pmatrix} P \begin{pmatrix} \left(\frac{1+\sqrt{5}}{2}\right)^n & 0 \\ 0 & \left(\frac{1-\sqrt{5}}{2}\right)^n \end{pmatrix} P^{-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ &= A \left(\frac{1+\sqrt{5}}{2}\right)^n + B \left(\frac{1-\sqrt{5}}{2}\right)^n, \end{align*}$$ pour certains coefficients $A,B$. Déterminer$A,B$ on peut soit diagnostiquer $M$ explicitement, ou tout simplement mettre en place un système linéaire en utilisant des valeurs connues de $f$. Depuis$f(0) = 1$ et $f(1) = 2$, cette dernière approche montre que $$A + B = 1 \\ \frac{1+\sqrt{5}}{2} A + \frac{1-\sqrt{5}}{2} B = 2$$ En résolvant ce système (par exemple en utilisant l'élimination gaussienne), nous découvrons que $A = \frac{5+3\sqrt{5}}{10}$ et $B = \frac{5-3\sqrt{5}}{10}$. Donc $$\begin{align*} f(n) &= \frac{5+3\sqrt{5}}{10} \left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{5-3\sqrt{5}}{10} \left(\frac{1-\sqrt{5}}{2}\right)^n \\ &= \Theta(\lambda_{\max}^n), \text{ where } \lambda_{\max} = \frac{1+\sqrt{5}}{2}. \end{align*}$$ La même approche fonctionne pour chaque langue régulière.

@Lee Gao est trop complexe (je n'ai même pas tout lu), voici une approche simpliste:

Soit f (n) toutes les chaînes souhaitées parmi lesquelles a (n) les chaînes se terminant en a et b (n) les chaînes se terminant en b.

Maintenant, pour chaque chaîne qui se termine par b, nous pouvons ajouter directement a pour obtenir ba en fin et une chaîne valide:

$$a(n)=b(n-1)\tag{1}$$ Notez que nous ne pouvons pas ajouter un à la fin des chaînes qui se terminent par un sinon nous aurons un aa à la fin.

Nous pouvons ajouter b à n'importe quelle chaîne:

$$b(n)=a(n-1)+b(n-1)\tag{2}$$

Maintenant $n\mapsto n-1$ dans $(1)$ et remplacer dans $(2)$:

$$b(n)=b(n-2)+b(n-1)$$ Donc b (n) est fib (n) et puisque a (n) est b (n-1), donc a (n) est fib (n-1). Maintenant f (n) est: $$f(n)=a(n)+b(n)={\rm fib}(n)+{\rm fib}(n-1)={\rm fib}(n+1)$$ Comme fib (n) est $(\varphi^n-\varphi^{-n})/\sqrt{5}$, donc f (n) est ${\rm O}(\varphi^n)$, $\varphi=\frac{1+\sqrt{5}}{2} \approx 1.618$. (Prise$\varphi/\sqrt5$ aussi constant et négligent $\varphi^{-n}$ pour grand $n$ pour obtenir une asymptote)

Remarque: fib (0) = 0, fib (1) = 1.