双色珠串排列计数

aimisiyou

hujunhua 发表于 2024-6-4 20:15
构造性解法
沿袭前面各贴，用0, 1表双色。

有点绕，没看懂意思

hujunhua

好的双色链环：(镜像对称视为不同）
a(1)=1:  01
a(2)=2:  0101, 0011
a(3)=3:  010101, 001101, 110010
a(4)=5:  01010101, 00110011, 00110101, 11001010, 00101101
a(5)=7:  0101010101, 0011001101, 1100110010, 0011010101, 1100101010, 0010110101, 1101001010
链环如果用骨节来表示能压缩一半，比如n=5的链环依次为：-----, 0101-, 1010-, 01---，10---，0-1--，1-0--
a(6)=13:  ------, 010101, 0101--, 1010--, 0-101-, 1-010-, 01-01-, 10-10-, 01----, 10----, 0-1---, 1-0---, 0--1--
a(7)=19:  -------, 010101-, 101010-, 0101---, 1010---, 1-010--, 0-101--, 1--010-, 0--101-, 01-01--, 10-10--, 0-1-0-1, 1-0-1-0, 01-----, 10-----, 1-0----, 0-1----, 1--0---, 0--1---

应该是A008965

hujunhua

a(1)=1:  01
a(2)=2:  0101, 0011
a(3)=2：010101, 001101
a(4)=4:  01010101, 00110011, 00110101, 00101101
a(5)=4:  0101010101, 0011001101, 0011010101, 0010110101
链环如果用骨节来表示能压缩一半，比如n=5的链环依次为：-----, 0101-, 01---，0-1--
a(6)=9:  ------, 010101, 0101--,  0-101-, 1-010-, 01-01-, 01----, 0-1---, 0--1--
a(7)=10:  -------, 010101-, 0101---, 1-010--, 0-101--, 01-01--, 0-1-0-1, 01-----, 0-1----, 1--0---
a(8)=22:  --------,01010101, 010101--,01010-1-, 10101-0-, 0101-01-, 010-101-, 0101----, 010-1---, 101-0---, 010--1--, 101--0--, 01-01---, 01--01--, 0-1-0-1-, 0-1--01-, 0-1-01--, 0--1-01-, 01------,0-1-----, 0--1----, 0---1---

应该是A053656

aimisiyou

hujunhua 发表于 2024-6-5 03:23
a(1)=1:  01
a(2)=2:  0101, 0011
a(3)=2：010101, 001101

有详细的证明过程吗？

hujunhua

在骨节的定义中，首尾两端被视为相邻。
相应地，在节位的奇性划分中，首尾两端被视为一个节。
为什么要这样呢？
因为首尾看起来不相邻，但合起来的堆长也不能超过2.
比如，假定首二位是00，若尾部还是0，那么去掉此3位，剩余部分是 n 个1，n-3个0，不好。
可见考察含端点的堆长时，两端必须视为相邻，合并计算。

一个好的环链，从任一缝隙剪断都是一个好的珠串，这是显然的。
反之也成立。一个好的珠串，两端接起来必是一个好的环链。

hujunhua

aimisiyou 发表于 2024-6-5 10:27
有详细的证明过程吗？

关于结构的详细证明，从下述引理开始。
首先，珠串的好坏等价于环链的好坏，因此我们都按环链处理。
【引理1】从一个好的环链中去掉两个相邻的异色珠子，剩下部分仍然是一个好的环链。
证明：
1#题设所谓“任意多个连续相邻的珠子”，我们姑且称之为一个“局部”。
按题设的定义，一个环链是好的，当且仅当它的任一局部都是好的。
从一个环链A中去掉一节01，剩余部分为B。设去掉01的地方为a01b,  
在B中，
不包含ab的局部也是原A的局部，因此都是好的。
包含ab的局部，来自A的包含a01b的局部，删除01不改变0,1之差，所以也是好的。
所以B是好的。
证毕。

根据引理1，就可以证明骨架定理、骨节定理、填充串的定义、好串的组成。

aimisiyou

hujunhua 发表于 2024-6-5 11:42
关于结构的详细证明，从下述引理开始。
首先，珠串的好坏等价于环链的好坏，因此我们都按环链处理。
【引 ...

如果任意多个连续相邻的珠子个数差值不超过3呢？能类推么？

myyour

hujunhua 发表于 2024-6-5 11:42
关于结构的详细证明，从下述引理开始。
首先，珠串的好坏等价于环链的好坏，因此我们都按环链处理。
【引 ...

原来这道题难度很高，怪不得我老想不出来。

王守恩

29#是学习23#的心得体会。谢谢 hujunhua ！
继续学习。可以把A,B去掉。因为:  A,A中间必有B,  B,B中间必有A。
将1颗A珠与1颗B珠穿成一个圆环,  好圆环有1种。
01, AB——1,
将2颗A珠与2颗B珠穿成一个圆环,  好圆环有2种。
01, ABAB——2,
02, AABB——1,0,
将3颗A珠与3颗B珠穿成一个圆环,  好圆环有2种。
01, ABABAB——3,
02, AABABB——2,0,
将4颗A珠与4颗B珠穿成一个圆环,  好圆环有4种。
01, ABABABAB——4,
02, AABABABB——3,0,
03, AABABBAB——2,1,
04, AABBAABB——1,0,1,0,
将5颗A珠与5颗B珠穿成一个圆环,  好圆环有4种。
01, ABABABABAB——5,
02, AABABABABB——4,0,
03, AABABABBAB——3,1,
04, AABABBAABB——2,0,1,0,
将6颗A珠与6颗B珠穿成一个圆环,  好圆环有9种。
01, ABABABABABAB——6,
02, AABABABABABB——5,0,
03, AABABABABBAB——4,1,
04, AABABABBABAB——3,2,
05, AABABABBAABB——3,0,1,0,
06, AABABBAABBAB——2,0,1,1,
07, AABABBAABABB——2,0,2,0,
08, AABABBABAABB——2,1,1,0,
09, AABBAABBAABB——1,0,1,0,1,0,
将7颗A珠与7颗B珠穿成一个圆环,  好圆环有10种。
01, ABABABABABABAB——7,
02, AABABABABABABB——6,0,  
03, AABABABABABBAB——5,1,
04, AABABABABBABAB——4,2,
05, AABABABABBAABB——4,0,1,0,
06, AABABABBAABBAB——3,0,1,1,
07, AABABABBAABABB——3,0,2,0,
08, AABABABBABAABB——3,1,1,0,
09, AABABBAABABBAB——2,0,2,1，
10, AABABBAABBAABB——2,0,1,0,1,0,
将8颗A珠与8颗B珠穿成一个圆环，好圆环有22种。
01, ABABABABABABABAB——8,
02, AABABABABABABABB——7,0,  
03, AABABABABABABBAB——6,1,
04, AABABABABABBABAB——5,2,
05, AABABABABBABABAB——4,3,
06, AABABABABABBAABB——5,0,1,0,
07, AABABABABBAABBAB——4,0,1,1,
08, AABABABABBAABABB——4,0,2,0,
09, AABABABABBABAABB——4,1,1,0,
10, AABABABBAABBABAB——3,0,1,2,
11, AABABABBAABABBAB——3,0,2,1,
12, AABABABBAABABABB——3,0,3,0,
13, AABABABBABAABBAB——3,1,1,1,
14, AABABABBABAABABB——3,1,2,0,
15, AABABABBABABAABB——3,2,1,0,
16, AABABBABAABABBAB——2,1,2,1,
17, AABABABBAABBAABB——3,0,1,0,1,0,
18, AABABBAABBAABBAB——2,0,1,0,1,1,
19, AABABBAABBABAABB——2,0,1,1,1,0,
20, AABABBAABABBAABB——2,0,2,0,1,0,
21, AABABBABAABBAABB——2,1,1,0,1,0,
22, AABBAABBAABBAABB——1,0,1,0,1,0,1,0,

A053656——1, 2, 2, 4, 4, 9, 10, 22, 30, 62, 94, 192, 316, 623, 1096, 2122, 3856, 7429, 13798, 26500, 49940, 95885, 182362, 350650,
好像没有递推公式, 可以有吗？ 谢谢各位好友！

hujunhua

王守恩 发表于 2024-6-13 20:31
将n颗红珠与n颗黄珠穿成一个圆环,  若任意连续相邻的珠子中,红珠跟黄珠最多相差2颗,  就称这个圆环为好圆环 ...

你这里学习23#，另创的这种压缩记录显然是一种退步，不如23#规整和便于遍历。
所以你的枚举，错漏不少，以下按你的序号列举。
n=7的，05=08
n=8的，03=20，05=15，10=19，13=16
n=9的，05=24，09=16，13=25，17=22，20=26