有什么规律吗？

王守恩

满足如下要求的 n 位二进数 b 有多少个？：
1. b 的个位数为 1，并且
2. 任意长的前缀中 1 不少于 0 .

假定这样的 b 有 a(n)个。前1~9项为

a(1)=1
a(2)=1
a(3)=2
a(4)=3
a(5)=6
a(6)=10
a(7)=20
a(8)=35
a(9)=70
.........
有什么规律吗？

dlpg070

似乎:
a(n) = binomial(n, ceiling(n/2))

.·.·.

dlpg070 发表于 2019-6-17 11:23
似乎:
a(n) = binomial(n, ceiling(n/2))

这是个括号匹配问题吧……
要求每一个右括号(0)都与左括号(1)匹配
这应该可以用卡特兰数进行计算

至于结果……懒得算了[滑稽]

dlpg070

.·.·. 发表于 2019-6-17 12:30
这是个括号匹配问题吧……
要求每一个右括号(0)都与左括号(1)匹配
这应该可以用卡特兰数进行计算

很漂亮的一道题，对应很多实际问题,许多解法.
a(n) = binomial(n, ceiling(n/2)) 是最简单的一种

1. Table[Binomial[n, Ceiling[n/2]], {n,0, 9}]

复制代码

1. {1, 1,2, 3, 6, 10, 20, 35, 70, 126}

复制代码

[滑稽] ,用catalan numer 计算可以,不简单,我不懂,试试看

王守恩

n=1~9的 b 罗列如下：

1=1

1=11

1=101
2=111

1=1011
2=1101
3=1111

1=10101
2=10111
3=11001
4=11011
5=11101
6=11111

01=101011
02=101101
03=101111
04=110011
05=110101
06=110111
07=111001
08=111011
09=111101
10=111111

01=1010101
02=1010111
03=1011001
04=1011011
05=1011101
06=1011111
07=1100101
08=1100111
09=1101001
10=1101011
11=1101101
12=1101111
13=1110001
14=1110011
15=1110101
16=1110111
17=1111001
18=1111011
19=1111101
20=1111111

01=10101011
02=10101101
03=10101111
04=10110011
05=10110101
06=10110111
07=10111001
08=10111011
09=10111101
10=10111111
11=11001011
12=11001101
13=11001111
14=11010011
15=11010101
16=11010111
17=11011001
18=11011011
19=11011101
20=11011111
21=11100011
22=11100101
23=11100111
24=11101001
25=11101011
26=11101101
27=11101111
28=11110001
29=11110011
30=11110101
31=11110111
32=11111001
33=11111011
34=11111101
35=11111111

01=101010101
02=101010111
03=101011001
04=101011011
05=101011101
06=101011111
07=101100101
08=101100111
09=101101001
10=101101011
11=101101101
12=101101111
13=101110001
14=101110011
15=101110101
16=101110111
17=101111001
18=101111011
19=101111101
20=101111111
21=110010101
22=110010111
23=110011001
24=110011011
25=110011101
26=110011111
27=110100101
28=110100111
29=110101001
30=110101011
31=110101101
32=110101111
33=110110001
34=110110011
35=110110101
36=110110111
37=110111001
38=110111011
39=110111101
40=110111111
41=111000101
42=111000111
43=111001001
44=111001011
45=111001101
46=111001111
47=111010001
48=111010011
49=111010101
50=111010111
51=111011001
52=111011011
53=111011101
54=111011111
55=111100001
56=111100011
57=111100101
58=111100111
59=111101001
60=111101011
61=111101101
62=111101111
63=111110001
64=111110011
65=111110101
66=111110111
67=111111001
68=111111011
69=111111101
70=111111111

补充内容 (2019-6-22 21:28):
把末位的 1 去掉，就是 13#。

aimisiyou

归根到底，就是求$$C_n^0+C_n^1+C_n^2+\dots+C_n^\frac{n}2$$

kastin

网上有人问过同样的问题，与Catalan数相近（但稍有区别），见
n个空填1与0要求从左往右数任何时候1不少于0求方案数？ - 叶落无声的回答 - 知乎

dlpg070

按1#给定条件用程序穷举计算得
{1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924,---}
与按通项公式 a(n) = binomial(n, ceiling(n/2))计算结果相同。
n=10，计算的怒分结果:

{{1, "1010101011", " v
  "}, {2, "1010101101", " v
  "}, {3, "1010101111", "v
  "}, {4, "1010110011", " v
  "}, {5, "1010110101", "
  "}, {6, "1010110111", "
  "}, {7, "1010111001", "
  "}, {8, "1010111011", "
  "}, {9, "1010111101", "
  "}, {10, "1010111111", " v
  "}, {11, "1011001011", "
  "}, {12, "1011001101", "
  "}, {13, "1011001111", "
  "}, {14, "1011010011", "
  "}, {15, "1011010101", "
  "}, {16, "1011010111", "
  "}, {17, "1011011001", "
  "}, {18, "1011011011", "
  "}, {19, "1011011101", "
  "}, {20, "1011011111", " v
  "}, {21, "1011100011", "
  "}, {22, "1011100101", "
  "}, {23, "1011100111", "
  "}, {24, "1011101001", "
  "}, {25, "1011101011", "
  "}, {26, "1011101101", "
  "}, {27, "1011101111", "
  "}, {28, "1011110001", "
  "}, {29, "1011110011", "
  "}, {30, "1011110101", " v
  "}, {31, "1011110111", "
  "}, {32, "1011111001", "
  "}, {33, "1011111011", "
  "}, {34, "1011111101", "
  "}, {35, "1011111111", "
  "}, {36, "1100101011", "
  "}, {37, "1100101101", "
  "}, {38, "1100101111", "
  "}, {39, "1100110011", "
  "}, {40, "1100110101", " v
  "}, {41, "1100110111", "
  "}, {42, "1100111001", "
  "}, {43, "1100111011", "
  "}, {44, "1100111101", "
  "}, {45, "1100111111", " v
  "}, {46, "1101001011", " v
  "}, {47, "1101001101", " v
  "}, {48, "1101001111", " v
  "}, {49, "1101010011", " v
  "}, {50, "1101010101", "
  "}, {51, "1101010111", "
  "}, {52, "1101011001", "
  "}, {53, "1101011011", "
  "}, {54, "1101011101", "
  "}, {55, "1101011111", "
  "}, {56, "1101100011", "
  "}, {57, "1101100101", "
  "}, {58, "1101100111", "
  "}, {59, "1101101001", "
  "}, {60, "1101101011", "
  "}, {61, "1101101101", "
  "}, {62, "1101101111", "
  "}, {63, "1101110001", "
  "}, {64, "1101110011", "
  "}, {65, "1101110101", "
  "}, {66, "1101110111", "
  "}, {67, "1101111001", "
  "}, {68, "1101111011", "
  "}, {69, "1101111101", "
  "}, {70, "1101111111", "
  "}, {71, "1110001011", "
  "}, {72, "1110001101", "
  "}, {73, "1110001111", "
  "}, {74, "1110010011", "
  "}, {75, "1110010101", "
  "}, {76, "1110010111", "
  "}, {77, "1110011001", "
  "}, {78, "1110011011", "
  "}, {79, "1110011101", "
  "}, {80, "1110011111", "
  "}, {81, "1110100011", "
  "}, {82, "1110100101", "
  "}, {83, "1110100111", "
  "}, {84, "1110101001", "
  "}, {85, "1110101011", "
  "}, {86, "1110101101", "
  "}, {87, "1110101111", "
  "}, {88, "1110110001", "
  "}, {89, "1110110011", "
  "}, {90, "1110110101", "
  "}, {91, "1110110111", "
  "}, {92, "1110111001", "
  "}, {93, "1110111011", "
  "}, {94, "1110111101", "
  "}, {95, "1110111111", "
  "}, {96, "1111000011", "
  "}, {97, "1111000101", "
  "}, {98, "1111000111", "
  "}, {99, "1111001001", "
  "}, {100, "1111001011", "
  "}, {101, "1111001101", "
  "}, {102, "1111001111", "
  "}, {103, "1111010001", "
  "}, {104, "1111010011", "
  "}, {105, "1111010101", "
  "}, {106, "1111010111", "
  "}, {107, "1111011001", "
  "}, {108, "1111011011", "
  "}, {109, "1111011101", "
  "}, {110, "1111011111", "
  "}, {111, "1111100001", "
  "}, {112, "1111100011", "
  "}, {113, "1111100101", "
  "}, {114, "1111100111", "
  "}, {115, "1111101001", "
  "}, {116, "1111101011", "
  "}, {117, "1111101101", "
  "}, {118, "1111101111", "
  "}, {119, "1111110001", "
  "}, {120, "1111110011", "
  "}, {121, "1111110101", "
  "}, {122, "1111110111", "
  "}, {123, "1111111001", "
  "}, {124, "1111111011", "
  "}, {125, "1111111101", "
  "}, {126, "1111111111", "
  "}}

dlpg070

kastin 7#:
网上有人问过同样的问题，与Catalan数相近（但稍有区别），见
n个空填1与0要求从左往右数任何时候1不少于0求方案数？ - 叶落无声的回答 - 知乎

两者略有区别，那里不要求个位数为1。

dlpg070

与Catalan数区别太大了:
此处a(n)= {1,2,3, 6,10, 20, 35,  70, 126,---}
Catalan数={1,2,5,14,42,132,429,1430,4862,---}
由后者表前者的表达式太复杂了。