Interval variety: Difference between revisions

Line 21:

{{Proof|contents=We prove this by dividing this word into four overlapping noncircular subwords which cover all cases.

Consider the subwords '''0123'''...('''''n''-2''')('''''n''-1''') and ('''''n''-1''')('''''n''-2''')...'''3210'''. If we treat ~~there~~ two words as noncircular, then there are ''n''-''k'' distinct ''k''-letter subwords.

Consider the subwords '''0123'''...('''''n''-2''')('''''n''-1''') and ('''''n''-1''')('''''n''-2''')...'''3210'''. If we treat these two words as noncircular, then there are ''n''-''k'' distinct ''k''-letter subwords.

Now consider the ''k''-letter noncircular subword ('''r-1''')('''r-2''')...'''210012'''...('''s-2''')('''s-1'''), where ''r'', ''s'' ≥ 1~~, which is a subword that strictly intersects the middle of the original word~~. Note that interchanging ''r'' and ''s'' yields equivalent subwords. If ''k'' is odd, there are (''k''-1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' ≥ ''k''.

Now consider the ''k''-letter noncircular subword ('''r-1''')('''r-2''')...'''210012'''...('''s-2''')('''s-1'''), where ''r'', ''s'' ≥ 1. Note that interchanging ''r'' and ''s'' yields equivalent subwords. If ''k'' is odd, there are (''k''-1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' ≥ ''k''.

A similar thing goes with ('''''n''-''r''-1''')...('''''n''-2''')('''''n''-1''')('''''n''-2''')..('''''n''-''s''-1'''). If ''k'' is odd, there are (''k''+1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' - 1 ≥ ''k''.

@@ Line 21: / Line 21: @@
 {{Proof|contents=We prove this by dividing this word into four overlapping noncircular subwords which cover all cases.
-Consider the subwords '''0123'''...('''''n''-2''')('''''n''-1''') and ('''''n''-1''')('''''n''-2''')...'''3210'''. If we treat there two words as noncircular, then there are ''n''-''k'' distinct ''k''-letter subwords.
+Consider the subwords '''0123'''...('''''n''-2''')('''''n''-1''') and ('''''n''-1''')('''''n''-2''')...'''3210'''. If we treat these two words as noncircular, then there are ''n''-''k'' distinct ''k''-letter subwords.
-Now consider the ''k''-letter noncircular subword ('''r-1''')('''r-2''')...'''210012'''...('''s-2''')('''s-1'''), where ''r'', ''s'' ≥ 1, which is a subword that strictly intersects the middle of the original word. Note that interchanging ''r'' and ''s'' yields equivalent subwords. If ''k'' is odd, there are (''k''-1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' ≥ ''k''.
+Now consider the ''k''-letter noncircular subword ('''r-1''')('''r-2''')...'''210012'''...('''s-2''')('''s-1'''), where ''r'', ''s'' ≥ 1. Note that interchanging ''r'' and ''s'' yields equivalent subwords. If ''k'' is odd, there are (''k''-1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' ≥ ''k''.
 A similar thing goes with ('''''n''-''r''-1''')...('''''n''-2''')('''''n''-1''')('''''n''-2''')..('''''n''-''s''-1'''). If ''k'' is odd, there are (''k''+1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' - 1 ≥ ''k''.