w*******x
发帖数: 489 | 1 12 个人站队站两排，
要求第二排的比第一排高，然后两排都要求从左到右增高
共有多少中站法？ 本来是编程题，但可以直接写出解析解。 | q****x
发帖数: 7404 | 2 题意不清。什么叫第二排比第一排高？是高于所有，还是高于同位置的那个？
【在 w*******x 的大作中提到】
: 12 个人站队站两排，
: 要求第二排的比第一排高，然后两排都要求从左到右增高
: 共有多少中站法？ 本来是编程题，但可以直接写出解析解。
| A**u
发帖数: 2458 | 3 应该高于同一个位置吧
高于所有人的话，就是一条直线没区别了
【在 q****x 的大作中提到】
: 题意不清。什么叫第二排比第一排高？是高于所有，还是高于同位置的那个？
| q****x
发帖数: 7404 | 4 先选一半，x = C(12,6)。
各自排序，x = x / 6!
相应位置选大元素放到后排，x = x / 2^6
【在 A**u 的大作中提到】
: 应该高于同一个位置吧
: 高于所有人的话，就是一条直线没区别了
| A**u
发帖数: 2458 | 5 看不懂.
你这个6! 2^6是什么意思
这东西应该是个动态规划
1只能放在（1,1）
12只能放在(2,6)
然后 2 只能放在(1,2) 或者(2,1)
然后 11 只能放在(2,5) 或者(1,6)
just two cents
【在 q****x 的大作中提到】
: 先选一半，x = C(12,6)。
: 各自排序，x = x / 6!
: 相应位置选大元素放到后排，x = x / 2^6
| l******i
发帖数: 1404 | 6 首先感谢楼主贡献，
如果可以的话，希望楼主最好能在帖子标题里加上问题的类别和关键词，
例如该帖名字可为：【Brain Teaser】出个题目
这样方便我们工作人员整理，谢谢啦。
我已经把标题改了。 | q****x
发帖数: 7404 | 7 生成一组合法序列的过程。以六个为例。
1. 任意等分成两组，例如{ 1, 4, 5 }，{ 2, 3, 6}，共有 C(6, 3) = 6*5*4 = 120.
2. 前后对调，保证个高在后排。上述例子变成{ 1, 3, 5 } { 2, 4, 6 }
这个对调在每个位置有发生和不发生两种情况，所以15种。
那个6!错了。不该有。
【在 A**u 的大作中提到】
: 看不懂.
: 你这个6! 2^6是什么意思
: 这东西应该是个动态规划
: 1只能放在（1,1）
: 12只能放在(2,6)
: 然后 2 只能放在(1,2) 或者(2,1)
: 然后 11 只能放在(2,5) 或者(1,6)
: just two cents
| w*******x
发帖数: 489 | 8 谢谢
这个本来是编程题
前面好像做错了，算出来应该得132, 有个巧办法
【在 l******i 的大作中提到】
: 首先感谢楼主贡献，
: 如果可以的话，希望楼主最好能在帖子标题里加上问题的类别和关键词，
: 例如该帖名字可为：【Brain Teaser】出个题目
: 这样方便我们工作人员整理，谢谢啦。
: 我已经把标题改了。
| k*****y
发帖数: 744 | 9 假设就是1-12排成这样的矩阵：
a_{1,1}, ... a_{1,6}
a_{2,1}, ... a_{2,6}
那么满足条件当且仅当
a_{1,i} 关于i递增，且
a_{1,i} >= 2i，a_{1,6} <= 12。
记N(n, k) = #{ (x_1, ... x_n) | 递增, x_i >=2i, x_n =k }，
题目就是要算N(6, 12)。
有递推:
N(6,12)
= N(5,10) + N(5, 11)
= 2 N(4,8) + 2N(4,9) + N(4,10)
= ...
= 42 N(1,2) + 42 N(1,3) + 28 N(1,4) + 14 N(1,5) + 5 N(1,6) + N(1,7)
= 132
【在 w*******x 的大作中提到】
: 12 个人站队站两排，
: 要求第二排的比第一排高，然后两排都要求从左到右增高
: 共有多少中站法？ 本来是编程题，但可以直接写出解析解。
| l******i
发帖数: 1404 | 10 kinecty大牛的回答真好。
【在 k*****y 的大作中提到】
: 假设就是1-12排成这样的矩阵：
: a_{1,1}, ... a_{1,6}
: a_{2,1}, ... a_{2,6}
: 那么满足条件当且仅当
: a_{1,i} 关于i递增，且
: a_{1,i} >= 2i，a_{1,6} <= 12。
: 记N(n, k) = #{ (x_1, ... x_n) | 递增, x_i >=2i, x_n =k }，
: 题目就是要算N(6, 12)。
: 有递推:
: N(6,12)
| | | w*******x
发帖数: 489 | 11 如果2N个人的话，
答案是choose(2N, N) - choose(2N, N-1)
【在 w*******x 的大作中提到】
: 12 个人站队站两排，
: 要求第二排的比第一排高，然后两排都要求从左到右增高
: 共有多少中站法？ 本来是编程题，但可以直接写出解析解。
| s********r
发帖数: 529 | 12 这个是怎么推出来的呀？诚求大牛指点
【在 w*******x 的大作中提到】
: 如果2N个人的话，
: 答案是choose(2N, N) - choose(2N, N-1)
| s********r
发帖数: 529 | 13 这种方法是a_{1,i}高还是a_{2,i}高呀？看条件好像是第一排的人高
那么条件1.a_{1,i}关于i递增说的是从左到右依次增高
条件2. a_{1,i} >=2i是说第一排的人比第二排的人高吗？这个好像不是充分条件啊，比
如第一排的人是{4,5,6,8,10,12}，第二排的人是{7,9,1,2,3,11}
请kinecty指点！
【在 k*****y 的大作中提到】
: 假设就是1-12排成这样的矩阵：
: a_{1,1}, ... a_{1,6}
: a_{2,1}, ... a_{2,6}
: 那么满足条件当且仅当
: a_{1,i} 关于i递增，且
: a_{1,i} >= 2i，a_{1,6} <= 12。
: 记N(n, k) = #{ (x_1, ... x_n) | 递增, x_i >=2i, x_n =k }，
: 题目就是要算N(6, 12)。
: 有递推:
: N(6,12)
| k*****y
发帖数: 744 | 14 比较习惯从下往上看，所以第二排放在上面了。
a_{2,i}那一行也要从小到大排，才可能满足条件。
a_{1,i}前面只有i-1个比它小的，那么最多在1到(2i-1)之间占了i-1个，所以至少剩下
了i个比2i小的在第二行，于是a_{2,i} < 2i <= a_{1,i}。
同求woshialex答案的直观解释。
，比
【在 s********r 的大作中提到】
: 这种方法是a_{1,i}高还是a_{2,i}高呀？看条件好像是第一排的人高
: 那么条件1.a_{1,i}关于i递增说的是从左到右依次增高
: 条件2. a_{1,i} >=2i是说第一排的人比第二排的人高吗？这个好像不是充分条件啊，比
: 如第一排的人是{4,5,6,8,10,12}，第二排的人是{7,9,1,2,3,11}
: 请kinecty指点！
| P*******e
发帖数: 39399 | 15 catalan number
【在 k*****y 的大作中提到】
: 比较习惯从下往上看，所以第二排放在上面了。
: a_{2,i}那一行也要从小到大排，才可能满足条件。
: a_{1,i}前面只有i-1个比它小的，那么最多在1到(2i-1)之间占了i-1个，所以至少剩下
: 了i个比2i小的在第二行，于是a_{2,i} < 2i <= a_{1,i}。
: 同求woshialex答案的直观解释。
:
: ，比
| s********r
发帖数: 529 | 16 嗯，多谢回答
但是那个递推关系我还是有点疑惑，根据题意,a_{1,6}应该是12，而N(6,12)=N(5,10)+
N(5,11)怎么理解呀？能不能讲得清楚一些呢？多谢kinecty了
【在 k*****y 的大作中提到】
: 比较习惯从下往上看，所以第二排放在上面了。
: a_{2,i}那一行也要从小到大排，才可能满足条件。
: a_{1,i}前面只有i-1个比它小的，那么最多在1到(2i-1)之间占了i-1个，所以至少剩下
: 了i个比2i小的在第二行，于是a_{2,i} < 2i <= a_{1,i}。
: 同求woshialex答案的直观解释。
:
: ，比
| k*****y
发帖数: 744 | 17 a_{1,6}是12，N(5,10)相当于conditional on a_{1,5}=10，N(5,11)相当于
conditional on a_{1,5} = 11。
)+
【在 s********r 的大作中提到】
: 嗯，多谢回答
: 但是那个递推关系我还是有点疑惑，根据题意,a_{1,6}应该是12，而N(6,12)=N(5,10)+
: N(5,11)怎么理解呀？能不能讲得清楚一些呢？多谢kinecty了
| p*****k
发帖数: 318 | 18 spoiler: Catalan number (& Young tableaux for physics background)
----- ----- ----- ----- ----
scooped by PetTurtle :P | z****t
发帖数: 78 | 19 hehe, 看了wikipedia上用André's reflection method的证明，相当巧妙。
【在 p*****k 的大作中提到】
: spoiler: Catalan number (& Young tableaux for physics background)
: ----- ----- ----- ----- ----
: scooped by PetTurtle :P
| L******g
发帖数: 1371 | 20 绿皮书 page 117 , ticket line. | | | l*******1
发帖数: 113 | 21 OMG. Pcasnik is here again.
This forum is saved!!! | A**u
发帖数: 2458 | 22 very good puzzle.
thanks. | M*******i
发帖数: 82 | 23 我也这么想的
【在 L******g 的大作中提到】
: 绿皮书 page 117 , ticket line.
| s********r
发帖数: 529 | 24 这两道题目的共同点大牛能否指点一下，貌似有暗合之处，可惜功力不到无法洞悉啊
还请指教则个
【在 M*******i 的大作中提到】
: 我也这么想的
| k*****y
发帖数: 744 | 25 the number of standard 2xN Young tableaux
= the number of monotonic paths along the edges of a grid with N × N square
cells, which do not pass above the diagonal
因为就是把{1,2N}填到standard 2xN Young tableaux，第一行的数字就是沿着X走的时
刻，第二行的是沿着Y走的时刻，可以发现是1:1对应的。
然后计算用这个比较巧妙
http://en.wikipedia.org/wiki/Catalan_number#Second_proof | s********r
发帖数: 529 | 26 嗯，这道题目挺神的，和绿皮书上面的ticket line对应起来了
square
【在 k*****y 的大作中提到】
: the number of standard 2xN Young tableaux
: = the number of monotonic paths along the edges of a grid with N × N square
: cells, which do not pass above the diagonal
: 因为就是把{1,2N}填到standard 2xN Young tableaux，第一行的数字就是沿着X走的时
: 刻，第二行的是沿着Y走的时刻，可以发现是1:1对应的。
: 然后计算用这个比较巧妙
: http://en.wikipedia.org/wiki/Catalan_number#Second_proof
| w*******x
发帖数: 489 | 27 就是，所以我觉得还挺有意思的
对于还不太清楚的，可以这么想，12个人排好对了，从低到高，然后依次进入两个队伍
x,y 但要求x<=y
这样等价于给人编号+，或者-， 正好进入y队，-号进入x队。要求sum>=0.
一共有 choose(2N,N)中选择+号的方法。满足sum<0 的根据reflection principle得
choose(2N, N-1)
所以答案是 choose(2N,N)-choose(2N,N-1)
编程实现的话可以这么写：
#include
using namespace std;
int howmanyways(int x, int y, int N)
{
//x: first row. x>=y
if(x==N)return 1;
int sum=0;
if(y
{
y++;
sum += howmanyways(x,y,N);
y--;
}
x++;
sum += howmanyways(x,y,N);
return sum;
}
int main()
{
int N;
cout<<" N = ";
cin>>N;
cout<
}
【在 s********r 的大作中提到】
: 嗯，这道题目挺神的，和绿皮书上面的ticket line对应起来了
:
: square
|
|
