双色珠串排列计数

aimisiyou

KeyTo9_Fans 发表于 2024-6-3 11:25
0颗珠子应该是1种排法：空集

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

怎么证明就是这个结果？

王守恩

观察加猜测。
1, 首位是"0"的数量=首位是"1"的数量。 2,  6,  14,  30,  62, ...
2, 首位是"0",可以在前面加"01"。
3, 首位是"1",可以在前面加"10"。
4, 首位是"0",末位是“1”，可以在前面加"1",后面加“0”。
5, 首位是"1",末位是“0”，可以在前面加"0",后面加“1”。

aimisiyou

王守恩 发表于 2024-6-3 14:56
观察加猜测。
1, 首位是"0"的数量=首位是"1"的数量。 2,  6,  14,  30,  62, ...
2, 首位是"0",可以在前面 ...

你这没考虑限制条件，任意多个连续相邻的珠子中红珠子跟黄珠子的颗数之差最多为2。

王守恩

aimisiyou 发表于 2024-6-3 16:35
你这没考虑限制条件，任意多个连续相邻的珠子中红珠子跟黄珠子的颗数之差最多为2。 ...

搞晕了(我不会电脑，纯手工)！请您复核。特别是前面5个数: 2, 6, 14, 30, 62。
将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种后面加"01"与"10"，可得32种。改：在首部"001"的16种后面“变化”，可得32种。

在首位"011"的16种后面加"01"与"10"，可得32种。改：在首部"011"的16种后面“变化”，可得32种。

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

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

aimisiyou

王守恩 发表于 2024-6-4 07:52
6颗红珠子跟6颗黄珠子排成一行，好的排法有63*2种。其中首位"0"有63种, 首位"1"有63种。

在首位"0"的63种 ...

我用DP来推算。

王守恩

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

lihpb00

得用穷举

hujunhua

构造性解法
沿袭前面各贴，用0, 1表双色。

一个好的珠串中，连续的0（或者1）堆的长度只能为2, 此外就是01交替间隔的串。这些0（或者1）堆积的地方称为骨节。
【定义一】（骨节与骨架）两个相邻的同色珠称为骨节。特别地，首尾于此被视为相邻位。所有的骨节构成骨架（无视非骨节色珠）。
【骨架定理】好珠串的骨架包括相同数量的两色骨节，并且两色骨节交错间隔。
【定义二】（填充串）由相同数量的0, 1逐一交错相间组成的不含骨节的串。0前1后称为0101串，反之称为1010串。
【好串的组成】一个好的珠串由骨架和骨节间的填充串组成，00-11间填充1010串，11-00间填充0101串。
【串的分节】将一个串的 2n个珠位两个两个划分为 n 个节位，有奇偶两种分法：
        1、奇性划分：1--23--45--67--...--(2n-2)(2n-1)--2n, (1和2n组成一个节位）
        2、偶性划分：12--34--56--78--...--(2n-1)2n.
【骨节定理】一个好串的骨节要么都处于奇性划分的节位上，要么都处于偶性划分的节位上。
【定义三】（奇/偶珠串）骨节处于奇/偶性划分的节位上的珠串。

有了以上描述，下面就可以排列计数了。
【含有 2r(r＞0) 个骨节的奇/偶性珠的计数】2C(n, 2r)
就是在 n 个 奇/偶性节位中选 2r 个骨节位的组合。乘以2是因为反色对偶。再加上奇、偶各2C(n, 2r), 共是4C(n, 2r).
r=0时，没有骨节，纯填充串就两种，0101串和1010串。
所以可排出的好的珠链数为
2C(n, 0)+4C(n, 2)+4C(n, 4)+…+4C(n, 2r)+…=2^(n+1)－2

hujunhua

如果把珠串首尾相接变成双色链环，去重似乎不那么容易呢。

难点在于环排列的旋转对称度具有数论特性，而不是代数特性。

数论特性一个数一个样，难以进行代数处理。