Fraenkel word: Difference between revisions

Line 44:

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

{{theorem|name=Lemma|contents=Let ''G''''n'' denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of ''G''''n'' such that ''w'' = ''uv'' where ''u'' is a nonempty suffix of ''F''''n'' and ''v'' is a nonempty prefix of ''F''''n''. For 1 ≤ {{!}}''w''{{!}} ≤ 2''n''/2 − 2, either {{!}}''w''{{!}}'''i''' = ceil({{!}}''w''{{!}}/2''i''+1) or ceil({{!}}''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 ''w'' = ''uv'' where ''u'' is a nonempty suffix of ''F''''n'' and ''v'' is a nonempty prefix of ''F''''n''. For 1 ≤ {{!}}''w''{{!}} ≤ 2''n''/2 − 2, either {{!}}''w''{{!}}'''i''' = ceil({{!}}''w''{{!}}/2''i''+1) or ceil({{!}}''w''{{!}}/2''i''+1) − 1.

}}

@@ Line 44: / Line 44: @@
 {{proof|contents=We use the previous lemma. In the first case, ''w'' is guaranteed to have exactly ''k''-many '''i'''s where {{!}}''w''{{!}} = ''k''2<sup>''i''+1</sup>. In the second case, if ''k''2<sup>''i''+1</sup> < {{!}}''w''{{!}} < (''k'' + 1)2<sup>''i''+1</sup> and ''w'' = ''uv'' or ''vu'' where {{!}}''u''{{!}} ≡ 0 mod 2<sup>''i''+1</sup>,  then ''u'' satisfies {{!}}''u''{{!}}<sub>'''i'''</sub> = ''k''2<sup>''i''+1</sup>/2<sup>''i''+1</sup> = ''k'' by the previous case. Thus {{!}}''w''{{!}}<sub>'''i'''</sub>  is determined by {{!}}''v''{{!}}<sub>'''i'''</sub>, which is 1 if ''v'' contains the '''i''' in the middle of ''F''<sub>''i''</sub>, implying {{!}}''w''{{!}}<sub>'''i'''</sub> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>), and 0 otherwise, implying {{!}}''w''{{!}}<sub>'''i'''</sub> = floor({{!}}''w''{{!}}/2<sup>''i''+1</sup>).}}
-{{theorem|name=Lemma|contents=Let ''G''<sub>''n''</sub> denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of ''G''<sub>''n''</sub> such that ''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 1 &le; {{!}}''w''{{!}} &le; 2<sup>''n''/2</sup> &minus; 2, either {{!}}''w''{{!}}<sub>'''i'''</sub> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) or ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) &minus; 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 ''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 1 &le; {{!}}''w''{{!}} &le; 2<sup>''n''/2</sup> &minus; 2, either {{!}}''w''{{!}}<sub>'''i'''</sub> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) or ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) &minus; 1.
 }}