l*******s
发帖数: 7316 | 1 用0,1,2,3,4,5,6,7,8,9 这10个数为各位的数字构成一个10位数，每个数只用1次。
问这些10位数中有多少个满足以下条件：
10位数中的任意3位（可以不是相邻的）都不是递减的。
比如3241 中的321就是递减的，而3412就没有任何3位是递减的。
注意：0123456789不是10位数，因为首位不能为0。
老规矩：两小时内只说答案，解题方法不限。
两小时后开始讨论，给出最简明解法的也有包子。 | H******7
发帖数: 34403 | | l**k
发帖数: 45267 | 3 意思就是０１２３４５６７８９中８个不动，挑２个出来插队，那不很简单么？
【在 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
发帖数: 7316 | 4 注意：0123456789不是10位数，因为首位不能为0。 | h*********g
发帖数: 1812 | | M*****e
发帖数: 11621 | 6 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
发帖数: 7316 | 7 这题是不是难度太高了？
【在 M*****e 的大作中提到】
: 11934?
| M*****e
发帖数: 11621 | 8 也有一大部分人在看球打嘴仗，无心学术
【在 l*******s 的大作中提到】
: 这题是不是难度太高了？
| l*******s
发帖数: 7316 | 9 你的答案是对的。等待简明解题方法。
题目出得很失败，下次改进。
【在 M*****e 的大作中提到】
: 11934?
| n****e
发帖数: 629 | 10 思路是考虑最大的放哪？然后可以推一个递推式？然后从2个数开始 可以推3个，。。
直到10个？然后还要考虑下0不能放左边的特殊情况？
更一般的，如果有N个数x1,...,xN。不能有k个连续大。一共几种排放法？
【在 M*****e 的大作中提到】
: 11934?
| | | n****e
发帖数: 629 | 11 N/k的情况是个很好的DP算法题。我貌似在leetcode看到过...
【在 n****e 的大作中提到】
: 思路是考虑最大的放哪？然后可以推一个递推式？然后从2个数开始 可以推3个，。。
: 直到10个？然后还要考虑下0不能放左边的特殊情况？
: 更一般的，如果有N个数x1,...,xN。不能有k个连续大。一共几种排放法？
| x****o
发帖数: 21566 | 12 我们都在啪啪啪，吊丝现在才会解数学题
【在 M*****e 的大作中提到】
: 也有一大部分人在看球打嘴仗，无心学术
| l*******s
发帖数: 7316 | 13 有简单的公式：
C(20,10)/11 - C(18,9)/10
或
C(20,10)-C(20,9)-C(18,9)+C(18,8) | T******e
发帖数: 18290 | 14 是啪别人还是被啪了？
【在 x****o 的大作中提到】
: 我们都在啪啪啪，吊丝现在才会解数学题
| n****e
发帖数: 629 | 15 看起来和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
发帖数: 7316 | 16 对。
【在 n****e 的大作中提到】
: 看起来和Catalan number有关啊
| n****e
发帖数: 629 | 17 N/k的普遍有公式么
【在 l*******s 的大作中提到】
: 对。
| x****o
发帖数: 21566 | 18 自己啪啪啪，手都拍红了
【在 T******e 的大作中提到】
: 是啪别人还是被啪了？
| n****e
发帖数: 629 | 19 知道答案证明也不难
不过想到答案还是挺巧妙的
【在 l*******s 的大作中提到】
: 对。
| M*****e
发帖数: 11621 | 20 我没简明方法，就是递归了，发现和Catalan的括号配对定义可以建立一一对应。
【在 l*******s 的大作中提到】
: 你的答案是对的。等待简明解题方法。
: 题目出得很失败，下次改进。
| | | M*****e
发帖数: 11621 | 21 题目很好。的确是最近除骚客版以外的地方都生意惨淡。。。
【在 l*******s 的大作中提到】
: 你的答案是对的。等待简明解题方法。
: 题目出得很失败，下次改进。
| l*******s
发帖数: 7316 | 22 括号配对有直接求解的方法，不需要递归。
有简单的方法证明跟括号配对一一对应吗？
能一页纸上写完就算简单。
【在 M*****e 的大作中提到】
: 我没简明方法，就是递归了，发现和Catalan的括号配对定义可以建立一一对应。
| M*****e
发帖数: 11621 | 23 证明部分留给你了 :) 不知道这个算不算一页
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
发帖数: 7316 | 24 你这个证明稍整理一下可以发表了。 你去查一下，目前已有的证明好像都很复杂
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
发帖数: 11748 | 25 不明觉厉
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
发帖数: 629 | 26 继续拜读
往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
发帖数: 6785 | 27 现了真身
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
发帖数: 11621 | 28 好像已经发表在买提顶尖期刊学术版了……
我把第二个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
发帖数: 7316 | 29 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) | K*****2
发帖数: 9308 | | | | l*******s
发帖数: 7316 | 31 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.
| l*******s
发帖数: 7316 | 32 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.
| M*****e
发帖数: 11621 | 33 对。靠，我可真大意，一篇帖子这么多笔误。
【在 l*******s 的大作中提到】
: 132的c_3=1？
:
: 2
: to
: =
: with
: .
| M*****e
发帖数: 11621 | 34 恩。
【在 l*******s 的大作中提到】
: c_i的定义可以简单点。
: c_i=s_{(i)}的尾部单调递增的位数
:
: 2
: to
: =
: with
: .
| l*******s
发帖数: 7316 | 35 笔误难免，思路最重要。我这样的门外汉景仰的很。
我想你可能是想举个例子跟前面的 ()(()) 对应，用312旧对了。
你去掉m(s)的定义，直接从构造括号对，和从1开始构造多位数开讲，应该很简明易懂。
【在 M*****e 的大作中提到】
: 对。靠，我可真大意，一篇帖子这么多笔误。
| M*****e
发帖数: 11621 | 36 为了你严谨的学术态度，我又写了一遍，但我语言组织能力差，看上去似乎更长了……
主要是在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
发帖数: 7316 | 37 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
| M*****e
发帖数: 11621 | 38 行。咱投哪里？
【在 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
发帖数: 8285 | 39 求挂名。。
【在 M*****e 的大作中提到】
: 好像已经发表在买提顶尖期刊学术版了……
: 我把第二个s_i改得复杂了点，赞严谨。
| M*****e
发帖数: 11621 | 40 老朋友见者有份
【在 z***i 的大作中提到】
: 求挂名。。
| | | l*******s
发帖数: 7316 | 41 不知道，我不是数学专业。
【在 M*****e 的大作中提到】
: 行。咱投哪里？
| l*******s
发帖数: 7316 | 42 我没改写错吧？
【在 M*****e 的大作中提到】
: 行。咱投哪里？
| z***i
发帖数: 8285 | 43 你们把娱乐搞成这样太牛了。。
【在 M*****e 的大作中提到】
: 老朋友见者有份
| M*****e
发帖数: 11621 | 44 没，你写得很好。
【在 l*******s 的大作中提到】
: 我没改写错吧？
| M*****e
发帖数: 11621 | 45 预防老年痴呆
【在 z***i 的大作中提到】
: 你们把娱乐搞成这样太牛了。。
| z***i
发帖数: 8285 | 46 静芬为什么不见了
【在 M*****e 的大作中提到】
: 预防老年痴呆
| M*****e
发帖数: 11621 | 47 闭关抱小孩去了
【在 z***i 的大作中提到】
: 静芬为什么不见了
| l*******s
发帖数: 7316 | 48 NBA 季后赛期间，静芬在蓝球板蹲点。现在季后赛结束了，静芬又会来露面了。
【在 z***i 的大作中提到】
: 静芬为什么不见了
| n****e
发帖数: 629 | 49 我其实还写了一个和对角线走法一一对应的证明
看了您的皇皇巨著 不敢贴了
【在 M*****e 的大作中提到】
: 预防老年痴呆
| M*****e
发帖数: 11621 | 50 原来如此。我们都被蒙蔽了。
【在 l*******s 的大作中提到】
: NBA 季后赛期间，静芬在蓝球板蹲点。现在季后赛结束了，静芬又会来露面了。
| | | M*****e
发帖数: 11621 | 51 这是讽刺我表达能力弱，写得太长吧
【在 n****e 的大作中提到】
: 我其实还写了一个和对角线走法一一对应的证明
: 看了您的皇皇巨著 不敢贴了
| n****e
发帖数: 629 | 52 功底扎实
我们都是半路出家的
和那个刘进三角差不多
【在 M*****e 的大作中提到】
: 这是讽刺我表达能力弱，写得太长吧
| M*****e
发帖数: 11621 | 53 胡戴高帽要不得
您快贴解法吧
【在 n****e 的大作中提到】
: 功底扎实
: 我们都是半路出家的
: 和那个刘进三角差不多
| z***i
发帖数: 8285 | 54 想起了湖人的贾巴尔，可能是二十年前看的了
静芬居然看篮球
【在 l*******s 的大作中提到】
: NBA 季后赛期间，静芬在蓝球板蹲点。现在季后赛结束了，静芬又会来露面了。
| z*****3
发帖数: 15515 | 55 我是科黑+詹蜜...
随便灌个水就能发paper了，数学家就是牛
【在 z***i 的大作中提到】
: 想起了湖人的贾巴尔，可能是二十年前看的了
: 静芬居然看篮球
|
|
