5 颗红珠 5 颗黄珠排成一行，其中任何相邻的同色连串，珠数之差最多为 2，有几种排法?

myyour

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

王守恩

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

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

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

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

将4颗红珠子跟4颗黄珠子排成一行，好的排法共有27*2种。
00101011,
00101101,
00101110,
00110011,
00110101,
00110110,
00111001,
00111010,
00111100,
01001011,
01001101,
01001110,
01010011,
01010101,
01010110,
01011001,
01011010,
01011100,
01100011,
01100101,
01100110,
01101001,
01101010,
01101100,
01110001,
01110010,
01110100,

王守恩

楼上错啦！

将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,

myyour

王守恩 发表于 2024-6-3 07:46
楼上错啦！

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

谢谢王老师！

王守恩

任重道远！题目改一下, 还得请陆老师出手(我不行)。

将 n 颗红珠子跟 n 颗黄珠子排成一行，若任意多个连续相邻的珠子中红珠子跟黄珠子的颗数之差最多为2，

就称这种排法为好的排法，好的排法共有多少种？

lihp2020

如果 n=5  假设没得条件 就C(10,5) =252 个  再排除点不符合条件的 应该猜测低于200个 可以直接数
也应该比较大很容易数错 或者数重复  注意检查

我们只是方便求 n比较大的求法
先随便写个正确的结果
ooxxoxoxoxxoox
只看 o
oo o o o oo
N个 o  分成呢k (n/2<k<=n)组  每组 就1 或者2个

明显 只看 o的次数 标记Anum(n,k)
明显 Anum(n,n)=1
         Anum（n，n-1） =n-1
         Anum(n,k) =C(k,n-k)
       


当 分成
oo o o o oo   中间 有Xoo Xo Xo Xo XooX

一共X+1 个缝隙
其中 其实有4类填发
A Xoo Xo Xo Xo XooX
B  oo Xo Xo Xo XooX
C Xoo Xo Xo Xo Xoo
D  oo Xo Xo Xo Xoo
A 就是 要分成 k+1 堆  B**C**D**
对应 就是 C(k,n-k)*(C(k+1,n-(k+1))+2C(k,n-k)+C(k-1,n-(k-1)))

在 k=[n/2]到n 求和  [] 向上取整
ps: 组合这个求和 确实我不会 但是 当n<20 我们可以求出各种C(n,k) 在自己求和
带入验证 n=2  k=1->2
C(1,1)*(C(2,0)+2C(1,1)+C(0,2)) +
C(2,0)*(C(3,-1)+2C(2,0)+C(1,1))

=1*(1+2*1+0)+1*(0+2+1) =6
其中C(0,2) 和C(3,-1) 也符合组合数的意义 等于0
带入验证 n=3  k=2->3
C(2,1)*(C(3,0)+2C(2,1)+C(1,2)) +
C(3,0)*(C(4,-1)+2C(3,0)+C(2,1))
= 2*(1+2*2+0)+1*(0+2*1+2) =14

带入验证 n=4  k=2->4
C(2,2)*(C(3,1)+2C(2,2)+C(1,3)) +
C(3,1)*(C(4,0)+2C(3,1)+C(2,2)) +
C(4,0)*(C(5,-1)+2C(4,0)+C(3,1))
=1*(3+2*1+0)+3*(1+2*3+1)+1*(0+2*1+3)=34
明显和王守恩 的15*2 不同  
ps:00110110 01101100缺？所以数的时候 注意认真仔细
计算 n=5 k=3->5  一共 84种
计算 n=10         一共8196种

王守恩

将6颗红珠子跟6颗黄珠子排成一行，好的排法共有63*2种。
001010101011,
001010101101,
001010110011,
001010110101,
001011001011,
001011001101,
001011010011,
001011010101,
001100101011,
001100101101,
001100110011,
001100110101,
001101001011,
001101001101,
001101010011,
001101010101,
010010101011,
010010101101,
010010110011,
010010110101,
010011001011,
010011001101,
010011010011,
010011010101,
010100101011,
010100101101.
010100110011.
010100110101,
010101001011,
010101001101,
010101010011,
010101010101,
010101010110,
010101011001,
010101011010,
010101100101,
010101100110,
010101101001,
010101101010,
010110010101,
010110010110,
010110011001,
010110011010,
010110100101,
010110100110,
010110101001,
010110101010,
011001010101,
011001010110,
011001011001,
011001011010,
011001100101,
011001100110,
011001101001,
011001101010,
011010010101,
011010010110,
011010011001,
011010011010,
011010100101,
011010100110,
011010101001,
011010101010,

王守恩

6颗红珠子跟6颗黄珠子排成一行，好的排法有63*2种。其中首位"0"有63种, 首位"1"有63种。

在首位"0"的63种前面加"01"，可得63种。

在首部"001"的16种后面加"变化"，可得32种。

在首部"011"的16种后面加"变化"，可得32种。

可得: 首位"0"有63+32+32=127种, "0"与"1"互换, 可得首位"1"有127种。

即: 7颗红珠子跟7颗黄珠子排成一行，好的排法有127*2种。

王守恩

将1颗红珠子跟1颗黄珠子排成一行，好的排法共有2种。
a(1)=2: 2=2*(0+1+0),  0表示首部"001"的数量, 1表示首部"01"的数量, 0表示首部"011"的数量,
01,
10,

将2颗红珠子跟2颗黄珠子排成一行，好的排法共有6种。
a(2)=6: 6=2*(1+1+1), 1表示首部"001"的数量, 1表示首部"010"的数量, 1表示首部"011"的数量,
0011,
0101,
0110,
1001,
1010,
1100,

将3颗红珠子跟3颗黄珠子排成一行，好的排法共有14种。
a(3)=14: 14=2*(2+3+2), 2表示首部"001"的数量, 3表示首部"010"的数量, 2表示首部"011"的数量,
001011,
001101,
010011,
010101,
010110,
011001,
011010,

将4颗红珠子跟4颗黄珠子排成一行，好的排法共有15*2种。
a(4)=30: 30=2*(4+7+4),  4表示首部"001"的数量, 7表示首部"010"的数量, 4表示首部"011"的数量,
00101011,
00101101,
00110011,
00110101,
01001011,
01001101,
01010011,
01010101,
01010110,
01011001,
01011010,
01100101,
01100110,
01101001,
01101010,

将5颗红珠子跟5颗黄珠子排成一行，好的排法共有31*2种。
a(5)=62: 62=2*(8+15+8),  8表示首部"001"的数量, 15表示首部"010"的数量, 8表示首部"011"的数量,

a(6)=126: 126=2*(16+31+16),  
a(7)=254: 254=2*(32+63+32),  
a(8)=510: 510=2*(64+127+64),

王守恩

谢谢 hujunhua！ 给出构造性解法。谢谢 hujunhua！

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

将1颗红珠子跟1颗黄珠子排成一行，好的排法共有2种。
将2颗红珠子跟2颗黄珠子排成一行，好的排法共有6种。
将3颗红珠子跟3颗黄珠子排成一行，好的排法共有14种。
将4颗红珠子跟4颗黄珠子排成一行，好的排法共有30种。
将5颗红珠子跟5颗黄珠子排成一行，好的排法共有62种。

  得到这样一串数:   2,  6,  14,  30,  62,  126, 254, 510, 1022, 2046, 4094, 8190, 16382, 32766, 65534,
131070, 262142, 524286, 1048574, 2097150, 4194302, 8388606, 16777214, 33554430, 67108862,
134217726, 268435454, 536870910, 1073741822, 2147483646, 4294967294, 8589934590,  ......

\(\displaystyle4\sum_{k=1}^{n}\frac{n!}{(2k)!(n-2k)!}+2=\sum_{k=0}^{n+1}\frac{(n+1)!}{k!(n+1-k)!}-2=2^{n+1}-2\)