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

kastin

012345算几位数？

mathe

成环前满足要求的数有以下7种模式（不同的字母代表不同的数字）：
1、AB………CD
2、AB………AB
3、AB………BA
4、AB………AC
5、AB………CA
6、AB………BC
7、AB………CB
只有1、6两种在成环后继续符合要求。
记各种模式的n位十进数的计数为CD(n), AB(n), ..., CB(n).
计算各种模式间的递推关系即可。

mathe

不同的数即使成环后圆排列相同仍视为不同的解（否则还要分析n的所有因子），在此题设下各模式间的递推关系如下：

CD(n+1)=6CD(n)+7AC(n)+7BC(n)
AB(n+1)=CA(n)
BA(n+1)=CB(n)
AC(n+1)=8BA(n)+7CA(n)
CA(n+1)=CD(n)+BC(n)
BC(n+1)=8AB(n)+7CB(n)
CB(n+1)=CD(n)+AC(n)

mathe

记`v_n=(CD_n, AB_n, BA_n, AC_n,CA_n, BC_n, CB_n)`(*为了减少括号重数，此处使用下标变量*)， 记上述递推方程的系数矩阵
$[(6,0,0,7,0,7,0),(0,0,0,0,1,0,0),(0,0,0,0,0,0,1),(0,0,8,0,7,0,0),(1,0,0,0,0,1,0),(0,8,0,0,0,0,7),(1,0,0,1,0,0,0)]$
为`M`, 于是上述递推方程可写成矩阵形式：  `v_{n+1}=M\cdot v_n`
初值可取自n=3时，显然, 除了BC(3)=10*9*8=720，`v_3`的其它分量皆为零，即`v_3=(0,0,0,0,0,720,0)`。
逆推至初值得通项公式`v_n=M^{n-3}\cdot v_3=`$[(6,0,0,7,0,7,0),(0,0,0,0,1,0,0),(0,0,0,0,0,0,1),(0,0,8,0,7,0,0),(1,0,0,0,0,1,0),(0,8,0,0,0,0,7),(1,0,0,1,0,0,0)]^{n-3}[(0),(0),(0),(0),(0),(720),(0)]$,
p(n)取其中1，6两行之和，即$p(n)=[1,0,0,0,0,1,0][(6,0,0,7,0,7,0),(0,0,0,0,1,0,0),(0,0,0,0,0,0,1),(0,0,8,0,7,0,0),(1,0,0,0,0,1,0),(0,8,0,0,0,0,7),(1,0,0,1,0,0,0)]^{n-3}[(0),(0),(0),(0),(0),(720),(0)]$, 而对于$n<=2, p(n)=0$
经计算可以知道$p(n)$的特征多项式为$x^5 - 7*x^4 - x^3 - 57*x^2 + 64$, 相应的递推式为$p(n+5)=7p(n+4)+p(n+3)+57p(n+2)-64p(n)$

如果将成环后圆排列相同的合并为一个等价类，就要将一个n阶循环群作用在这个结果上，
根据Burnside's lemma,
等价类数$b(n)=\frac{1}{n}\sum_{d|n}\varphi(\frac{n}{d})p(d)$
例如$b(77)=\frac{10p(7)+6p(11)+p(77)}{77}=44816534719419245372952960144655997086890520197099265077993427788960$

另，如果划分等价类时再考虑环的翻转对称，则结果为b(n)/2. 因为相邻 3 个数都不同使得没有翻转自对称者。

hujunhua

kastin 发表于 2017-3-29 20:32
012345算几位数？

按@mathe楼上的初值p(3)=720, 则012345算6位数。也就是mathe未排除最高位取0的解。

主帖给出的`p(n,2)=9^n+(-1)^n9`可得p(3,2)=720.  因p(3,3)=p(3,2), 可见mathe的选择是符合题设的。

mathe

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

hujunhua

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

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

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

jjnet

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

mathe

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