找回密码
 欢迎注册
查看: 21902|回复: 27

[悬赏] 这样的十进数有多少个?(排列问题)

[复制链接]
发表于 2017-3-29 11:05:15 | 显示全部楼层 |阅读模式
购买主题 已有 6 人购买  本主题需向作者支付 1 枚金币 才能浏览
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-3-29 20:32:06 | 显示全部楼层
012345算几位数?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-3-29 22:02:51 来自手机 | 显示全部楼层
成环前满足要求的数有以下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).
计算各种模式间的递推关系即可。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-3-29 22:04:54 来自手机 | 显示全部楼层
不同的数即使成环后圆排列相同仍视为不同的解(否则还要分析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)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-3-30 07:33:01 | 显示全部楼层
记`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 个数都不同使得没有翻转自对称者。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-3-30 10:02:50 | 显示全部楼层
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的选择是符合题设的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-3-30 11:32:11 | 显示全部楼层
由于其数字构成一个环,就不存在第一位之说了,所以没有排除最高位为0的情况
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-3-30 11:44:18 | 显示全部楼层
题目是说该十进数如果构成一个环的话,要满足...条件。要求的排列还是不构成环的十进数,所以那些成环后圆排列相同的不同数仍视作不同的解。

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

是否排除最高位为0的情况,只影响初值,不影响递推公式,但最终会影响通项公式。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-3-30 12:15:19 | 显示全部楼层
多谢!
虽然我没有看懂, 但是根据公式和计算机穷举出来的结果是正确的, 我本以为是一个很简单的排列组合问题,
想不到挺复杂了, 去了几个地方询问都没有结果, 就到这里注册了一个账号, 果然专业啊。
看来要消化很久了, 有没有相关的书籍推荐呀(题中涉及到的知识点群论,特征方程,矩阵等)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-3-30 12:48:01 | 显示全部楼层
题目中的进一步要求把片断长度改为k会导致计算过程快速复杂化。
倒是10进制如果改为其它进制,计算过程完全一致。
比如题目中k从3变化到4,那么同样我们假设最开始3个数为ABC,那么最后面三个数就可以有34种不同的模式,也就是题目需要处理一个34阶矩阵了。可以想象这个复杂度随着k的变大会迅速上升
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 22:31 , Processed in 0.049734 second(s), 22 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表