求助：计数问题

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
关于结构的详细证明，从下述引理开始。
首先，珠串的好坏等价于环链的好坏，因此我们都按环链处理。
【引 ...

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

王守恩

将n颗红珠与n颗黄珠穿成一个圆环,  若任意连续相邻的珠子中,红珠跟黄珠最多相差2颗,  就称这个圆环为好圆环,  好圆环有多少种？
将1颗A珠与1颗B珠穿成一个圆环，好圆环有1种。
01, AB——1,
将2颗A珠与2颗B珠穿成一个圆环，好圆环有2种。
01, AABB——A 1 B,
02, ABAB——2,
将3颗A珠与3颗B珠穿成一个圆环，好圆环有2种。
01, AABABB——A 2 B,
02, ABABAB——3,
将4颗A珠与4颗B珠穿成一个圆环，好圆环有4种。
01, AABABABB——A 3 B,
02, AABABBAB——A 2 B 1,
03, AABBAABB——A 1 BA 1 B,
04, ABABABAB——4,
将5颗A珠与5颗B珠穿成一个圆环，好圆环有4种。
01, AABABABABB——A 4 B,
02, AABABABBAB——A 3 B 1,
03, AABABBAABB——A 2 BA 1 B,
04, ABABABABAB——5,
将6颗A珠与6颗B珠穿成一个圆环，好圆环有9种。
01, AABABABABABB——A 5 B,
02, AABABABABBAB——A 4 B 1,
03, AABABABBAABB——A 3 BA 1 B,
04, AABABABBABAB——A 3 B 2,
05, AABABBAABABB——A 2 BA 2 B,
06, AABABBAABBAB——A 2 BA 1 B 1,
07, AABABBABAABB——A 2 B 1 A 1 B,
08, AABBAABBAABB——A 1 BA 1 BA 1 B,
09, ABABABABABAB——6,
将7颗A珠与7颗B珠穿成一个圆环，好圆环有10种。
01, AABABABABABABB——A 6 B,  
02, AABABABABABBAB——A 5 B 1,
03, AABABABABBAABB——A 4 BA 1 B,
04, AABABABABBABAB——A 4 B 2,
05, AABABABBAABABB——A 3 BA 2 B,
06, AABABABBAABBAB——A 3 BA 1 B 1,
07, AABABABBABAABB——A 3 B 1 A 1 B,
08, AABABBAABABABB——A 2 BA 3 B,
09, AABABBAABBAABB——A 2 BA 1 BA 1 B,
10, ABABABABABABAB——7,
将8颗A珠与8颗B珠穿成一个圆环，好圆环有22种。
01, AABABABABABABABB——A 7 B,  
02, AABABABABABABBAB——A 6 B 1,
03, AABABABABABBAABB——A 5 BA 1 B,
04, AABABABABABBABAB——A 5 B 2,
05, AABABABABBAABABB——A 4 BA 2 B,
06, AABABABABBAABBAB——A 4 BA 1 B 1,
07, AABABABABBABAABB——A 4 B 1 A 1 B,
08, AABABABABBABABAB——A 4 B 3,
09, AABABABBAABABABB——A 3 BA 3 B,
10, AABABABBAABABBAB——A 3 BA 2 B 1,
11, AABABABBAABBAABB——A 3 BA 1 BA 1 B,
12, AABABABBAABBABAB——A 3 BA 1 B 2,
13, AABABABBABAABABB——A 3 B 1 A 2 B,
14, AABABABBABAABBAB——A 3 B 1 A 1 B 1,
15, AABABBAABABABABB——A 2 BA 4 B,
16, AABABBAABABABBAB——A 2 BA 3 B 1,
17, AABABBAABABBAABB——A 2 BA 2 BA 1 B,
18, AABABBAABBAABBAB——A 2 BA 1 BA 1 B 1,
19, AABABBABAABABABB——A 2 B 1 A 3 B,
20, AABBAABABABABABB——A 1 BA 5 B,
21, AABBAABBAABBAABB——A 1 BA 1 BA 1 BA 1 B,
22, ABABABABABABABAB——8,
将9颗A珠与9颗B珠穿成一个圆环，好圆环有30种。
01, AABABABABABABABABB——A 8 B,  
02, AABABABABABABABBAB——A 7 B 1,
03, AABABABABABABBAABB——A 6 BA 1 B,
04, AABABABABABABBABAB——A 6 B 2,
05, AABABABABABBAABABB——A 5 BA 2 B,
06, AABABABABABBAABBAB——A 5 BA 1 B 1,
07, AABABABABABBABAABB——A 5 B 1 A 1 B,
08, AABABABABABBABABAB——A 5 B 3,
09, AABABABABBAABABABB——A 4 BA 3 B,
10, AABABABABBAABABBAB——A 4 BA 2 B 1,
11, AABABABABBAABBAABB——A 4 BA 1 BA 1 B,
12, AABABABABBAABBABAB——A 4 BA 1 B 2,
13, AABABABABBABAABABB——A 4 B 1 A 2 B,
14, AABABABABBABAABBAB——A 4 B 1 A 1 B 1,
15, AABABABABBABABAABB——A 4 B 2 A 1 B,
16, AABABABBAABABABABB——A 3 BA 4 B,
17, AABABABBAABABABBAB——A 3 BA 3 B 1,
18, AABABABBAABABBAABB——A 3 BA 2 BA 1 B,
19, AABABABBAABABBABAB——A 3 BA 2 B 2,
20, AABABABBAABBAABABB——A 3 BA 1 BA 2 B,
21, AABABABBAABBAABBAB——A 3 BA 1 BA 1 B 1,
22, AABABABBABAABABABB——A 3 B 1 A 3 B,
23, AABABABBABAABABBAB——A 3 B 1 A 2 B 1,
24, AABABBAABABABABABB——A 2 BA 5 B,
25, AABABBAABABABABBAB——A 2 BA 4 B 1,
26, AABABBAABABABBAABB——A 2 BA 3 BA 1 B,
27, AABABBAABABABBABAB——A 2 BA 3 B 2,
28, AABABBAABABBABAABB——A 2 BA 2 B 1 A 1 B,
29, AABABBAABBAABBAABB——A 2 BA 1 BA 1 BA 1 B,
30, ABABABABABABABABAB——9,