海蓝云分享 http://blog.sciencenet.cn/u/hailanyun0415 夕阳技术的守墓人-邮箱:jkyhly@hnfnu.edu.cn ;hailanyun0415@gmail.com

博文

一道排列组合题

已有 3328 次阅读 2015-7-26 16:50 |个人分类:其他|系统分类:科普集锦| 排列, 组合, 二项式

今天在群里看见一道题,
共5个按钮,对应5种动物。每个按钮按一下出现一种动物。再按一下出现第二只这个动物。按钮每个只能按2次,5个按钮随机按。求最后能产生多少个不同的画面。

这是一个变态的甲方提供给苦逼的课件制作者的,要求乙方把所有的画面都做出来,乙方估计是美工,数学应该也不怎么样,做了40几个以后发现不对劲了,效率怎么这么低?于是就进群求教。

我算了两次,推出的第一个公式是::

$\prod_{i=1}^{n-1}{((2i+1)+B[2i+1,2])}$

这个公式看不懂没事,后面有更简单的。看上去有点复杂,但其实很好理解,我们用数字来表示动物好了。1个按钮只会出现一个画面,但按按钮不一定照先1后2的顺序所以有3个空位留给第2个按钮,就像这样子:

( )1( )1( )

括号内可以是个2个2。那么就有$3+B[3,2]=6$种情况,我们用abcd表示,于是第3个按钮就有5个空位了,就像这样子:

( )a( )b( )c( )d( )

括号内可以是个3个3。那么就有$5+B[5,2]=15$种情况。abcd有6种情况,所以,共计 15*6=90 种情况。

依次类推,出现的情况依次是:

2个按钮有6种情况,是4!的1/4。
3个按钮有15*6=90种情况,是6!的1/8。
4个按钮有28*15*6=2520种情况,是8!的1/16。

5个按钮共计45*28*15*6=113400种情况,恰好是10!的1/32。


引入阶乘是由于担心重复计算导致可能性超出总的可能性,结果却发现了这一巧合,这就说明n个按钮,有 (2n)!/2n 种情况


写博文之前还没理解这个公式,写的过程才发现有种更简单的解题思路:n个按钮,总共按出2n个动物,有(2n)!种情况,但有2个动物是重复的,一共有n组,所以要除以2n

举个简单的例子,2个按钮,先按出的是黑色,后按出的是红色,那么就有可能按出1122这种情况。但4!里还包括了:1122,1122,1122。所以要除以22

这种思路就算一开始没想到,做过一遍以后也就有了。这种题做的过程中有一种探究未知的兴奋,但做完了以后,又觉得挺一般的。其实解题过程就如同做爱,射了以后,就会觉得很空虚。乙方倒也不在乎具体的结果,她的意思是超过100个就不想做了,何况是11万个。


---------------

7.28修改:


1.Binomial是二项式系数,以前高中学的时候用的是C,现在貌似用B了。

$B[2i+1,2]=\frac{(2i+1)*2i}{2}$


2.利用上式证明下面的式子并不难。

$\prod_{i=1}^{n-1}{((2i+1)+B[2i+1,2])}=\frac{(2n)!}{2^n}$


3. $\frac{(2n)!}{2^n}$ 把偶数项的2约掉,会变成 $n!\prod_{i=1}^{n-1}{(2i+1)}$

这个公式也能对应一个解题思路:

举例来说,假设5个按钮,先按出的是黑色,后按出的是红色

先按出的黑色有$n!$种可能。其中一种可能是:

1( )2( )3( )4( )5( )

此时5只有1个空位可呆

1 2 3 4 5(   )

放入5后,4有3个空位可呆

1 2 3 4( )5( )5( )

不论4放哪里,3都有5个空位可呆,

1 2 3( )4( )4( )5(     )5(     )

1 2 3( )4(     )5( )4( )5(     )

1 2 3( )4(     )5(     )5( )4( )

以此类推,2有7个空位,1有9个空位

$n=5$时,9*7*5*3对应的就是$\prod_{i=1}^{n-1}{(2i+1)}$




https://wap.sciencenet.cn/blog-729147-908426.html

上一篇:从数学的角度判断维稳
下一篇:bad apple
收藏 IP: 42.48.86.*| 热度|

3 尤明庆 yangb919 dulizhi95

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 20:29

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部