a*******1
发帖数: 1554 | 1 红球黑球各n个，排成一列，要求对任意的m<=2n，前m个球中红球的数目不少于黑球的
数目。问有多少种排列的方法？谢谢。 | p*****k
发帖数: 318 | | a*******1
发帖数: 1554 | 3 谢谢！但它只给了公式，请问怎么推导呢？现在大脑真的退化了实在想不到...
【在 p*****k 的大作中提到】
: Catalan number, see e.g.,
: http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics
| u****4
发帖数: 5 | 4 symmetric random walk. X(red)=1, X(black)=-1. X_1 must be 1, X_{2n} must be
-1. then use reflection...
【在 a*******1 的大作中提到】
: 红球黑球各n个，排成一列，要求对任意的m<=2n，前m个球中红球的数目不少于黑球的
: 数目。问有多少种排列的方法？谢谢。
| d*********n
发帖数: 27 | 5 I have a naive solution, but I am not sure if this is what's asked for.
If there are "i" black balls in the first "m", then there are
{m, i} * {2n-m, n-i}
ways to arrange all the balls. ( note: {m,i}=m!/(i!(m-i)!) )
Since there are at most [m/2] black balls in the first m, the total number
is
sum_{i=0}^[m/2] {m, i} * {2n-m, n-i} | u****4
发帖数: 5 | 6 i think the lz means for all m, not a given m...so you probabily answered to
a different question..
【在 d*********n 的大作中提到】
: I have a naive solution, but I am not sure if this is what's asked for.
: If there are "i" black balls in the first "m", then there are
: {m, i} * {2n-m, n-i}
: ways to arrange all the balls. ( note: {m,i}=m!/(i!(m-i)!) )
: Since there are at most [m/2] black balls in the first m, the total number
: is
: sum_{i=0}^[m/2] {m, i} * {2n-m, n-i}
| d*********n
发帖数: 27 | 7
to
You are right. My answer only works for any given "m" .
If all values of "m" are wanted, one can simply add all the cases up. There
is a simpler result for this case:
({2N,N} - K ) / 2 + K
where K is the total number of cases where "m" is even and half of the "m"
balls are red. This result is true because if all "m" are considered, one
only needs to notice that red and black balls have equal chance to dominate
the first "m" balls. The only complexity is that cases involving "K" should
be cou
【在 u****4 的大作中提到】
: i think the lz means for all m, not a given m...so you probabily answered to
: a different question..
| u****4
发帖数: 5 | 8 are you sure there are no overlapping cases? hehe..
There
dominate
should
【在 d*********n 的大作中提到】
:
: to
: You are right. My answer only works for any given "m" .
: If all values of "m" are wanted, one can simply add all the cases up. There
: is a simpler result for this case:
: ({2N,N} - K ) / 2 + K
: where K is the total number of cases where "m" is even and half of the "m"
: balls are red. This result is true because if all "m" are considered, one
: only needs to notice that red and black balls have equal chance to dominate
: the first "m" balls. The only complexity is that cases involving "K" should
|
| P********l
发帖数: 452 | 9 把红球看成左括号，黑球看成右括号。这个问题就变成了括号配对的问题。
f(n)=sum( f(i) * f(n-i-1) ) i=0 .. n-1
http://en.wikipedia.org/wiki/Binary_tree
wiki说这玩意就是 catlan number!
【在 a*******1 的大作中提到】
: 红球黑球各n个，排成一列，要求对任意的m<=2n，前m个球中红球的数目不少于黑球的
: 数目。问有多少种排列的方法？谢谢。
|
|
