这样的十进数有多少个？（排列问题）

mathe

我们假设自对称状态有$s$个，而不是自对称的有$2t$个
变换矩阵为$M$,而我们还有一个$t \times (s+2t)$阶约束矩阵$H=[(O, I, -I)]$,使得对于任意一个状态向量$v'$必然有$Hv'=0$
由于状态向量变换一次后变成$Mv'$,于是必然也有$HMv'=0,HM^2v'=0,....$
于是
$[(H),(HM),(HM^2),(HM^3),(...)]v'=0$
所以向量$v'$的维数减去矩阵
$[(H),(HM),(HM^2),(HM^3),(...)]$
的秩正好等于状态向量的实际有效维数，所以这个线性变换$M$在状态向量空间中真正的有效次数就是等于这个差值，这个也代表了递推数列的阶。
而我实际计算了K=3,4,5的情况，
矩阵$[(H),(HM),(HM^2),(HM^3),(...)]$的秩都等于矩阵$[(H),(HM)]$的秩。这个估计是$M$的所有特征值的代数重数会等于几何重数。
如果这两个秩都相等，而且按计算结果$[(H),(HM)]$列满秩那么就可以得出实际上递推数列的阶会等于对称状态的数目$s$。

我们现在假设$[(H),(HM)]$的核空间可以用矩阵$L$表示，于是$Q=[(H',M'H',L')]$是$(s+2t)\times(s+2t)$阶可逆方阵,而且$LH'=O, LM'H'=O$
于是任意一个合法的状态$v$可以写成$v=L'h'=Q[(O),(O),(h')]$. $Q^{-1}M^{n-3}v=(Q^{-1}MQ)^{n-3}[(O),(O),(h')]$
也就是说我们只要计算矩阵$Q^{-1}MQ$,然后这个方阵右下角的$s\times s$阶子方阵就是所求的降阶后的变换阵。
利用这种方法计算的K=5的特征多项式是
$(x-6)(x-1)^3(x+1)^3(x^2+1)^2(x^4+x^3-x^2+x+6)(x^4+x^3+x^2+x+6)(x^4+x^3+6*x^2+36*x+216)(x^6-x^5-5x^4+5x^3-30x^2-36x+216)(x^6+x^5+5x^4-5x^3-30x^2-36x-216)(x^8-x^7+x^6-x^5+10x^4-6x^3+x^2-6x+36)$

1. 
   
2. PT=concat(H~, (H*M)~);
   
3. L=matker(PT~);
   
4. Q=concat(PT,L);
   
5. R=Q^-1*M*Q;
   

复制代码

mathe

上面算法计算结果对于K=3是
$720[(0, -1, 7, 1, 0, 8, -1)][(-130/229,13118/229,0, 0, 0, 0, 0),(-31/229, -99/229, 0, 0, 0, 0, 0),(217/229, 464/229, 7, 1, 0, 8, -1),(-7, 0, 0, 0 ,8, 0, 7),(0, 7 ,1, 0, 0, 0, 0),(19/229, 792/229, 0 ,0, 0 ,0 ,1),(99/229, 12660/229, 7, 0, 0, 8 ,0)]^{n-3}[(0),( 0), (0), (1), (0), (0), (0)]$
然后我们只要取最后5行5列得$720[(7, 1, 0, 8, -1)][( 7, 1, 0, 8, -1),( 0, 0 ,8, 0, 7),(1, 0, 0, 0, 0),(0 ,0, 0 ,0 ,1),(7, 0, 0, 8 ,0)]^{n-3}[ (0), (1), (0), (0), (0)]$
类似K=4的结果是
$5040[(6, 1, 0, 0, -1, 5, 2, 0, 0, 0, 1, 0, 5, 0)][(0, 1, 0 ,0, 0, 0 ,1, 0, 0, 0, 0 ,0, 0, 0),(0 ,0, 7, 0, 0, 0, 0 ,6 ,0, 0, 0, 0, 0, 0),(0, 0, 0, -7/6, 0, 1/6, 0, 0, 1/6, 0, 0 ,0 ,0 ,0),(0, 0 ,0 ,0 ,0, 0, 0 ,0, 0, 0 ,1, 0, 0, 0),(0, 0, 0, 0 ,0, 5, 0, 0, 0 ,6 ,0, 0, 6, 0),(6 ,0, 0, 0, 0, 5, 0, 0, 0, 0, 1, 0 ,5, 0),(0, 0, 0, 0 ,6, 0 ,0, 7, -6, 0, 0, 6, 0, -7),(0, 0, 0 ,0 ,0 ,1 ,0 ,0 ,1, 0 ,0 ,0, 0, 0),(0 ,0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0),(0 ,0, 0, 0, 7/6, 0 ,0, 7/6 ,-1 ,0, 0, 0, 0, -7/6),(0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ,1, 0, 0),(0 ,0, 0 ,0, 0, 0 ,0 ,0, 6 ,0, 0, 0, 0 ,7),(0, 0 ,0, 0, 0, 0, 1, 0 ,0, 0, 0 ,1 ,0 ,0),(0, 0, 0, 0 ,0, 0, 0 ,0, 1, 0, 0 ,0 ,0 ,0)]^{n-4}[(0), (1),( 0),( 0), (0),( 0),( 0), (0),( 0), (0), (0), (0), (0),( 0)]$
不过实际计算可以知道矩阵最小多项式还可以降低一次(也就是$(x+1)^2$项可以降低为$(x+1)$),也就是只需要13阶
同样对于K=5,可以验算虽然结果矩阵的特征多项式是
$(x-6)(x-1)^3(x+1)^3(x^2+1)^2(x^4+x^3-x^2+x+6)(x^4+x^3+x^2+x+6)(x^4+x^3+6*x^2+36*x+216)(x^6-x^5-5x^4+5x^3-30x^2-36x+216)(x^6+x^5+5x^4-5x^3-30x^2-36x-216)(x^8-x^7+x^6-x^5+10x^4-6x^3+x^2-6x+36)$
但是其极小多项式为$(x-6)(x-1)(x+1)(x^2+1)(x^4+x^3-x^2+x+6)(x^4+x^3+x^2+x+6)(x^4+x^3+6*x^2+36*x+216)(x^6-x^5-5x^4+5x^3-30x^2-36x+216)(x^6+x^5+5x^4-5x^3-30x^2-36x-216)(x^8-x^7+x^6-x^5+10x^4-6x^3+x^2-6x+36)$, 是一个37次多项式，而对应数列前面若干项（从n=5开始）为
30240
151200
604800
1814400
3628800
46751040
374220000
2524737600
14938560000
77718009600
445531847040
2712276403200
16824964464000
103374343800000
617483630937600
3664753055288640
21837147241644000
130987685561040000
788907380549248800
4744766700436795200
28473260931177834240
170667202760009373600
1023095448436157006400
6137898978940425396000
36838710229709607408000
221094889504876359483840
1326659091470885259511200
7959227075484282169286400
47750852315053352228702400
286497229035411628799241600
1719025119704447664447219840
10314475777660028879863627200
61887537159261232978690790400
371322790337209747988943784800
2227914360433389973865066820000
13367428356945652161399478319040
80204702391166954732387581376800
481229760111874619105995284110400
2887383136829665817272151400242400
17324292695239380514914948686234400
103945650626732360665419727553859840
623673547432474411057945382554831200
3742041506266723081383067390634397600
22452256076663180473072202039484369600
由此也可以利用递推关系式
$ a(n+37)= 4a(n+36) + 6a(n+35) + 4a(n+34) + 21a(n+33) + 1052a(n+32) + 953a(n+31) - 1803a(n+30) - 13334a(n+29) - 77066a(n+28) - 104214a(n+27)- 119566a(n+26)+ 149984a(n+25)+ 2676030a(n+24)+ 2087020a(n+23)+ 1591320a(n+22)+ 16945045a(n+21)+ 6202970a(n+20)- 19560760a(n+19)+ 31584610a(n+18)+ 36046155a(n+17)- 646436970a(n+16)- 519990845a(n+15)+ 306879755a(n+14)- 432091230a(n+13)- 6217952004a(n+12)- 3676588704a(n+11)+ 968486544a(n+10)- 2735044704a(n+9)- 29726450496a(n+8)- 8846537472a(n+7)+ 868361472a(n+6)- 9946685952a(n+5)- 41782127616a(n+4)+ 13060694016a(n+3)- 2176782336a(n+2)+ 13060694016a(n+1) + 78364164096a(n)$推出余下各项