Fraenkel word: Difference between revisions

(2 intermediate revisions by 2 users not shown)

Line 2:

<math>\displaystyle{

\begin{align*}

\begin{aligned}

F_0 &= \epsilon, \\

F_1 &= \mathbf{0}, \\

Line 9:

&\ \ \vdots \\

F_{n} &= F_{n-1}(\mathbf{n-1})F_{n-1},

\end{align*}}

\end{aligned}}

</math>

Line 17:

== Facts ==

Below we denote the length of a word ''w'' by {{abs|''w''}} and the number of occurrences of the letter '''i''' in ''w'' as {{abs|''w''}}'''i''', as is standard notation in combinatorics on words. The notation ''w''(''u''0, ..., {{nowrap|''u''''r'' − 1}}) represents the word ''w'' in '''0''', '''1''', ..., {{nowrap|'''r − 1'''}} but with '''i''' replaced by the word ''u''''i''.

Below we denote the length of a word ''w'' by {{abs|''w''}} and the number of occurrences of the letter '''i''' in ''w'' as {{abs|''w''}}'''i''', as is standard notation in combinatorics on words. The notation ''w''(''u''0, ..., {{nowrap|''u''''r'' − 1}}) represents the word ''w'' in '''0''', '''1''', ..., {{nowrap|'''''r'' − 1'''}} but with '''i''' replaced by the word ''u''''i''.

=== Fraenkel words are balanced ===

Line 39:

{{theorem|name=Lemma|contents=For all {{nowrap|''n'' ≥ 1|0 ≤ ''i'' ≤ ''n'' − 1}}, and {{nowrap|1 ≤ {{abs|''w''}} ≤ 2''n''/2 − 2}}, the following holds for any subword ''w'' of ''F''''n'':

# If {{nowrap|{{abs|''w''}} ≡ 0 (mod 2''i'' + 1)}}, then {{nowrap|{{abs|''w''}}'''i''' {{=}} {{abs|''w''}}/2''i'' + 1}}.

# If {{nowrap|{{abs|''w''}} ≢ 0 (mod 2''i'' + 1)}}, then {{abs|''w''}}'''i''' {{=}} either {{nowrap|{{floor|{{abs|''w''}}/2''i'' + 1}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2''i'' + 1}}}}.

# If {{nowrap|{{abs|''w''}} ≢ 0 (mod 2''i'' + 1)}}, then {{abs|''w''}}'''i''' {{=}} either {{nowrap|{{floor|{{abs|''w''}}/2''i'' + 1|1.75}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2''i'' + 1|1.75}}}}.

#* More precisely, if for a given ''i'' we have {{nowrap|''w'' {{=}} ''uv''}} or ''vu'' where ''u'' is a possibly empty word whose length is {{nowrap|0 (mod 2''i'' + 1)}}, and ''v'' is a nonempty word intersecting the middle of an {{nowrap|''F''''i'' + 1}}, then {{nowrap|{{abs|''w''}}'''i''' {{=}} {{ceil|{{abs|''w''}}/2''i'' + 1}}}}. Otherwise, {{nowrap|{{abs|''w''}}'''i''' {{=}} {{floor|{{abs|''w''}}/2''i'' + 1}}}}.

#* More precisely, if for a given ''i'' we have {{nowrap|''w'' {{=}} ''uv''}} or ''vu'' where ''u'' is a possibly empty word whose length is {{nowrap|0 (mod 2''i'' + 1)}}, and ''v'' is a nonempty word intersecting the middle of an {{nowrap|''F''''i'' + 1}}, then {{nowrap|{{abs|''w''}}'''i''' {{=}} {{ceil|{{abs|''w''}}/2''i'' + 1|1.75}}}}. Otherwise, {{nowrap|{{abs|''w''}}'''i''' {{=}} {{floor|{{abs|''w''}}/2''i'' + 1|1.75}}}}.

}}

{{proof|contents=We use the previous lemma. In the first case, ''w'' is guaranteed to have exactly ''k''-many '''i'''s where {{abs|''w''}} = ''k''2''i'' + 1. In the second case, if ''k''2''i'' + 1 < {{abs|''w''}} < (''k'' + 1)2''i'' + 1 and ''w'' = ''uv'' or ''vu'' where {{abs|''u''}} ≡ 0 mod 2''i'' + 1, then ''u'' satisfies {{abs|''u''}}'''i''' = ''k''2''i'' + 1/2''i'' + 1 = ''k'' by the previous case. Thus {{abs|''w''}}'''i''' is determined by {{abs|''v''}}'''i''', which is 1 if ''v'' contains the '''i''' in the middle of ''F''''i'', implying {{abs|''w''}}'''i''' = {{ceil|{{abs|''w''}}/2''i'' + 1}}, and 0 otherwise, implying {{abs|''w''}}'''i''' = floor({{abs|''w''}}/2''i'' + 1).}}

{{proof|contents=We use the previous lemma. In the first case, ''w'' is guaranteed to have exactly ''k''-many '''i'''s where {{abs|''w''}} = ''k''2''i'' + 1. In the second case, if ''k''2''i'' + 1 < {{abs|''w''}} < (''k'' + 1)2''i'' + 1 and ''w'' = ''uv'' or ''vu'' where {{abs|''u''}} ≡ 0 mod 2''i'' + 1, then ''u'' satisfies {{abs|''u''}}'''i''' = ''k''2''i'' + 1/2''i'' + 1 = ''k'' by the previous case. Thus {{abs|''w''}}'''i''' is determined by {{abs|''v''}}'''i''', which is 1 if ''v'' contains the '''i''' in the middle of ''F''''i'', implying {{abs|''w''}}'''i''' = {{ceil|{{abs|''w''}}/2''i'' + 1|1.75}}, and 0 otherwise, implying {{abs|''w''}}'''i''' = floor({{abs|''w''}}/2''i'' + 1).}}

{{theorem|name=Lemma|contents=Let [''F''''n''] denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of [''F''''n''] such that {{nowrap|''w'' {{=}} ''uv''}} where ''u'' is a nonempty suffix of ''F''''n'' and ''v'' is a nonempty prefix of ''F''''n''. For {{nowrap|1 ≤ {{abs|''w''}} ≤ 2''n''/2 − 2}}, either {{nowrap|{{abs|''w''}}'''i''' {{=}} {{ceil|{{abs|''w''}}/2''i'' + 1}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2''i'' + 1}} − 1}}.

{{theorem|name=Lemma|contents=Let [''F''''n''] denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of [''F''''n''] such that {{nowrap|''w'' {{=}} ''uv''}} where ''u'' is a nonempty suffix of ''F''''n'' and ''v'' is a nonempty prefix of ''F''''n''. For {{nowrap|1 ≤ {{abs|''w''}} ≤ 2''n''/2 − 2}}, either {{nowrap|{{abs|''w''}}'''i''' {{=}} {{ceil|{{abs|''w''}}/2''i'' + 1|1.75}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2''i'' + 1|1.75}} − 1}}.

}}

Line 52:

# Both {{abs|''u''}} and {{abs|''v''}} are {{nowrap|0 (mod 2''i'' + 1)}}.

# At least one of {{abs|''u''}} and {{abs|''v''}} is not {{nowrap|0 (mod 2''i'' + 1)}}.

In case 1, by the preceding lemma {{nowrap|{{abs|''u''}}'''i''' {{=}} {{abs|''u''}}/2''i'' + 1}} and {{nowrap|{{abs|''v''}}'''i''' {{=}} {{abs|''v''}}/2''i'' + 1}}, and hence {{nowrap|{{abs|''w''}}'''i''' {{=}} {{abs|''w''}}/2''i'' + 1}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2''i'' + 1}}}}.

In case 1, by the preceding lemma {{nowrap|{{abs|''u''}}'''i''' {{=}} {{abs|''u''}}/2''i'' + 1}} and {{nowrap|{{abs|''v''}}'''i''' {{=}} {{abs|''v''}}/2''i'' + 1}}, and hence {{nowrap|{{abs|''w''}}'''i''' {{=}} {{abs|''w''}}/2''i'' + 1}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2''i'' + 1|1.75}}}}.

In case 2, suppose {{nowrap|''w'' {{=}} ''ustv''}} where ''st'' is as in case 1 and {{abs|''u''}} and {{abs|''v''}} are less than {{nowrap|2''i'' + 1}}. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''''i''. Using {{nowrap|{{abs|''st''}} {{=}} {{abs|''st''}}'''i'''2''i'' + 1}}, we have

Line 60:

thus

{{nowrap|{{abs|''w''}}'''i''' ≥ {{abs|''st''}}'''i'''}} {{nowrap|{{=}} {{abs|''st''}}/2''i'' + 1}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2''i'' + 1}} − 1}}.

{{nowrap|{{abs|''w''}}'''i''' ≥ {{abs|''st''}}'''i'''}} {{nowrap|{{=}} {{abs|''st''}}/2''i'' + 1}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2''i'' + 1|1.75}} − 1}}.

On the other hand, {{nowrap|{{abs|''w''}}'''i''' < {{ceil|{{abs|''w''}}/2''i'' + 1}}}}, lest ''u'' or ''v'' have an '''i'''. Therefore {{nowrap|{{abs|''w''}}'''i''' {{=}} {{ceil|{{abs|''w''}}/2''i'' + 1}} − 1}}.

On the other hand, {{nowrap|{{abs|''w''}}'''i''' < {{ceil|{{abs|''w''}}/2''i'' + 1|1.75}}}}, lest ''u'' or ''v'' have an '''i'''. Therefore {{nowrap|{{abs|''w''}}'''i''' {{=}} {{ceil|{{abs|''w''}}/2''i'' + 1|1.75}} − 1}}.

}}

Line 77:

<math>\displaystyle{

\begin{align*}

\begin{aligned}

G_0 &= \epsilon, \\

G_1 &= \mathbf{0}, \\

Line 84:

&\ \ \vdots \\

G_{n} &= G_{n-1}(\mathbf{n-1})G_{n-1}(\mathbf{n-1})G_{n-1}.

\end{align*}}

\end{aligned}}

</math>

Line 100:

[[Category:Terms]]

[[Category:Combinatorics on words]]

~~[[Category:Math]]~~

[[Category:Pages with open problems]]

@@ Line 2: / Line 2: @@
 <math>\displaystyle{
-\begin{align*}
+\begin{aligned}
 F_0 &= \epsilon, \\
 F_1 &= \mathbf{0}, \\
@@ Line 9: / Line 9: @@
 &\ \ \vdots \\
 F_{n} &= F_{n-1}(\mathbf{n-1})F_{n-1},
-\end{align*}}
+\end{aligned}}
 </math>
@@ Line 17: / Line 17: @@
 == Facts ==
-Below we denote the length of a word ''w'' by {{abs|''w''}} and the number of occurrences of the letter '''i''' in ''w'' as {{abs|''w''}}<sub>'''i'''</sub>, as is standard notation in combinatorics on words. The notation ''w''(''u''<sub>0</sub>, ..., {{nowrap|''u''<sub>''r'' − 1</sub>}}) represents the word ''w'' in '''0''', '''1''', ..., {{nowrap|'''r − 1'''}} but with '''i''' replaced by the word ''u''<sub>''i''</sub>.
+Below we denote the length of a word ''w'' by {{abs|''w''}} and the number of occurrences of the letter '''i''' in ''w'' as {{abs|''w''}}<sub>'''i'''</sub>, as is standard notation in combinatorics on words. The notation ''w''(''u''<sub>0</sub>, ..., {{nowrap|''u''<sub>''r'' − 1</sub>}}) represents the word ''w'' in '''0''', '''1''', ..., {{nowrap|'''''r'' − 1'''}} but with '''i''' replaced by the word ''u''<sub>''i''</sub>.
 === Fraenkel words are balanced ===
@@ Line 39: / Line 39: @@
 {{theorem|name=Lemma|contents=For all {{nowrap|''n'' &ge; 1|0 &le; ''i'' &le; ''n'' − 1}}, and {{nowrap|1 &le; {{abs|''w''}} &le; 2<sup>''n''/2</sup> − 2}}, the following holds for any subword ''w'' of ''F''<sub>''n''</sub>:
 # If {{nowrap|{{abs|''w''}} ≡ 0 (mod 2<sup>''i'' + 1</sup>)}}, then {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{abs|''w''}}/2<sup>''i'' + 1</sup>}}.
-# If {{nowrap|{{abs|''w''}} ≢ 0 (mod 2<sup>''i'' + 1</sup>)}}, then {{abs|''w''}}<sub>'''i'''</sub> {{=}} either {{nowrap|{{floor|{{abs|''w''}}/2<sup>''i'' + 1</sup>}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>}}}}.
+# If {{nowrap|{{abs|''w''}} ≢ 0 (mod 2<sup>''i'' + 1</sup>)}}, then {{abs|''w''}}<sub>'''i'''</sub> {{=}} either {{nowrap|{{floor|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}.
-#* More precisely, if for a given ''i'' we have {{nowrap|''w'' {{=}} ''uv''}} or ''vu'' where ''u'' is a possibly empty word whose length is {{nowrap|0 (mod 2<sup>''i'' + 1</sup>)}}, and ''v'' is a nonempty word intersecting the middle of an {{nowrap|''F''<sub>''i'' + 1</sub>}}, then {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>}}}}. Otherwise, {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{floor|{{abs|''w''}}/2<sup>''i'' + 1</sup>}}}}.
+#* More precisely, if for a given ''i'' we have {{nowrap|''w'' {{=}} ''uv''}} or ''vu'' where ''u'' is a possibly empty word whose length is {{nowrap|0 (mod 2<sup>''i'' + 1</sup>)}}, and ''v'' is a nonempty word intersecting the middle of an {{nowrap|''F''<sub>''i'' + 1</sub>}}, then {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}. Otherwise, {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{floor|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}.
 }}
-{{proof|contents=We use the previous lemma. In the first case, ''w'' is guaranteed to have exactly ''k''-many '''i'''s where {{abs|''w''}} = ''k''2<sup>''i'' + 1</sup>. In the second case, if ''k''2<sup>''i'' + 1</sup> < {{abs|''w''}} < (''k'' + 1)2<sup>''i'' + 1</sup> and ''w'' = ''uv'' or ''vu'' where {{abs|''u''}} ≡ 0 mod 2<sup>''i'' + 1</sup>,  then ''u'' satisfies {{abs|''u''}}<sub>'''i'''</sub> = ''k''2<sup>''i'' + 1</sup>/2<sup>''i'' + 1</sup> = ''k'' by the previous case. Thus {{abs|''w''}}<sub>'''i'''</sub>  is determined by {{abs|''v''}}<sub>'''i'''</sub>, which is 1 if ''v'' contains the '''i''' in the middle of ''F''<sub>''i''</sub>, implying {{abs|''w''}}<sub>'''i'''</sub> = {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>}}, and 0 otherwise, implying {{abs|''w''}}<sub>'''i'''</sub> = floor({{abs|''w''}}/2<sup>''i'' + 1</sup>).}}
+{{proof|contents=We use the previous lemma. In the first case, ''w'' is guaranteed to have exactly ''k''-many '''i'''s where {{abs|''w''}} = ''k''2<sup>''i'' + 1</sup>. In the second case, if ''k''2<sup>''i'' + 1</sup> < {{abs|''w''}} < (''k'' + 1)2<sup>''i'' + 1</sup> and ''w'' = ''uv'' or ''vu'' where {{abs|''u''}} ≡ 0 mod 2<sup>''i'' + 1</sup>,  then ''u'' satisfies {{abs|''u''}}<sub>'''i'''</sub> = ''k''2<sup>''i'' + 1</sup>/2<sup>''i'' + 1</sup> = ''k'' by the previous case. Thus {{abs|''w''}}<sub>'''i'''</sub>  is determined by {{abs|''v''}}<sub>'''i'''</sub>, which is 1 if ''v'' contains the '''i''' in the middle of ''F''<sub>''i''</sub>, implying {{abs|''w''}}<sub>'''i'''</sub> = {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}, and 0 otherwise, implying {{abs|''w''}}<sub>'''i'''</sub> = floor({{abs|''w''}}/2<sup>''i'' + 1</sup>).}}
-{{theorem|name=Lemma|contents=Let [''F''<sub>''n''</sub>] denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of [''F''<sub>''n''</sub>] such that {{nowrap|''w'' {{=}} ''uv''}} where ''u'' is a nonempty suffix of ''F''<sub>''n''</sub> and ''v'' is a nonempty prefix of ''F''<sub>''n''</sub>. For {{nowrap|1 &le; {{abs|''w''}} &le; 2<sup>''n''/2</sup> − 2}}, either {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>}} − 1}}.
+{{theorem|name=Lemma|contents=Let [''F''<sub>''n''</sub>] denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of [''F''<sub>''n''</sub>] such that {{nowrap|''w'' {{=}} ''uv''}} where ''u'' is a nonempty suffix of ''F''<sub>''n''</sub> and ''v'' is a nonempty prefix of ''F''<sub>''n''</sub>. For {{nowrap|1 &le; {{abs|''w''}} &le; 2<sup>''n''/2</sup> − 2}}, either {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}} − 1}}.
 }}
@@ Line 52: / Line 52: @@
 # Both {{abs|''u''}} and {{abs|''v''}} are {{nowrap|0 (mod 2<sup>''i'' + 1</sup>)}}.
 # At least one of {{abs|''u''}} and {{abs|''v''}} is not {{nowrap|0 (mod 2<sup>''i'' + 1</sup>)}}.
-In case 1, by the preceding lemma {{nowrap|{{abs|''u''}}<sub>'''i'''</sub> {{=}} {{abs|''u''}}/2<sup>''i'' + 1</sup>}} and {{nowrap|{{abs|''v''}}<sub>'''i'''</sub> {{=}} {{abs|''v''}}/2<sup>''i'' + 1</sup>}}, and hence {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{abs|''w''}}/2<sup>''i'' + 1</sup>}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>}}}}.
+In case 1, by the preceding lemma {{nowrap|{{abs|''u''}}<sub>'''i'''</sub> {{=}} {{abs|''u''}}/2<sup>''i'' + 1</sup>}} and {{nowrap|{{abs|''v''}}<sub>'''i'''</sub> {{=}} {{abs|''v''}}/2<sup>''i'' + 1</sup>}}, and hence {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{abs|''w''}}/2<sup>''i'' + 1</sup>}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}.
 In case 2, suppose {{nowrap|''w'' {{=}} ''ustv''}} where ''st'' is as in case 1 and {{abs|''u''}} and {{abs|''v''}} are less than {{nowrap|2<sup>''i'' + 1</sup>}}. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''<sub>''i''</sub>. Using {{nowrap|{{abs|''st''}} {{=}} {{abs|''st''}}<sub>'''i'''</sub>2<sup>''i'' + 1</sup>}}, we have
@@ Line 60: / Line 60: @@
 thus
-{{nowrap|{{abs|''w''}}<sub>'''i'''</sub> &ge; {{abs|''st''}}<sub>'''i'''</sub>}} {{nowrap|{{=}} {{abs|''st''}}/2<sup>''i'' + 1</sup>}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>}} − 1}}.
+{{nowrap|{{abs|''w''}}<sub>'''i'''</sub> &ge; {{abs|''st''}}<sub>'''i'''</sub>}} {{nowrap|{{=}} {{abs|''st''}}/2<sup>''i'' + 1</sup>}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}} − 1}}.
-On the other hand, {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> &lt; {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>}}}}, lest ''u'' or ''v'' have an '''i'''. Therefore {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>}} − 1}}.
+On the other hand, {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> &lt; {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}, lest ''u'' or ''v'' have an '''i'''. Therefore {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}} − 1}}.
 }}
@@ Line 77: / Line 77: @@
 <math>\displaystyle{
-\begin{align*}
+\begin{aligned}
 G_0 &= \epsilon, \\
 G_1 &= \mathbf{0}, \\
@@ Line 84: / Line 84: @@
 &\ \ \vdots \\
 G_{n} &= G_{n-1}(\mathbf{n-1})G_{n-1}(\mathbf{n-1})G_{n-1}.
-\end{align*}}
+\end{aligned}}
 </math>
@@ Line 100: / Line 100: @@
 [[Category:Terms]]
 [[Category:Combinatorics on words]]
-[[Category:Math]]
 [[Category:Pages with open problems]]

Fraenkel word: Difference between revisions

Sintel bot (talk | contribs)