数学题, 两小时内答对的有包子# Joke - 肚皮舞运动
j*3
1 楼
我用最直接的方法，把他们都存到数组里，然后从左到右扫一遍。。。找到顺序乱的。。
但这个方法space o(n)
有啥好主意？还想到了用俩pointer那个方法，但这个不知道是否可行。。。
但这个方法space o(n)
有啥好主意？还想到了用俩pointer那个方法，但这个不知道是否可行。。。
l*s
2 楼
用0,1,2,3,4,5,6,7,8,9 这10个数为各位的数字构成一个10位数，每个数只用1次。
问这些10位数中有多少个满足以下条件：
10位数中的任意3位（可以不是相邻的）都不是递减的。
比如3241 中的321就是递减的，而3412就没有任何3位是递减的。
注意：0123456789不是10位数，因为首位不能为0。
老规矩：两小时内只说答案，解题方法不限。
两小时后开始讨论，给出最简明解法的也有包子。
问这些10位数中有多少个满足以下条件：
10位数中的任意3位（可以不是相邻的）都不是递减的。
比如3241 中的321就是递减的，而3412就没有任何3位是递减的。
注意：0123456789不是10位数，因为首位不能为0。
老规矩：两小时内只说答案，解题方法不限。
两小时后开始讨论，给出最简明解法的也有包子。
g*o
3 楼
啥意思?
存到数组里后找longest increasing subsequence?
存到数组里后找longest increasing subsequence?
H*7
4 楼
乐见WSN嗷嗷地扑上来抢食
s*l
5 楼
最大bst是说个数最多吗？
我觉得不用extra space把~
从底向上 返回每个node下 最大bst的个数 要是
有新的最大值就更新max
这样应该可以把~
我觉得不用extra space把~
从底向上 返回每个node下 最大bst的个数 要是
有新的最大值就更新max
这样应该可以把~
l*k
6 楼
意思就是０１２３４５６７８９中８个不动，挑２个出来插队，那不很简单么？
【在 l*******s 的大作中提到】
: 用0,1,2,3,4,5,6,7,8,9 这10个数为各位的数字构成一个10位数，每个数只用1次。
: 问这些10位数中有多少个满足以下条件：
: 10位数中的任意3位（可以不是相邻的）都不是递减的。
: 比如3241 中的321就是递减的，而3412就没有任何3位是递减的。
: 注意：0123456789不是10位数，因为首位不能为0。
: 老规矩：两小时内只说答案，解题方法不限。
: 两小时后开始讨论，给出最简明解法的也有包子。
【在 l*******s 的大作中提到】
: 用0,1,2,3,4,5,6,7,8,9 这10个数为各位的数字构成一个10位数，每个数只用1次。
: 问这些10位数中有多少个满足以下条件：
: 10位数中的任意3位（可以不是相邻的）都不是递减的。
: 比如3241 中的321就是递减的，而3412就没有任何3位是递减的。
: 注意：0123456789不是10位数，因为首位不能为0。
: 老规矩：两小时内只说答案，解题方法不限。
: 两小时后开始讨论，给出最简明解法的也有包子。
j*3
7 楼
对的
我知道这个办法并不好
【在 g****o 的大作中提到】
: 啥意思?
: 存到数组里后找longest increasing subsequence?
我知道这个办法并不好
【在 g****o 的大作中提到】
: 啥意思?
: 存到数组里后找longest increasing subsequence?
l*s
8 楼
注意：0123456789不是10位数，因为首位不能为0。
j*3
9 楼
好像可以哦。。
楼主说的第二个方法可以么？
【在 s********l 的大作中提到】
: 最大bst是说个数最多吗？
: 我觉得不用extra space把~
: 从底向上 返回每个node下 最大bst的个数 要是
: 有新的最大值就更新max
: 这样应该可以把~
楼主说的第二个方法可以么？
【在 s********l 的大作中提到】
: 最大bst是说个数最多吗？
: 我觉得不用extra space把~
: 从底向上 返回每个node下 最大bst的个数 要是
: 有新的最大值就更新max
: 这样应该可以把~
h*g
10 楼
学术版就是学术版
i*u
11 楼
中序遍历 最长递增序列
M*e
12 楼
11934?
【在 l*******s 的大作中提到】
: 用0,1,2,3,4,5,6,7,8,9 这10个数为各位的数字构成一个10位数，每个数只用1次。
: 问这些10位数中有多少个满足以下条件：
: 10位数中的任意3位（可以不是相邻的）都不是递减的。
: 比如3241 中的321就是递减的，而3412就没有任何3位是递减的。
: 注意：0123456789不是10位数，因为首位不能为0。
: 老规矩：两小时内只说答案，解题方法不限。
: 两小时后开始讨论，给出最简明解法的也有包子。
【在 l*******s 的大作中提到】
: 用0,1,2,3,4,5,6,7,8,9 这10个数为各位的数字构成一个10位数，每个数只用1次。
: 问这些10位数中有多少个满足以下条件：
: 10位数中的任意3位（可以不是相邻的）都不是递减的。
: 比如3241 中的321就是递减的，而3412就没有任何3位是递减的。
: 注意：0123456789不是10位数，因为首位不能为0。
: 老规矩：两小时内只说答案，解题方法不限。
: 两小时后开始讨论，给出最简明解法的也有包子。
j*3
13 楼
其实不需要存，是吧？
【在 i**********u 的大作中提到】
: 中序遍历 最长递增序列
【在 i**********u 的大作中提到】
: 中序遍历 最长递增序列
l*s
14 楼
这题是不是难度太高了？
【在 M*****e 的大作中提到】
: 11934?
【在 M*****e 的大作中提到】
: 11934?
a*a
15 楼
Time: O(n), Space: O(1)应该能作到.
with Poster-Order process, recursively call on the left/right children,
which returns:
1. The largest BST size in this branch
2. The largest BST size in this branch starting with the root
3. The value range [min, max] of the BST in (2)
Based on this information returned from left/right children, the current
root can easily figure out the things it needs to return itself.
with Poster-Order process, recursively call on the left/right children,
which returns:
1. The largest BST size in this branch
2. The largest BST size in this branch starting with the root
3. The value range [min, max] of the BST in (2)
Based on this information returned from left/right children, the current
root can easily figure out the things it needs to return itself.
M*e
16 楼
也有一大部分人在看球打嘴仗，无心学术
【在 l*******s 的大作中提到】
: 这题是不是难度太高了？
【在 l*******s 的大作中提到】
: 这题是不是难度太高了？
h*k
17 楼
recursion is never space O1, except tail recursion
【在 a***a 的大作中提到】
: Time: O(n), Space: O(1)应该能作到.
: with Poster-Order process, recursively call on the left/right children,
: which returns:
: 1. The largest BST size in this branch
: 2. The largest BST size in this branch starting with the root
: 3. The value range [min, max] of the BST in (2)
: Based on this information returned from left/right children, the current
: root can easily figure out the things it needs to return itself.
【在 a***a 的大作中提到】
: Time: O(n), Space: O(1)应该能作到.
: with Poster-Order process, recursively call on the left/right children,
: which returns:
: 1. The largest BST size in this branch
: 2. The largest BST size in this branch starting with the root
: 3. The value range [min, max] of the BST in (2)
: Based on this information returned from left/right children, the current
: root can easily figure out the things it needs to return itself.
l*s
18 楼
你的答案是对的。等待简明解题方法。
题目出得很失败，下次改进。
【在 M*****e 的大作中提到】
: 11934?
题目出得很失败，下次改进。
【在 M*****e 的大作中提到】
: 11934?
n*e
19 楼
思路是考虑最大的放哪？然后可以推一个递推式？然后从2个数开始 可以推3个，。。
直到10个？然后还要考虑下0不能放左边的特殊情况？
更一般的，如果有N个数x1,...,xN。不能有k个连续大。一共几种排放法？
【在 M*****e 的大作中提到】
: 11934?
直到10个？然后还要考虑下0不能放左边的特殊情况？
更一般的，如果有N个数x1,...,xN。不能有k个连续大。一共几种排放法？
【在 M*****e 的大作中提到】
: 11934?
n*e
20 楼
N/k的情况是个很好的DP算法题。我貌似在leetcode看到过...
【在 n****e 的大作中提到】
: 思路是考虑最大的放哪？然后可以推一个递推式？然后从2个数开始 可以推3个，。。
: 直到10个？然后还要考虑下0不能放左边的特殊情况？
: 更一般的，如果有N个数x1,...,xN。不能有k个连续大。一共几种排放法？
【在 n****e 的大作中提到】
: 思路是考虑最大的放哪？然后可以推一个递推式？然后从2个数开始 可以推3个，。。
: 直到10个？然后还要考虑下0不能放左边的特殊情况？
: 更一般的，如果有N个数x1,...,xN。不能有k个连续大。一共几种排放法？
x*o
21 楼
我们都在啪啪啪，吊丝现在才会解数学题
【在 M*****e 的大作中提到】
: 也有一大部分人在看球打嘴仗，无心学术
【在 M*****e 的大作中提到】
: 也有一大部分人在看球打嘴仗，无心学术
l*s
22 楼
有简单的公式：
C(20,10)/11 - C(18,9)/10
或
C(20,10)-C(20,9)-C(18,9)+C(18,8)
C(20,10)/11 - C(18,9)/10
或
C(20,10)-C(20,9)-C(18,9)+C(18,8)
T*e
23 楼
是啪别人还是被啪了？
【在 x****o 的大作中提到】
: 我们都在啪啪啪，吊丝现在才会解数学题
【在 x****o 的大作中提到】
: 我们都在啪啪啪，吊丝现在才会解数学题
n*e
24 楼
看起来和Catalan number有关啊
【在 l*******s 的大作中提到】
: 有简单的公式：
: C(20,10)/11 - C(18,9)/10
: 或
: C(20,10)-C(20,9)-C(18,9)+C(18,8)
【在 l*******s 的大作中提到】
: 有简单的公式：
: C(20,10)/11 - C(18,9)/10
: 或
: C(20,10)-C(20,9)-C(18,9)+C(18,8)
l*s
25 楼
对。
【在 n****e 的大作中提到】
: 看起来和Catalan number有关啊
【在 n****e 的大作中提到】
: 看起来和Catalan number有关啊
n*e
26 楼
N/k的普遍有公式么
【在 l*******s 的大作中提到】
: 对。
【在 l*******s 的大作中提到】
: 对。
x*o
27 楼
自己啪啪啪，手都拍红了
【在 T******e 的大作中提到】
: 是啪别人还是被啪了？
【在 T******e 的大作中提到】
: 是啪别人还是被啪了？
n*e
28 楼
知道答案证明也不难
不过想到答案还是挺巧妙的
【在 l*******s 的大作中提到】
: 对。
不过想到答案还是挺巧妙的
【在 l*******s 的大作中提到】
: 对。
M*e
29 楼
我没简明方法，就是递归了，发现和Catalan的括号配对定义可以建立一一对应。
【在 l*******s 的大作中提到】
: 你的答案是对的。等待简明解题方法。
: 题目出得很失败，下次改进。
【在 l*******s 的大作中提到】
: 你的答案是对的。等待简明解题方法。
: 题目出得很失败，下次改进。
M*e
30 楼
题目很好。的确是最近除骚客版以外的地方都生意惨淡。。。
【在 l*******s 的大作中提到】
: 你的答案是对的。等待简明解题方法。
: 题目出得很失败，下次改进。
【在 l*******s 的大作中提到】
: 你的答案是对的。等待简明解题方法。
: 题目出得很失败，下次改进。
l*s
31 楼
括号配对有直接求解的方法，不需要递归。
有简单的方法证明跟括号配对一一对应吗？
能一页纸上写完就算简单。
【在 M*****e 的大作中提到】
: 我没简明方法，就是递归了，发现和Catalan的括号配对定义可以建立一一对应。
有简单的方法证明跟括号配对一一对应吗？
能一页纸上写完就算简单。
【在 M*****e 的大作中提到】
: 我没简明方法，就是递归了，发现和Catalan的括号配对定义可以建立一一对应。
M*e
32 楼
证明部分留给你了 :) 不知道这个算不算一页
A_n = {n pairs of parentheses in the Catalan sense}
B_n = {321-avoiding permutations in S_n}
C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
, ()()(()) has c = 3.
For any s in B_n, let m(s) be the number of positions one can insert n+1 to
get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
A_n C_n: take any t in A_n, reconstruct it according to the order of “)
”, from left to right. The corresponding element in C_n is the number of
components c_i at each stage. For example, ()(()) is reconstructed as () ->
()() -> ()(()), and it has c_1 = 1, c_2 = c_3 = 2. It's not hard to see this
is a bijection.
B_n C_n: take any s in B_n, and check all the subsequences s_{(i)} made
of {1,...,i} for any i. Let c_i be m(s_{(i)})-1. For example, 312 has
subsequences 1, 12, 312, which maps to c_1 = 1, c_2 = c_3 = 2. It's a
straightforward exercise to prove this is also a bijection.
【在 l*******s 的大作中提到】
: 括号配对有直接求解的方法，不需要递归。
: 有简单的方法证明跟括号配对一一对应吗？
: 能一页纸上写完就算简单。
A_n = {n pairs of parentheses in the Catalan sense}
B_n = {321-avoiding permutations in S_n}
C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
, ()()(()) has c = 3.
For any s in B_n, let m(s) be the number of positions one can insert n+1 to
get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
A_n C_n: take any t in A_n, reconstruct it according to the order of “)
”, from left to right. The corresponding element in C_n is the number of
components c_i at each stage. For example, ()(()) is reconstructed as () ->
()() -> ()(()), and it has c_1 = 1, c_2 = c_3 = 2. It's not hard to see this
is a bijection.
B_n C_n: take any s in B_n, and check all the subsequences s_{(i)} made
of {1,...,i} for any i. Let c_i be m(s_{(i)})-1. For example, 312 has
subsequences 1, 12, 312, which maps to c_1 = 1, c_2 = c_3 = 2. It's a
straightforward exercise to prove this is also a bijection.
【在 l*******s 的大作中提到】
: 括号配对有直接求解的方法，不需要递归。
: 有简单的方法证明跟括号配对一一对应吗？
: 能一页纸上写完就算简单。
l*s
33 楼
你这个证明稍整理一下可以发表了。 你去查一下，目前已有的证明好像都很复杂
http://www.emis.de/journals/SLC/wpapers/s60stump.pdf
http://www.sciencedirect.com/science/article/pii/S0166218X06000
你两处s_i一个表示第i位，一个表示由1到i组成的子串，需要区分一下。
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
http://www.emis.de/journals/SLC/wpapers/s60stump.pdf
http://www.sciencedirect.com/science/article/pii/S0166218X06000
你两处s_i一个表示第i位，一个表示由1到i组成的子串，需要区分一下。
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
l*i
34 楼
不明觉厉
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
n*e
35 楼
继续拜读
往Catalan上凑
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
往Catalan上凑
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
p*e
36 楼
现了真身
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
M*e
37 楼
好像已经发表在买提顶尖期刊学术版了……
我把第二个s_i改得复杂了点，赞严谨。
【在 l*******s 的大作中提到】
: 你这个证明稍整理一下可以发表了。 你去查一下，目前已有的证明好像都很复杂
: http://www.emis.de/journals/SLC/wpapers/s60stump.pdf
: http://www.sciencedirect.com/science/article/pii/S0166218X06000
: 你两处s_i一个表示第i位，一个表示由1到i组成的子串，需要区分一下。
:
: 2
: to
: =
: with
: .
我把第二个s_i改得复杂了点，赞严谨。
【在 l*******s 的大作中提到】
: 你这个证明稍整理一下可以发表了。 你去查一下，目前已有的证明好像都很复杂
: http://www.emis.de/journals/SLC/wpapers/s60stump.pdf
: http://www.sciencedirect.com/science/article/pii/S0166218X06000
: 你两处s_i一个表示第i位，一个表示由1到i组成的子串，需要区分一下。
:
: 2
: to
: =
: with
: .
l*s
38 楼
Catalan number 直接公式的推导：
令1表示左括号，0表示右括号，则n对括号可转化为求一个2n位、含n个1、n个0的二进
制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含n个1、n个0的2n
位二进制数共有C(2n,n)个，下面考虑不满足要求的数目。
考虑一个含n个1、n个0的2n位二进制数，扫描到第2m+1位上时有m+1个0和m个1（容易证
明一定存在这样的情况），则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以
后的部分0变成1、1变成0，则对应一个n+1个0和n-1个1的二进制数。反之亦然（相似的
思路证明两者一一对应）。
从而C_n = C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)
令1表示左括号，0表示右括号，则n对括号可转化为求一个2n位、含n个1、n个0的二进
制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含n个1、n个0的2n
位二进制数共有C(2n,n)个，下面考虑不满足要求的数目。
考虑一个含n个1、n个0的2n位二进制数，扫描到第2m+1位上时有m+1个0和m个1（容易证
明一定存在这样的情况），则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以
后的部分0变成1、1变成0，则对应一个n+1个0和n-1个1的二进制数。反之亦然（相似的
思路证明两者一一对应）。
从而C_n = C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)
K*2
39 楼
你们太nb了，卡特兰数是啥我都快想不起来了
l*s
40 楼
132的c_3=1？
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
l*s
41 楼
c_i的定义可以简单点。
c_i=s_{(i)}的尾部单调递增的位数
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
c_i=s_{(i)}的尾部单调递增的位数
2
to
=
with
.
【在 M*****e 的大作中提到】
: 证明部分留给你了 :) 不知道这个算不算一页
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1}
: For any t in A_n, let c(t) be the number of components. E.g., ()() has c = 2
: , ()()(()) has c = 3.
: For any s in B_n, let m(s) be the number of positions one can insert n+1 to
: get an element in B_{n+1}. To be more explicit, if s = 123..n, then m(s) =
: n+1, otherwise there is a largest j(necessarily <= n-1) that has an i>j with
: s_i < s_j, and in this case m(s) = n-j+1. One always has 2 <= m(s) <= n+1.
M*e
42 楼
对。靠，我可真大意，一篇帖子这么多笔误。
【在 l*******s 的大作中提到】
: 132的c_3=1？
:
: 2
: to
: =
: with
: .
【在 l*******s 的大作中提到】
: 132的c_3=1？
:
: 2
: to
: =
: with
: .
M*e
43 楼
恩。
【在 l*******s 的大作中提到】
: c_i的定义可以简单点。
: c_i=s_{(i)}的尾部单调递增的位数
:
: 2
: to
: =
: with
: .
【在 l*******s 的大作中提到】
: c_i的定义可以简单点。
: c_i=s_{(i)}的尾部单调递增的位数
:
: 2
: to
: =
: with
: .
l*s
44 楼
笔误难免，思路最重要。我这样的门外汉景仰的很。
我想你可能是想举个例子跟前面的 ()(()) 对应，用312旧对了。
你去掉m(s)的定义，直接从构造括号对，和从1开始构造多位数开讲，应该很简明易懂。
【在 M*****e 的大作中提到】
: 对。靠，我可真大意，一篇帖子这么多笔误。
我想你可能是想举个例子跟前面的 ()(()) 对应，用312旧对了。
你去掉m(s)的定义，直接从构造括号对，和从1开始构造多位数开讲，应该很简明易懂。
【在 M*****e 的大作中提到】
: 对。靠，我可真大意，一篇帖子这么多笔误。
M*e
45 楼
为了你严谨的学术态度，我又写了一遍，但我语言组织能力差，看上去似乎更长了……
主要是在C_n B_n 这段，为了和前面的可以无缝连接，我把它反过来写了，原帖
的方向描述更简单些。
A_n = {n pairs of parentheses in the Catalan sense}
B_n = {321-avoiding permutations in S_n}
C_n = {n-integer sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1 for i>=
2}
A_n C_n: take any t in A_n, and reconstruct it according to the order of
“)”, from left to right. The corresponding element in C_n is built by the
number of components c_i at each stage. For example, ()(()) is
reconstructed as () -> ()() -> ()(()), and it has component numbers c_1 = 1,
c_2 = c_3 = 2.
C_n B_n: for any c in C_n, one can construct an element in B_n as
follows. First write down 1 for c_1 = 1, trivially in B_1. At stage i >= 2,
suppose we already have a 321-avoiding permutation sequence, with the length
of the last ascending run(*) c_{i-1}, we insert i into one of the c_{i-1} +
1 spaces the ascending run has, so that new last ascending run has length c
_i. For any c_i in [1, c_{i-1} + 1], the choice exists and is unique. It's
not hard to see the insertion keeps the sequence 321-free. For example, for
c_1 = 1, c_2 = c_3 = 2, we get 1, 12, 312 as our permutation sequence.
It's a straightforward exercise to prove both maps are bijective.
*: An ascending run of a permutation is a nonempty increasing contiguous
subsequence of the permutation that cannot be extended at either end. The
last ascending run in this note is the ascending run that contains the last
element of the sequence.
懂。
【在 l*******s 的大作中提到】
: 笔误难免，思路最重要。我这样的门外汉景仰的很。
: 我想你可能是想举个例子跟前面的 ()(()) 对应，用312旧对了。
: 你去掉m(s)的定义，直接从构造括号对，和从1开始构造多位数开讲，应该很简明易懂。
主要是在C_n B_n 这段，为了和前面的可以无缝连接，我把它反过来写了，原帖
的方向描述更简单些。
A_n = {n pairs of parentheses in the Catalan sense}
B_n = {321-avoiding permutations in S_n}
C_n = {n-integer sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1 for i>=
2}
A_n C_n: take any t in A_n, and reconstruct it according to the order of
“)”, from left to right. The corresponding element in C_n is built by the
number of components c_i at each stage. For example, ()(()) is
reconstructed as () -> ()() -> ()(()), and it has component numbers c_1 = 1,
c_2 = c_3 = 2.
C_n B_n: for any c in C_n, one can construct an element in B_n as
follows. First write down 1 for c_1 = 1, trivially in B_1. At stage i >= 2,
suppose we already have a 321-avoiding permutation sequence, with the length
of the last ascending run(*) c_{i-1}, we insert i into one of the c_{i-1} +
1 spaces the ascending run has, so that new last ascending run has length c
_i. For any c_i in [1, c_{i-1} + 1], the choice exists and is unique. It's
not hard to see the insertion keeps the sequence 321-free. For example, for
c_1 = 1, c_2 = c_3 = 2, we get 1, 12, 312 as our permutation sequence.
It's a straightforward exercise to prove both maps are bijective.
*: An ascending run of a permutation is a nonempty increasing contiguous
subsequence of the permutation that cannot be extended at either end. The
last ascending run in this note is the ascending run that contains the last
element of the sequence.
懂。
【在 l*******s 的大作中提到】
: 笔误难免，思路最重要。我这样的门外汉景仰的很。
: 我想你可能是想举个例子跟前面的 ()(()) 对应，用312旧对了。
: 你去掉m(s)的定义，直接从构造括号对，和从1开始构造多位数开讲，应该很简明易懂。
l*s
46 楼
A_n = {n pairs of valid parentheses}
B_n = {321-avoiding permutations in S_n}
For any a_i in A_i, c(a_i) is defined as number of pairs of
parentheses in a_i which are not within any other parentheses.
For any a_n in A_n, (c(a_n,1),c(a_n,2),...c(a_n,n)) is called
construction sequence of a_n,
where a_n,i is sub-sequence of a_n made of of first i ")"s
and their corresponding "("s.
For example the construction sequence of ()(()) is (1,2,2)
For any b_i in B_i, c(b_i) is defined as maximum number elements
in increasing order at end of b_i.
For any b_n in B_n, (c(b_n,1),c(b_n,2),...c(b_n,n)) is called
construction sequence of b_n,
where b_n,i is sub-sequence of b_n made of first i elements in S_n.
For example the construction sequence of 312 is (1,2,2)
It is clear that A_n and B_n are bijection by mapping elements
in A_n to B_n with same construction sequence and vice versa.
>=
of
the
【在 M*****e 的大作中提到】
: 为了你严谨的学术态度，我又写了一遍，但我语言组织能力差，看上去似乎更长了……
: 主要是在C_n B_n 这段，为了和前面的可以无缝连接，我把它反过来写了，原帖
: 的方向描述更简单些。
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-integer sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1 for i>=
: 2}
: A_n C_n: take any t in A_n, and reconstruct it according to the order of
: “)”, from left to right. The corresponding element in C_n is built by the
: number of components c_i at each stage. For example, ()(()) is
B_n = {321-avoiding permutations in S_n}
For any a_i in A_i, c(a_i) is defined as number of pairs of
parentheses in a_i which are not within any other parentheses.
For any a_n in A_n, (c(a_n,1),c(a_n,2),...c(a_n,n)) is called
construction sequence of a_n,
where a_n,i is sub-sequence of a_n made of of first i ")"s
and their corresponding "("s.
For example the construction sequence of ()(()) is (1,2,2)
For any b_i in B_i, c(b_i) is defined as maximum number elements
in increasing order at end of b_i.
For any b_n in B_n, (c(b_n,1),c(b_n,2),...c(b_n,n)) is called
construction sequence of b_n,
where b_n,i is sub-sequence of b_n made of first i elements in S_n.
For example the construction sequence of 312 is (1,2,2)
It is clear that A_n and B_n are bijection by mapping elements
in A_n to B_n with same construction sequence and vice versa.
>=
of
the
【在 M*****e 的大作中提到】
: 为了你严谨的学术态度，我又写了一遍，但我语言组织能力差，看上去似乎更长了……
: 主要是在C_n B_n 这段，为了和前面的可以无缝连接，我把它反过来写了，原帖
: 的方向描述更简单些。
: A_n = {n pairs of parentheses in the Catalan sense}
: B_n = {321-avoiding permutations in S_n}
: C_n = {n-integer sequence with c_1 = 1, and 1 <= c_i <= c_{i-1} + 1 for i>=
: 2}
: A_n C_n: take any t in A_n, and reconstruct it according to the order of
: “)”, from left to right. The corresponding element in C_n is built by the
: number of components c_i at each stage. For example, ()(()) is
M*e
47 楼
行。咱投哪里？
【在 l*******s 的大作中提到】
: A_n = {n pairs of valid parentheses}
: B_n = {321-avoiding permutations in S_n}
: For any a_i in A_i, c(a_i) is defined as number of pairs of
: parentheses in a_i which are not within any other parentheses.
: For any a_n in A_n, (c(a_n,1),c(a_n,2),...c(a_n,n)) is called
: construction sequence of a_n,
: where a_n,i is sub-sequence of a_n made of of first i ")"s
: and their corresponding "("s.
: For example the construction sequence of ()(()) is (1,2,2)
: For any b_i in B_i, c(b_i) is defined as maximum number elements
【在 l*******s 的大作中提到】
: A_n = {n pairs of valid parentheses}
: B_n = {321-avoiding permutations in S_n}
: For any a_i in A_i, c(a_i) is defined as number of pairs of
: parentheses in a_i which are not within any other parentheses.
: For any a_n in A_n, (c(a_n,1),c(a_n,2),...c(a_n,n)) is called
: construction sequence of a_n,
: where a_n,i is sub-sequence of a_n made of of first i ")"s
: and their corresponding "("s.
: For example the construction sequence of ()(()) is (1,2,2)
: For any b_i in B_i, c(b_i) is defined as maximum number elements
z*i
48 楼
求挂名。。
【在 M*****e 的大作中提到】
: 好像已经发表在买提顶尖期刊学术版了……
: 我把第二个s_i改得复杂了点，赞严谨。
【在 M*****e 的大作中提到】
: 好像已经发表在买提顶尖期刊学术版了……
: 我把第二个s_i改得复杂了点，赞严谨。
M*e
49 楼
老朋友见者有份
【在 z***i 的大作中提到】
: 求挂名。。
【在 z***i 的大作中提到】
: 求挂名。。
l*s
50 楼
不知道，我不是数学专业。
【在 M*****e 的大作中提到】
: 行。咱投哪里？
【在 M*****e 的大作中提到】
: 行。咱投哪里？
l*s
51 楼
我没改写错吧？
【在 M*****e 的大作中提到】
: 行。咱投哪里？
【在 M*****e 的大作中提到】
: 行。咱投哪里？
z*i
52 楼
你们把娱乐搞成这样太牛了。。
【在 M*****e 的大作中提到】
: 老朋友见者有份
【在 M*****e 的大作中提到】
: 老朋友见者有份
M*e
53 楼
没，你写得很好。
【在 l*******s 的大作中提到】
: 我没改写错吧？
【在 l*******s 的大作中提到】
: 我没改写错吧？
M*e
54 楼
预防老年痴呆
【在 z***i 的大作中提到】
: 你们把娱乐搞成这样太牛了。。
【在 z***i 的大作中提到】
: 你们把娱乐搞成这样太牛了。。
z*i
55 楼
静芬为什么不见了
【在 M*****e 的大作中提到】
: 预防老年痴呆
【在 M*****e 的大作中提到】
: 预防老年痴呆
M*e
56 楼
闭关抱小孩去了
【在 z***i 的大作中提到】
: 静芬为什么不见了
【在 z***i 的大作中提到】
: 静芬为什么不见了
l*s
57 楼
NBA 季后赛期间，静芬在蓝球板蹲点。现在季后赛结束了，静芬又会来露面了。
【在 z***i 的大作中提到】
: 静芬为什么不见了
【在 z***i 的大作中提到】
: 静芬为什么不见了
n*e
58 楼
我其实还写了一个和对角线走法一一对应的证明
看了您的皇皇巨著 不敢贴了
【在 M*****e 的大作中提到】
: 预防老年痴呆
看了您的皇皇巨著 不敢贴了
【在 M*****e 的大作中提到】
: 预防老年痴呆
M*e
59 楼
原来如此。我们都被蒙蔽了。
【在 l*******s 的大作中提到】
: NBA 季后赛期间，静芬在蓝球板蹲点。现在季后赛结束了，静芬又会来露面了。
【在 l*******s 的大作中提到】
: NBA 季后赛期间，静芬在蓝球板蹲点。现在季后赛结束了，静芬又会来露面了。
M*e
60 楼
这是讽刺我表达能力弱，写得太长吧
【在 n****e 的大作中提到】
: 我其实还写了一个和对角线走法一一对应的证明
: 看了您的皇皇巨著 不敢贴了
【在 n****e 的大作中提到】
: 我其实还写了一个和对角线走法一一对应的证明
: 看了您的皇皇巨著 不敢贴了
n*e
61 楼
功底扎实
我们都是半路出家的
和那个刘进三角差不多
【在 M*****e 的大作中提到】
: 这是讽刺我表达能力弱，写得太长吧
我们都是半路出家的
和那个刘进三角差不多
【在 M*****e 的大作中提到】
: 这是讽刺我表达能力弱，写得太长吧
M*e
62 楼
胡戴高帽要不得
您快贴解法吧
【在 n****e 的大作中提到】
: 功底扎实
: 我们都是半路出家的
: 和那个刘进三角差不多
您快贴解法吧
【在 n****e 的大作中提到】
: 功底扎实
: 我们都是半路出家的
: 和那个刘进三角差不多
z*i
63 楼
想起了湖人的贾巴尔，可能是二十年前看的了
静芬居然看篮球
【在 l*******s 的大作中提到】
: NBA 季后赛期间，静芬在蓝球板蹲点。现在季后赛结束了，静芬又会来露面了。
静芬居然看篮球
【在 l*******s 的大作中提到】
: NBA 季后赛期间，静芬在蓝球板蹲点。现在季后赛结束了，静芬又会来露面了。
z*3
64 楼
我是科黑+詹蜜...
随便灌个水就能发paper了，数学家就是牛
【在 z***i 的大作中提到】
: 想起了湖人的贾巴尔，可能是二十年前看的了
: 静芬居然看篮球
随便灌个水就能发paper了，数学家就是牛
【在 z***i 的大作中提到】
: 想起了湖人的贾巴尔，可能是二十年前看的了
: 静芬居然看篮球
相关阅读
当你问美国人中国有哪些城市，韩国和东京已经加入天朝陕西教师网上吐槽强制捐款200，治安拘留五天white nationalists看病拒绝华人医生，要求必须是白人香港法院改判黄之锋、罗冠聪、周永康入狱unidentified_title海日的粉丝好多啊歼15起飞1分钟与鸟群迎面相撞 引擎起火…unidentified_title共产主义就要实现了国内的种族歧视真是嚣张啊正能量unidentified_title“天使粒子”团队内讧了这些中国的三级片女星如果你都不认识，那你真的too young too simple革命新动向zz燕窝到底有没有用我再给大家上一课想要传销绝种国内需要这样做印度的最高法院一辆面包车内塞了14个人，乘客说；你这是超载，被逮着要扣不少分呢！掏耳朵黑头，是我见过人世间最恶心的东西。没有之一