数学研发论坛

 找回密码
 欢迎注册
12
返回列表 发新帖
楼主: 王守恩

[转载] 有几种不同排法?

[复制链接]
发表于 2021-7-18 05:48:49 | 显示全部楼层
圆环排列的问题虽然穷举有限,但不完全穷举可以这样推理:
易排得只有以下两种模式,其中同色点对∈{{1,6},{2,5},{3,4}},同形状三点组∈{{1,2,4},{3,5,6}}。
107CE02C-616C-4013-9B38-389FCA17D6E5.jpeg
模式 1 由于对称性,只有唯一解。模式 2 中{1,2,4}有6种排列,故有6解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-7-18 14:58:02 | 显示全部楼层
将圆环排列问题一般化而向高阶扩展,问:
将 1,2,…,n 排成一个圆圈,把这个圆排列任意剪成两段,各段的数字之和都不能被 n+1 整除,有几种不同的圆排列?
(不妨把两个反向合同的圆排列视为相同。)

当 n = 2k+1时,去掉中数 k+1 后,其它n-1个数分为和等于n+1的 k 对。结果 n 为奇数时,满足要求的排列种数为0。
所以 n 只能取为偶数,题目才能成立。

让我们从 n=8 开始:
将 1,2,…,8 排成一个圆圈,把这个圆排列任意剪成两段,各段的数字之和都不能被 9 整除,有几种不同的圆排列?
不妨把两个反向合同的圆排列视为相同。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-7-19 04:12:14 | 显示全部楼层
王守恩 发表于 2021-7-18 14:58
将 1,2,…,n排成一个圆圈,把这个圆排列任意剪成两段,各段的数字之和都不能被 n+1 整除,有几种不同的圆 ...

沿着n=8,10,12,14,16,……前进, 说不定能得到一个新数列。

虽然与直排列问题相比答数较小,但该数列增长速度感觉仍然会比较快,故可以考虑去掉数论同构的重复排列,新数列可能会好看一点。
所谓数论同构,指乘以一个与n+1互质的数取模(mod n+1)的变换下同构。按此同构划分取商,n=6时只有两个本原解。即12楼的模式2的6个排列皆同构。

评分

参与人数 1威望 +6 金币 +6 贡献 +6 经验 +6 鲜花 +6 收起 理由
王守恩 + 6 + 6 + 6 + 6 + 6 谢谢!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-7-19 16:55:51 | 显示全部楼层
王守恩 发表于 2021-7-18 14:58
将 1,2,…,8排成一个圆圈,把这个圆排列任意剪成两段,各段的数字之和都不能被 9 整除,有几种不同的圆 ...

当n=8时,经编程计算,共有39种不同排法,详见附件。
PLFF7JS8.dat (1.75 KB, 下载次数: 2)

评分

参与人数 1威望 +9 金币 +9 贡献 +9 经验 +9 鲜花 +9 收起 理由
王守恩 + 9 + 9 + 9 + 9 + 9 谢谢!及时雨!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-7-20 06:27:45 | 显示全部楼层
sheng_jianguo 发表于 2021-7-19 16:55
当n=8时,经编程计算,共有39种不同排法,详见附件。

在数论同构下,合并为 7 个本原解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-7-22 10:05:18 | 显示全部楼层
本帖最后由 王守恩 于 2021-7-22 11:04 编辑
sheng_jianguo 发表于 2021-7-19 16:55
当n=8时,经编程计算,共有39种不同排法,详见附件。

简单算起。
将 1,2,…,n 排成一个圆圈,任意相邻两数之和都不能被 n+1 整除,有几种不同的圆排列?
不妨把两个反向合同的圆排列视为相同。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-7-24 16:51:11 | 显示全部楼层
本帖最后由 sheng_jianguo 于 2021-7-27 20:27 编辑

问题:将 1,2,…,n 排成一个圆圈,任意相邻两数之和都不能被 n+1 整除,有几种不同的圆排列?不妨把两个反向合同的圆排列视为相同。
解答:对于此问题,有不难的如下计算公式(当n<4时,显然满足要求的圆排列数为0,故下面公式中,假定n≥4。):

符号说明
`S_n` 圆排列总数(不要求任意相邻两数之和都不能被` n+1`   整除)
`T_n ` 满足要求的圆排列总数(要求任意相邻两数之和都不能被 `n+1`  整除)
`F_n` 不满足要求的圆排列总数
`k ` 在`1,2,…,n` 中,两数之和能被` n+1`  整除的数对(不考虑先后次序)个数
`n_j`  圆排列中至少出现某个`j` 对两数之和能被 `n+1` 整除的圆排列数之和`(j=1,…,k)`

计算公式
`T_n = S_n - F_n`
`S_n =(n-1)!/2`
根据容斥原理:
`F_n =n_1-n_2+n_3…+(-1)^{k+1}n_k`
`k=[n/2]`  其中`[`  ` ] ` 为求整运算(去掉小数点后的整数)
`n_j =C_k^j2^{j-1}(n-j-1)!`  其中`C_k^j` 为`k` 个不同数中取`j` 个不同数的组合数,等于`k(k-1)` `…` `(k-j+1)/j!`

例子`(n=8)`
`S_8=7!/2=2520`
`k=[8/2]=4`
`n_1=4×20×6!=2880`
`n_2=6×21×5!=1440`
`n_3=4×22×4!=384`
`n_4=1×23×3!=48`
`T_8 =2520-(2880-1440+384-48)=744`
即`n=8` 时,满足要求的圆排列总数为`744` 种。经编程验算,结论正确。

计算公式也可写成:
`T_n = (n-1)!/2 -(C_k^12^{0}(n-2)!-C_k^22^{1}(n-3)!+...+(-1)^{k+1}C_k^k2^{k-1}(n-k-1)!)`  
其中`k=[n/2]`  

注:要求任意相邻两数之和都不能被 n+1 整除中,如将n+1改为其它数(如n,n+2等),只要有可能,计算公式可类似上面方法得出。


点评

合并公式已给出  发表于 2021-7-27 20:29
公式能合并就好了!  发表于 2021-7-26 19:04

评分

参与人数 1威望 +12 金币 +12 贡献 +12 经验 +12 鲜花 +12 收起 理由
王守恩 + 12 + 12 + 12 + 12 + 12 神马都是浮云

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-7-25 08:19:06 | 显示全部楼层
本帖最后由 王守恩 于 2021-7-25 09:36 编辑
sheng_jianguo 发表于 2021-7-24 16:51
问题:将 1,2,…,n 排成一个圆圈,任意相邻两数之和都不能被 n+1 整除,有几种不同的圆排列?不妨把两个反向 ...


问题:将 1,2,…,n 排成一个圆圈,任意相邻两数之和都不能被 n+1 整除,有几种不同的圆排列?不妨把两个反向合同的圆排列视为相同。
将1,2,3,4排成一个圆圈,任意相邻两数之和都不能被5整除,有1种不同的圆排列。
1243
将1,2,...5排成一个圆圈,任意相邻两数之和都不能被6整除,有4种不同的圆排列。
12354
12534
12543
13254
将1,2,...6排成一个圆圈,任意相邻两数之和都不能被7整除,有16种不同的圆排列。
123564
123645
123654
124563
124635
124653
126354
126453
132465
132645
132654
135624
136245
142365
142635
146235
将1,2,...7排成一个圆圈,任意相邻两数之和都不能被8整除,有120种不同的圆排列。
将1,2,...8排成一个圆圈,任意相邻两数之和都不能被9整除,有744种不同的圆排列。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-7-29 12:37:26 | 显示全部楼层
本帖最后由 王守恩 于 2021-7-29 12:45 编辑
sheng_jianguo 发表于 2021-7-24 16:51
问题:将 1,2,…,n 排成一个圆圈,任意相邻两数之和都不能被 n+1 整除,有几种不同的圆排列?不妨把两个反向 ...

谢谢 sheng_jianguo! 总算搞明白。谢谢 sheng_jianguo!

\(\D T_{n}=\sum_{k=0}^{n/2}\ \frac{(n-k-1)!\ \lfloor n/2\rfloor!\ 2^{k-1}\ \ \ }{k!\ \lfloor n/2-k\rfloor!\ \cos(k\pi)}\ \ \ \ \  n=4,5,6,7,8,9,...\)

{1, 4, 16, 120, 744, 6912, 56256, 631680, 6385920, 84211200, 1018114560, 15432560640,
217234805760, 3722677862400, 59809766768640, 1143584003358720, 20651520261980160}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-9-22 19:23 , Processed in 0.120333 second(s), 23 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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