王守恩 发表于 2021-7-5 17:02:29

有几种不同排法?

将 1,2,3,…,7 排成一行，使前 k（k=1,2,…,6）个数之和都不能被 7 整除，有几种不同排法?

王守恩 发表于 2021-7-8 08:48:58

谢谢各位大侠！我就是不知道这个程应该怎么编(不会编)。谢谢各位大侠！

hujunhua 发表于 2021-7-8 11:35:22

总和28。7不能排到行首和行尾，7在行中也不影响模7的余，可以视而不见，所以只有6!。
前k项之和不为7整除，则后(6-k)项之和亦是，所以问题等价于：
将{1,2,3,4,5,6}的一个排列从中截断为两段，各段的数字之和都不是7的倍数，这样的排列共有多少个。
这个答案乘以5倍（7有5个插板位置），就是原问题的答数。
显然，一个排列是，则其逆排列也是。故搜索范围可对称减半。
记`b_i=r·a_i\pmod{7}`(取绝对值最小剩余）, 那`a_1a_2a_3a_4a_5a_6`是，则`b_1b_2b_3b_4b_5b_6`也是。

sheng_jianguo 发表于 2021-7-9 15:52:23

经编程计算，共有2040种不同排法，详见附件，仅供参考。

王守恩 发表于 2021-7-11 14:43:43

2040/5=408, 这是3#所说的去掉 7 之后的等价问题的答数。
408/6=68, 最高位有6种等可能，故以 1 为首的共68个排列。

01:123456
02:123465
03:123546
04:123564
05:123645
06:123654
00:124×
07:125346
08:125364
09:125436
10:125464
10:1256×
11:126345
12:126354
13:126435
14:126453
00:1265×
15:132456
16:132465
17:132546
18:132564
19:132645
20:132654
21:134256
22:134265
23:134526
24:134562
00:1346×
25:135246
26:135264
27:135426
28:135462
29:135624
30:135642
31:136245
32:136254
00:1364×
33:136524
34:136542
00:142×
35:143256
36:143265
37:143526
38:143562
00:1436×
39:145236
40:145263
41:145326
42:145362
43:145623
44:145632
45:146235
46:146253
00:1463×
47:146523
48:146532
49:152346
50:152364
51:152436
52:152463
00:1526×
53:153246
54:153264
55:153426
56:153462
57:153624
58:153642
59:154236
60:154263
61:154326
62:154362
63:154623
64:154632
00:1562×
65:156324
66:156342
67:156423
68:156432
00:16×

王守恩 发表于 2021-7-15 07:15:22

手工计算法

将{1,2,3,4,5,6}的一个排列从中截断为两段，各段的数字之和都不是7的倍数，这样的排列共有多少个？

A1=符合要求的首 1 排列集，Ai=符合要求的首 i 排列集。
易知，Ai=i·A1(mod 7), 所以|Ai|=|A1|.(这就是楼上所说的首位有6种等可能）
所以我们只需要计算 |A1|。
|A1|=5!-4!(第2位是6)-2×3!((第2,3位是2,4)-8×2!((第2,3,4位是2,5,6与3,4,6)=68

王守恩 发表于 2021-7-16 05:24:53

将 1,2,…,6 排成一个圆圈，把这个圆排列任意剪成两段，各段的数字之和都不能被 7 整除，有几种不同的圆排列?
不妨把两个反向合同的圆排列视为相同。

sheng_jianguo 发表于 2021-7-16 16:41:49

王守恩 发表于 2021-7-15 07:15
将{1,2,3,4,5,6}的一个排列从中截断为两段，各段的数字之和都不是7的倍数，这样的排列共有多少个？

A1= ...

将{1,2,3,4,5,6}的一个排列从中截断为两段，各种截断方法中，两段的数字之和都不是7的倍数，这样的排列共有多少个？
经编程计算，共有408种不同排法，详见附件，仅供参考。

hujunhua 发表于 2021-7-16 18:54:44

王守恩 发表于 2021-7-16 05:24
将 1,2,…,6 排成一个圆圈，把这个圆排列任意剪成两段，各段的数字之和都不能被 7 整除，有几种不同的圆排 ...
手工排了一下，不计方向只有7种，还是蛮稀贵的。而且这7个解还可以重叠摆放成下图的样子。

红圈上的环排列是独特的，对径和等于7，三数之和等于7和14的互相间隔，各占一个正三角形.
其它6个绿圈上的环排列可由乘法互换，在这个意义上可视为一个等价类。
试了一下想把红环放到中间，结果发现不可能。

王守恩 发表于 2021-7-17 14:48:47

王守恩 发表于 2021-7-16 05:24
将 1,2,…,6 排成一个圆圈，把这个圆排列任意剪成两段，各段的数字之和都不能被 7 整除，有几种不同的圆排 ...先看1的左右，考虑1,6，124不能相邻，有以下5种模式
12⚪⚪⚪3
12⚪⚪⚪5
13⚪⚪⚪4
13⚪⚪⚪5
14⚪⚪⚪5
考虑 124，25，34 不能相邻，答案只有7种。
126453
123645
132654
132465
132645
136245
146235

页: [1] 2
查看完整版本: 有几种不同排法?