最长的例外序列，求证。

第8个小笼包

原帖由 lulijie 于 2009-1-31 23:06 发表
本序列为例外序列     AAABAACABBABCACBACCBBBCBCCCAA
可以按字典的方法排列。
4*4的按字典顺序排列最前的是：
AAAABAAACAAADAABBAABCAABDAACBAACCAACDAADBAADCAADDABABACABAD
ABBBABBCABBDABCBABCCABCDABDBABDC ...

在出现完AAAD以后，为什么是接AABB而不是AABA呢？

lulijie

请看30#的说明，因为前面已经有了

第8个小笼包

你这样要不断检查之前出现的组合，是算一种计算机算法吧，不太像证明的思路。

第8个小笼包

对了，以3×3的为例，以AAA排首位，再以AA结尾，中间再有一个AA连续。然后对于B和C来说，都在序列的中间了，而且只有连续的BBB，BB，CCC，CC各一个而已，剩下的就是单独的两个A，B和C个四个，这样来插入排序的方法不知可行否？

ursace

用归纳法怎么样

第8个小笼包

有点困难，问题是在于组合的数多了一个以后排列的顺序全部不一样了，很难使用第一和第二归纳法

lulijie

感谢TLTV，感谢CCTV，最主要的是感谢35＃LV
你的提议有如深夜中的一声惊雷，震醒了在黑暗中艰难摸索的我们。我要继承你的提议，完成你未尽的事业，完成用数学归纳法来证明的壮举。
m*n序列（m>=n)，字母m个，组合长度n个，那么例外序列的最大长度为m^n+n-1。
对于长度为m^n+n的序列中可选择的组合有m^n+1个，而组合总共只有m^n，所以必有两个组合相同，所以它肯定不是例外序列。
下面我们证明m^n+n-1长度的序列必定存在例外序列：
我们用P(k)表示长度为k的序列。
第一步：k=n+1 时，P(k)存在例外序列。
      显然，由n个A和1个B组成的序列就满足条件。
第二步：假设k=i 时，P(k)存在例外序列，那么P(k+1)也存在例外序列。（i<m^n+n-1）
      对于长度为i的例外序列，假设其末尾n-1个字母是字符串S，
      那么如果在该序列中，字符串S除了末尾的外只出现m-1次，那么必然可以在末尾加上一个字母，使它仍然是例外序列。（因为以字符串S开头，n长度的组合共有m种）。            
      而如果在该序列中字符串S除了末尾的外出现m次，那么就不能在末尾加上任何字母使得它成为例外序列，这种情况，该序列必然是字符串S开头。（因为以字符串S结尾，n长度的组合共有m种，该序列包括尾部的字符串S，总共出现m+1，所以必有一个出现在头部）。我们去掉尾部的字符串S，首尾相接，就构成长度为i-n+1的例外环。在这个环中，假设存在一个子字符串Z（长度为n-1），它在该环中最多只出现m-1次，那么我们从Z的前面剪开环，在尾部加上字符串Z，得到长度为i的新的序列，该序列必定是例外序列。由于除了尾部的字符串Z外，字符串Z只在该序列中出现m-1次，所以必定可在尾部加上一个字母，使其仍然是例外序列，我们就得到长度为i+1的例外序列。
      那么在环中任何一个长度为n-1的子字符串都至少出现m次以上的情况，存不存在呢。
      假设存在，比如字符串Z，出现了m次，那么那么该字符串加上在它后面的字母组成长度为n的组合也有m个，由于它们都是由字符串Z开头，而该环又是例外环，所以它们是相互不同的组合，它们尾部的字母必定不相同。也就是说所有的可能字母（m个）全部出现。对于字母A来说，假设它前面的n-2个字母与它构成字符串Y，那么Y也在该环中出现m次，所以字母A在该环中至少出现了m次。同理，对于其他任何字母，也都出现了至少m次,所以该环的长度至少为m^m，由于m>=n,所以该环的长度必定大于或等于m^n，所以i>＝m^n+n-1。这与第二步的假设（i<m^n+n-1）相矛盾。
综上所述，假设k=i 时，P(k)存在例外序列，那么P(k+1)也存在例外序列。（i<m^n+n-1）。
所以i＝m^n+n-1时，也存在例外序列。
－－－－－－－－－－－－－－－－－－－－－－－－－－
因此  例外序列的最大长度为m^n+n-1。

---------------------------------------------------------------------------------------
上述红字部分有错误，谢谢42#指出。

[ 本帖最后由 lulijie 于 2009-2-5 21:28 编辑 ]

第8个小笼包

原帖由 第8个小笼包 于 2009-1-31 21:14 发表
很好，这个方法显然可以推广到N个情形，第一步已经完成，假设存在最长例外数列，则一定形成一个环状。而且你不必假设AAA出现在首位，如果出现在中间，我们可以把它切断，然后把多余的补到新数列的最后。

-------- ...

还是不要用截取的方法，不一定能保证形成最长序列，用分类讨论吧，AAA在序列的边上已经证完，由于BC地位一样，不妨设AAB在序列的边上，方法一样，还剩下4个带AA的组合，其中在中间的AAA独占3分，所以，只剩下一个带AA的组合在序列的另一边。还有一种情况，同理，不妨设AB在边上，带AB的组合总共有6个，除了序列边上的还剩5个，中间的每个AB组合各占2个，所以一定纯在一个带AB的组合在序列的另一边。所有情况讨论完毕。这个方法同样可以推广到N个的情形。

lulijie

那么当n>m时，在环中任何一个长度为n-1的子字符串都至少出现m次以上的情况，存不存在呢。
假设存在，因为长n-1的子字符串总可能数有m^(n-1)种，
        如果环中所有可能的长n-1的子字符串都出现，那么因为每种字符串都出现m次，所以环中以该字符串为开头的长度为n的字符串也都出现m次，由于它是例外环，所以它们都不相同。因为m^(n-1)种字符串，每种都出现了m次，所以环中长n的字符串也出现了m^(n-1) * m=m^n次，所以环长度最少为m^n次，所以序列的长度i最少为m^n+n-1，与假设矛盾。
        所以环中所有可能的长n-1的子字符串至少有一个未出现，那么假设该未出现的子字符串为U，前n-2个字母组成字符串R，末尾字母为y：
        那么在该环中，如果在环中字符串R出现，就将环在字符串R的尾部剪开，让这个序列以R为尾，在该新序列头部加上与尾部n-1个字母相同的字符串，在尾部加上y，就得到长度为i+1的新的序列,它是例外序列。
        如果在该环中，字符串R未出现。那么就设U的前n-3个字母组成字符串R1，后2个字母组成字符串y1，在环中找R1，找到R1，在其尾部剪开，让这个序列以R1为尾，在该新序列头部加上与尾部n-1个字母相同的字符串，在尾部加上y1，就得到长度为i+1的新的序列,它是例外序列。若找不到，就按该段的方法一直往前找，直到Rx为1个字母为止，肯定能找到，也按照该方法剪开加上，得到长i+1的例外序列。
－－－－－－－－－－－－－－－－－－
所以n>m时，题目也成立。

lulijie

按照数学归纳法的证明精神：从一个给定的例外序列，可以按照以下构造方法，让它不断增长，直到达到最长长度。
m* n一般情况。
第一步：在序列中检查末尾n-1个字符构成的字符串，若除末尾外，最多找到m-1处，那么肯定能在末尾加上一个字符，使得它是例外序列。
第二步：若找到m次，那么，其头n-1个字符与尾n-1个字符必定相等，将尾部这n-1个字符剪掉，使头尾相接成为环。
第三步：在环中找只出现m-1次或以下次的长度为n-1的字符串，找到，在其尾部剪断，在头部加上该字符串，得到新序列，其与原序列等长，那么肯定能在其末尾加上一个字符，使得它是例外序列。
第四步：若环中所有长n-1的字符串都出现m次，那么肯定是n>m的情况，那么至少有一种长度为n-1的字符串不在环中出现，称它为字符串S，然后在环中找S的前面部分字符串（长度从n-2一直到找到1），找到后就在其尾部剪断，在头部加上剪断后新序列的末尾n-1个字符，尾部添加一定长度的字符串，使得其末尾字符串为S，这样得到的序列就是增长的例外序列。