有几种不同排法?

hujunhua

圆环排列的问题虽然穷举有限，但不完全穷举可以这样推理：
易排得只有以下两种模式，其中同色点对∈{{1,6},{2,5},{3,4}}，同形状三点组∈{{1,2,4},{3,5,6}}。

模式 1 由于对称性，只有唯一解。模式 2 中{1,2,4}有6种排列，故有6解。

王守恩

将圆环排列问题一般化而向高阶扩展，问：
将 1,2,…,n 排成一个圆圈，把这个圆排列任意剪成两段，各段的数字之和都不能被 n+1 整除，有几种不同的圆排列?
（不妨把两个反向合同的圆排列视为相同。）

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

让我们从 n=8 开始：
将 1,2,…,8 排成一个圆圈，把这个圆排列任意剪成两段，各段的数字之和都不能被 9 整除，有几种不同的圆排列?
不妨把两个反向合同的圆排列视为相同。

hujunhua

王守恩 发表于 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个排列皆同构。

sheng_jianguo

王守恩 发表于 2021-7-18 14:58
将 1,2,…,8排成一个圆圈，把这个圆排列任意剪成两段，各段的数字之和都不能被 9 整除，有几种不同的圆 ...

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

2021-7-19 16:52 上传

点击文件名下载附件

hujunhua

sheng_jianguo 发表于 2021-7-19 16:55
当n=8时，经编程计算，共有39种不同排法，详见附件。

在数论同构下，合并为 7 个本原解。

王守恩

sheng_jianguo 发表于 2021-7-19 16:55
当n=8时，经编程计算，共有39种不同排法，详见附件。

简单算起。
将 1,2,…,n 排成一个圆圈，任意相邻两数之和都不能被 n+1 整除，有几种不同的圆排列?
不妨把两个反向合同的圆排列视为相同。

sheng_jianguo

问题：将 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等），只要有可能，计算公式可类似上面方法得出。

王守恩

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种不同的圆排列。

王守恩

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}