[组合] 概率问题，方格黑白染色

急用，请教各位，谢谢！
QQ截图20170529012333.jpg

分享到: QQ空间 腾讯微博 腾讯朋友

lrh2006

2^#

发表于 2017-5-29 08:39 | 只看该作者

回复 1# lrh2006

第2问求过程，哪位大神能解释一下，多谢！

TOP

isee

3^#

发表于 2017-5-29 16:50 | 只看该作者

回复 lrh2006

第2问求过程，哪位大神能解释一下，多谢！
lrh2006 发表于 2017-5-29 08:39

请看科普 2016年理科课标全国卷III 第12题（规范01数列）

TOP

isee

4^#

发表于 2017-5-29 16:57 | 只看该作者

本帖最后由 isee 于 2017-5-29 16:58 编辑

（学校）又到了排列组合内容了，我也想准备下排列组合中的（趣味）“典型”问题，好像除了这个 Catalan数，还有欧拉错排问题，还有什么类型？不知到了。。。无知了。。

TOP

kuing

5^#

发表于 2017-5-29 17:29 | 只看该作者

可以利用 http://kuing.orzweb.net/viewthread.php?tid=4099 里的方法。

本题与那帖中的题的区别在于，帖中的题目限定了 0 和 1 的个数相同，而这里却没这个限制，不过方法显然还是能用。

根据那帖的方法易知，在方形网格中，若 $m$, $n\inN^+$, $m\geqslant n$，则由 $(0,0)$ 到 $(m,n)$ 且恒满足 $y\leqslant x$ 的最短路径总数为 $C_{m+n}^n-C_{m+n}^{n-1}$。

回到本题的情形中，若染色的格子数为 $2n$，则转化后等价于由 $(0,0)$ 到直线 $x+y=2n$ 上的格点且恒满足 $0\leqslant y\leqslant x$ 的最短路径总数。

根据上述结果，当终点为 $(n+k,n-k)$（$0\leqslant k\leqslant n-1$）时的数目为 $C_{2n}^{n-k}-C_{2n}^{n-k-1}$，而终点为 $(2n,0)$ 时只有 1 条，于是求和后，总数就是 $C_{2n}^n$。

同理，若格子数为 $2n-1$，则总数为 $C_{2n-1}^{n-1}$，将两种情况合起来，最终结论就是：若格式数为 $n$，则总数为 $C_n^{\lfloor n/2\rfloor}$。

所以本题第二问的结果就是 $C_6^3/2^6=5/16$。

$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

kuing

6^#

发表于 2017-5-29 18:10 | 只看该作者

回复 5# kuing

话说，结果这么简单，总觉得会有更直接的解释。如果真是这样的话，那也就可以反过来解那帖的Catalan数了。

=======
补充说明一下具体做法——
设染 $2n$ 个格子时满足条件的方法数为 $a_n$，在这当中，设满足黑白数目相等的方法数为 $c_n$，
那么当染 $2(n+1)$ 个格子时，如果前 $2n$ 格黑白数目不相等，则后两格可任意染，如果相等，则后两格只能染“黑白”或“黑黑”，所以有 $a_{n+1}=4(a_n-c_n)+2c_n=4a_n-2c_n$，
故此，如果这题有特别简单的解法，那就是 $a_n$ 易得，从而反过来推出 $c_n$，即Catalan数。

TOP

isee