论坛 › 难题征解 › 双色珠串排列计数

myyour 发表于 2024-6-2 15:39:04

双色珠串排列计数

求助计数问题，困挠了许多天。
将5颗红珠子跟5颗黄珠子排成一行，若任一连续片段中红黄珠子颗数之差最多为2，就称这种排法为好的排法，好的排法共有多少种？

aimisiyou 发表于 2024-6-2 19:08:29

编个程序算下吧

aimisiyou 发表于 2024-6-2 22:31:48

本帖最后由 aimisiyou 于 2024-6-2 22:42 编辑

lst
(1 1 0 1 0 1 0 1 0 0) (1 1 0 1 0 1 0 0 1 0) (1 1 0 1 0 0 1 1 0 0) (1 1 0 1 0 0 1 0 1 0) (1 1 0 0 1 1 0 1 0 0)
(1 1 0 0 1 1 0 0 1 0) (1 1 0 0 1 0 1 1 0 0) (1 1 0 0 1 0 1 0 1 0) (1 1 0 0 0 1 1 1 0 0) (1 1 0 0 0 1 1 0 1 0)
(1 0 1 1 0 1 0 1 0 0) (1 0 1 1 0 1 0 0 1 0) (1 0 1 1 0 0 1 1 0 0) (1 0 1 1 0 0 1 0 1 0) (1 0 1 1 0 0 0 1 1 0)
(1 0 1 0 1 1 0 1 0 0) (1 0 1 0 1 1 0 0 1 0) (1 0 1 0 1 1 0 0 0 1) (1 0 1 0 1 0 1 1 0 0) (1 0 1 0 1 0 1 0 1 0)
(1 0 1 0 1 0 1 0 0 1) (1 0 1 0 1 0 0 1 1 0) (1 0 1 0 1 0 0 1 0 1) (1 0 1 0 0 1 1 1 0 0) (1 0 1 0 0 1 1 0 1 0)
(1 0 1 0 0 1 1 0 0 1) (1 0 1 0 0 1 0 1 1 0) (1 0 1 0 0 1 0 1 0 1) (1 0 0 1 1 1 0 0 1 0) (1 0 0 1 1 1 0 0 0 1)
(1 0 0 1 1 0 1 0 1 0) (1 0 0 1 1 0 1 0 0 1) (1 0 0 1 1 0 0 1 1 0) (1 0 0 1 1 0 0 1 0 1) (1 0 0 1 0 1 1 0 1 0)
(1 0 0 1 0 1 1 0 0 1) (1 0 0 1 0 1 0 1 1 0) (1 0 0 1 0 1 0 1 0 1) (1 0 0 0 1 1 1 0 0 1) (1 0 0 0 1 1 0 1 0 1)
(0 1 1 1 0 0 1 0 1 0) (0 1 1 1 0 0 0 1 1 0) (0 1 1 0 1 0 1 0 1 0) (0 1 1 0 1 0 1 0 0 1) (0 1 1 0 1 0 0 1 1 0)
(0 1 1 0 1 0 0 1 0 1) (0 1 1 0 0 1 1 0 1 0) (0 1 1 0 0 1 1 0 0 1) (0 1 1 0 0 1 0 1 1 0) (0 1 1 0 0 1 0 1 0 1)
(0 1 1 0 0 0 1 1 1 0) (0 1 1 0 0 0 1 1 0 1) (0 1 0 1 1 0 1 0 1 0) (0 1 0 1 1 0 1 0 0 1) (0 1 0 1 1 0 0 1 1 0)
(0 1 0 1 1 0 0 1 0 1) (0 1 0 1 1 0 0 0 1 1) (0 1 0 1 0 1 1 0 1 0) (0 1 0 1 0 1 1 0 0 1) (0 1 0 1 0 1 0 1 1 0)
(0 1 0 1 0 1 0 1 0 1) (0 1 0 1 0 1 0 0 1 1) (0 1 0 1 0 0 1 1 1 0) (0 1 0 1 0 0 1 1 0 1) (0 1 0 1 0 0 1 0 1 1)
(0 1 0 0 1 1 1 0 0 1) (0 1 0 0 1 1 0 1 0 1) (0 1 0 0 1 1 0 0 1 1) (0 1 0 0 1 0 1 1 0 1) (0 1 0 0 1 0 1 0 1 1)
(0 0 1 1 1 0 0 1 0 1) (0 0 1 1 1 0 0 0 1 1) (0 0 1 1 0 1 0 1 0 1) (0 0 1 1 0 1 0 0 1 1) (0 0 1 1 0 0 1 1 0 1)
(0 0 1 1 0 0 1 0 1 1) (0 0 1 0 1 1 0 1 0 1) (0 0 1 0 1 1 0 0 1 1) (0 0 1 0 1 0 1 1 0 1) (0 0 1 0 1 0 1 0 1 1)
_ (length lst)
80

KeyTo9_Fans 发表于 2024-6-2 23:42:15

如果把5改成n，答案可能是这个数列：

https://oeis.org/A095121

但上面的数列的定义和楼主的定义不一样。

如果确实是同一个数列，我们可以考虑给A095121加一条Comment，把楼主的定义写上去。

myyour 发表于 2024-6-3 08:34:17

aimisiyou 发表于 2024-6-2 22:31
lst
(1 1 0 1 0 1 0 1 0 0) (1 1 0 1 0 1 0 0 1 0) (1 1 0 1 0 0 1 1 0 0) (1 1 0 1 0 0 1 0 1 0) (1 1 0 0 ...

应该不能出现000或111这类连续的，否则差就大于2了。

myyour 发表于 2024-6-3 08:36:03

KeyTo9_Fans 发表于 2024-6-2 23:42
如果把5改成n，答案可能是这个数列：

https://oeis.org/A095121


我看不懂，惭愧

nyy 发表于 2024-6-3 09:52:50

穷举法，
每个位置两种可能，2^10=1024，一共就1024种可能，然后一个一个过滤！

王守恩 发表于 2024-6-3 10:27:18

将5颗红珠子跟5颗黄珠子排成一行，若任意多个连续相邻的珠子中红珠子跟黄珠子的颗数之差最多为2，就称这种排法为好的排法，好的排法共有多少种？

将1颗红珠子跟1颗黄珠子排成一行，好的排法共有2种。
01,
10,

将2颗红珠子跟2颗黄珠子排成一行，好的排法共有6种。
0011,
0101,
0110,
1001,
1010,
1100,

将3颗红珠子跟3颗黄珠子排成一行，好的排法共有14种。
001011,
001101,
010011,
010101,
010110,
011001,
011010,
100101,
100110,
101001,
101010,
101100,
110010,
110100,

将4颗红珠子跟4颗黄珠子排成一行，好的排法共有15*2种。
00101011,
00101101,
00110011,
00110101,
01001011,
01001101,
01010011,
01010101,
01010110,
01011001,
01011010,
01100101,
01100110,
01101001,
01101010,

将5颗红珠子跟5颗黄珠子排成一行，好的排法共有31*2种。
0010101011,
0010101101,
0010110011,
0010110101,
0011001011,
0011001101,
0011010011,
0011010101,
0100101011,
0100101101.
0100110011.
0100110101,
0101001011,
0101001101,
0101010011,
0101010101,
0101010110,
0101011001,
0101011010,
0101100101,
0101100110,
0101101001,
0101101010,
0110010101,
0110010110,
0110011001,
0110011010,
0110100101,
0110100110,
0110101001,
0110101010,

aimisiyou 发表于 2024-6-3 10:56:41

应该可以用DP。

KeyTo9_Fans 发表于 2024-6-3 11:25:26

王守恩 发表于 2024-6-3 10:27
将5颗红珠子跟5颗黄珠子排成一行，若任意多个连续相邻的珠子中红珠子跟黄珠子的颗数之差最多为2，就称这种 ...

0颗珠子应该是1种排法：空集

然后得到这个数列：1，2，6，14，30，62……

这个数列的编号应该就是A095121吧？

https://oeis.org/A095121

查看完整版本: 双色珠串排列计数