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

mathe

由于其数字构成一个环，就不存在第一位之说了，所以没有排除最高位为0的情况

hujunhua

题目是说该十进数如果构成一个环的话，要满足...条件。要求的排列还是不构成环的十进数，所以那些成环后圆排列相同的不同数仍视作不同的解。

在常规意义上，还是应该排除最高位为0的排列的。

是否排除最高位为0的情况，只影响初值，不影响递推公式，但最终会影响通项公式。

jjnet

多谢！
虽然我没有看懂， 但是根据公式和计算机穷举出来的结果是正确的， 我本以为是一个很简单的排列组合问题，
想不到挺复杂了， 去了几个地方询问都没有结果， 就到这里注册了一个账号， 果然专业啊。
看来要消化很久了， 有没有相关的书籍推荐呀（题中涉及到的知识点群论，特征方程，矩阵等）

mathe

题目中的进一步要求把片断长度改为k会导致计算过程快速复杂化。
倒是10进制如果改为其它进制，计算过程完全一致。
比如题目中k从3变化到4，那么同样我们假设最开始3个数为ABC,那么最后面三个数就可以有34种不同的模式，也就是题目需要处理一个34阶矩阵了。可以想象这个复杂度随着k的变大会迅速上升

mathe

题目中还有一点比较有意思的结果，可以看到虽然题目中矩阵是7阶的，但是这个数列却是一个5阶线性递推数列，
于是可以猜测其中应该还有一些隐含的约束在里面。
如果我们把3#中每个模式反序观之，可以看出4和7是镜像偶，相应的计数函数可以互相代换，省掉一个，其它5个模式是镜像自对称的，计数函数也各不相等。
于是对应的矩阵刚好可以降低到6阶，7用4代换后的矩阵如下：
$M_2=[(6,0,0,7,0,7),(0,0,0,0,1,0),(0,0,0,1,0,0),(0,0,8,0,7,0),(1,0,0,0,0,1),(0,8,0,7,0,0)]$
经计算不出所料$M$和$M_2$的最小多项式都是$x^5−7x^4−x^3−57x^2+64=(x-8)(x-1)(x+1)(x^2+x+8)$,但是出乎意料的是$M_2$的特征多项式不是$M$的特征多项式的因子
其中$M$的特征多项式是$(x-8)(x-1)(x+1)(x^2+x+8)^2$,而$M_2$的特征多项式是$(x-8)(x-1)(x+1)^2(x^2+x+8)$

ps: 最出人意料的是只有1对计数相等的模式，而不是两对从而降为5阶矩阵。

另外一般情况，我们把10个数改为T个数，那么递推数列的特征多项式就是$(x-T+2)(x-1)(x+1)(x^2+x+T-2)$

jjnet

终于理解了到矩阵计算这一步， 但是下面一句
'经计算可以知道p(n)的特征多项式为"   不懂， 特征多项式跟递推公式和矩阵结果存在什么关系？ 是线性代数的书有讲吗？

jjnet

另外， 这个递推公式能转换成通项公式吗？

mathe

比如数值表示可以用Pari/Gp如下计算:
? b=[1,0,0,0,0,1]
%1 = [1, 0, 0, 0, 0, 1]
? v=[0,0,0,0,0,720]~
%2 = [0, 0, 0, 0, 0, 720]~
? m=[6,0,0,7,0,7;0,0,0,0,1,0;0,0,0,1,0,0;0,0,8,0,7,0;1,0,0,0,0,1;0,8,0,7,0,0]
%3 =
[6 0 0 7 0 7]

[0 0 0 0 1 0]

[0 0 0 1 0 0]

[0 0 8 0 7 0]

[1 0 0 0 0 1]

[0 8 0 7 0 0]

? mateigen(m)
%4 =
[-2 0 7 -0.73224568138195777351247600767754318618 + 0.63585792627329425022285708692064049226*I -0.73224568138195777351247600767754318618 - 0.63585792627329425022285708692064049226*I]

[-1 1 1/8 -0.0037188099808061420345489443378119001906 - 0.086161420681990502393643449803322083513*I -0.0037188099808061420345489443378119001906 + 0.086161420681990502393643449803322083513*I]

[-1 -1 1/8 0.10832533589251439539347408829174664107 - 0.0046754259284801047810504197567694153845*I 0.10832533589251439539347408829174664107 + 0.0046754259284801047810504197567694153845*I]

[1 -1 1 -0.067178502879078694817658349328214971211 - 0.29922725942272670598722686443324258459*I -0.067178502879078694817658349328214971211 + 0.29922725942272670598722686443324258459*I]

[1 1 1 -0.23800383877159309021113243761996161228 + 0.053433439182629768926290511505936175822*I -0.23800383877159309021113243761996161228 - 0.053433439182629768926290511505936175822*I]

[1 1 1 1 1]

? P=%4;
? P^-1*m*P
%6 =
[-1.0000000000000000000000000000000000000 + 0.E-37*I -1.4693679385278593850 E-39 + 0.E-37*I -3.673419846319648463 E-38 + 0.E-38*I 1.4693679385278593850 E-39 + 8.265194654219209041 E-40*I -7.346839692639296925 E-39 - 2.3877229001077715006 E-39*I]

[-5.142787784847507848 E-39 + 0.E-37*I 1.0000000000000000000000000000000000000 + 0.E-37*I -6.538687326448974264 E-38 - 3.159141067834897678 E-38*I 2.5713938924237539236 E-39 + 7.255004196481305714 E-39*I 9.550891600431086002 E-39 - 7.255004196481305714 E-39*I]

[-8.816207631167156310 E-39 + 4.353682780823287065 E-40*I -8.816207631167156310 E-39 + 1.0884206952058217666 E-39*I 7.9999999999999999999999999999999999999 - 9.360417978770067193 E-39*I -2.938735877055718770 E-39 + 7.074734518837841484 E-40*I 0.E-38 - 1.8639204405399697752 E-39*I]

[2.938735877055718770 E-39 - 1.7632415262334312620 E-38*I 1.4693679385278593850 E-38 - 1.7632415262334312620 E-38*I 2.938735877055718770 E-39 - 1.7632415262334312620 E-38*I -0.50000000000000000000000000000000000002 - 2.7838821814150109610597356494592747602*I -2.350988701644575016 E-38 - 2.938735877055718770 E-38*I]

[-1.7632415262334312620 E-38 + 5.289724578700293786 E-38*I 1.7632415262334312620 E-38 + 5.289724578700293786 E-38*I 5.877471754111437540 E-39 + 5.289724578700293786 E-38*I -1.4693679385278593850 E-38 - 5.877471754111437540 E-39*I -0.50000000000000000000000000000000000000 + 2.7838821814150109610597356494592747603*I]

? P^-1*v
%7 = [34.999999999999999999999999999999999999 + 1.0579449157400587572 E-36*I, 35.999999999999999999999999999999999998 - 1.0579449157400587572 E-36*I, 64.000000000000000000000000000000000000 + 3.134651602192766688 E-37*I, 292.50000000000000000000000000000000000 - 39.602969096903865607333658755210973202*I, 292.50000000000000000000000000000000000 + 39.602969096903865607333658755210973202*I]~
? b*P
%8 = [-1, 1, 8, 0.26775431861804222648752399232245681382 + 0.63585792627329425022285708692064049226*I, 0.26775431861804222648752399232245681382 - 0.63585792627329425022285708692064049226*I]
?
由此可以看出，由于数列通项为$b*M^{n-3}*v' = b*P*(P^{-1}MP)^{n-3}*P^{-1}v'$
其中$b*P=[-1, 1, 8, 0.26775431861804222648752399232245681382 + 0.63585792627329425022285708692064049226*I, 0.26775431861804222648752399232245681382 - 0.63585792627329425022285708692064049226*I]$
$P^{-1}v'= [34.999999999999999999999999999999999999 + 1.0579449157400587572 E-36*I, 35.999999999999999999999999999999999998 - 1.0579449157400587572 E-36*I, 64.000000000000000000000000000000000000 + 3.134651602192766688 E-37*I, 292.50000000000000000000000000000000000 - 39.602969096903865607333658755210973202*I, 292.50000000000000000000000000000000000 + 39.602969096903865607333658755210973202*I]~$
而$P^{-1}MP$是对角阵$diag{-1，1，8， -0.5-2.7838821814150109610597356494592747602*I，-0.5+2.7838821814150109610597356494592747602*I}$
表示$a(n)=-35*(-1)^(n-3)+36+512*8^(n-3)+(103.5+175.38457742914569054676334591593430989i)*(-0.5-2.7838821814150109610597356494592747602i)^(n-3)+(103.5-175.38457742914569054676334591593430989i)*(-0.5+2.7838821814150109610597356494592747602i)^(n-3)$
只是很奇怪，这里P不是方阵,Pari-gp是如何算出$P^{-1}$的而且最后通项好像也没有错
如果我们设$r_1,r_2$分别是方程$x^2+x+8=0$的根，那么通解应该是
$a(n)=-35*(-1)^{n-3}+36+512*8^{n-3}+(135+63*r_2)r_1^{n-3}+(135+63*r_1)r_2^{n-3}$
上面表达式还可以写成
$a(n)=36-35*(-1)^{n-3}+512*8^{n-3}+135*(r_1^{n-3}+r_2^{n-3})+504*(r_1^{n-4}+r_2^{n-4})=36-35*(-1)^{n-3}+512*8^{n-3}+135b(n-3)+504b(n-4)$
其中$b(n)$是二阶递推数列$b(0)=2,b(1)=-1,b(n+2)=-b(n+1)-8b(n)$
或者
$a(n)=36+35*(-1)^n+8^n+270*\sqrt{8}^{n-3}*cos((n-3)(\pi-arctan(\sqrt{31})))+1008*\sqrt{8}^{n-4}*cos((n-4)(\pi-arctan(\sqrt{31})))$

mathe

楼上计算过程说明准确计算过程需要将矩阵转化为Jordan标准型，但是pari/gp好像没有对应的函数。

hujunhua

mathe 发表于 2017-3-30 12:48
题目中的进一步要求把片断长度改为k会导致计算过程快速复杂化。
比如题目中k从3变化到4，可以有34种不同的模式，也就是题目需要处理一个34阶矩阵了.

k=4时，34种模式中，有10个镜像对称偶，剩余14个为镜像自对称。故递推矩阵可降为24阶。

手工排的，不知道有没有错误。如果没有错误的话，猜想k=5时，或许递推矩阵阶数可降为5！