繁體
|
簡體
Sclub交友聊天~加入聊天室當版主
(檢舉)
分享
新浪微博
QQ空间
人人网
腾讯微博
Facebook
Google+
Plurk
Twitter
Line
快速注册
登录
论坛
搜索
帮助
原始风格
brown
purple
green
red
orange
gray
pink
violet
blue
greyish-green
jeans
greenwall
私人消息 (0)
公共消息 (0)
系统消息 (0)
好友消息 (0)
帖子消息 (0)
应用通知 (0)
应用邀请 (0)
悠闲数学娱乐论坛(第2版)
»
初等数学讨论
» 择偶问题
返回列表
发帖
kuing
发短消息
加为好友
kuing
当前离线
UID
1
帖子
8832
主题
619
精华
0
积分
66354
威望
113
阅读权限
200
性别
男
来自
广东广州
在线时间
21788 小时
注册时间
2013-6-13
最后登录
2024-3-9
1
#
跳转到
»
发表于 2018-11-8 14:40
|
显示全部帖子
回复
4#
mproustaervi
这个算法应该不对。
不妨将情况简化到最简单的情形:双方各二人,每人从对方二选一。
按你的算法:1/2X1/2,最后再乘以2,结果就是0.5。
但通过枚举发现,这种最简情形,要使得一个互选都没有,只有两种可能,而总共有16种可能,所以有互选的概率应该是 14/16,结论不符。
TOP
kuing
发短消息
加为好友
kuing
当前离线
UID
1
帖子
8832
主题
619
精华
0
积分
66354
威望
113
阅读权限
200
性别
男
来自
广东广州
在线时间
21788 小时
注册时间
2013-6-13
最后登录
2024-3-9
2
#
发表于 2018-11-9 02:54
|
显示全部帖子
先尝试解决每人只选一人的简单情形,即:
双方各 `n` 人,每人从对方 `n` 人中随机选 `1` 人,求存在互选的概率。
将双方的人分别记为 `\{a_1,a_2,\ldots ,a_n\}` 及 `\{b_1,b_2,\ldots ,b_n\}`,将事件“`a_i` 与 `b_j` 互选”记作 `A_{ij}`,记集合 `U=\{A_{ij}\mid 1\leqslant i,j\leqslant n\}`,设存在互选的方法数为 `S`,根据容斥原理,有
\[S=\sum_{A_{ij}\in U} \abs{A_{ij}}
-\sum_{\{A_{ij},A_{kl}\}\subseteq U} \abs{A_{ij}\cap A_{kl}}
+\sum_{\{A_{ij},A_{kl},A_{pq}\}\subseteq U} \abs{A_{ij}\cap A_{kl}\cap A_{pq}}-\cdots.\]
先看第一个和式,对于 `A_{11}`,即 `a_1` 与 `b_1` 互选,其余的人随便选,所以 $\abs{A_{11}}=n^{2n-2}$,其他的显然是一样的道理,而 `A_{ij}` 共 `n^2` 个,因此
\[\sum_{A_{ij}\in U} \abs{A_{ij}}=n^2\cdot n^{2n-2}=n^{2n};\]
再看第二个和式,由于现在只是选一人,因此如果 `i=k` 或 `j=l` 则 $A_{ij}\cap A_{kl}=\kongji$,而对于 `i\ne k` 且 `j\ne l` 的,比如 `A_{11}\cap A_{22}`,即 `a_1` 与 `b_1` 互选且 `a_2` 与 `b_2` 互选,其余的人随便选,所以 $\abs{A_{11}\cap A_{22}}=n^{2n-4}$,其他的也是一样的道理,而满足 `i\ne k` 或 `j\ne l` 的 `\{A_{ij},A_{kl}\}` 共 `(C_n^2)^2\cdot2!` 个,因此
\[\sum_{\{A_{ij},A_{kl}\}\subseteq U} \abs{A_{ij}\cap A_{kl}}
=(C_n^2)^2\cdot2!\cdot n^{2n-4};\]
第三个和式道理也是一样,单个 `n^{2n-6}`,共 `(C_n^3)^2\cdot3!` 个,所以
\[\sum_{\{A_{ij},A_{kl},A_{pq}\}\subseteq U} \abs{A_{ij}\cap A_{kl}\cap A_{pq}}
=(C_n^3)^2\cdot3!\cdot n^{2n-6};\]
规律已经很明显,用和式写起来即
\[S=n^{2n}-\sum_{k=2}^{n}(-1)^k(C_n^k)^2\cdot k!\cdot n^{2n-2k},\]
而总的方法数显然为 `n^{2n}`,所以概率为
\[P=1-\sum_{k=2}^{n}(-1)^k(C_n^k)^2\frac{k!}{n^{2k}}.\]
这只是只选一人,已经不容易,选多人就更复杂了,因为能选多人则像 `A_{11}\cap A_{12}` 这种情况也存在,而且与 `A_{11}\cap A_{22}` 的方法数不同,公式就算勉强列出来恐怕也相当复杂,或许应该考虑换个方向,时间关系还是明天再研究……
$\href{https://kuingggg.github.io/}{\text{About Me}}$
TOP
kuing
发短消息
加为好友
kuing
当前离线
UID
1
帖子
8832
主题
619
精华
0
积分
66354
威望
113
阅读权限
200
性别
男
来自
广东广州
在线时间
21788 小时
注册时间
2013-6-13
最后登录
2024-3-9
3
#
发表于 2018-11-9 03:09
|
显示全部帖子
回复
6#
kuing
对于 5# 所讲的二选一,即代入 `n=2` 得 `P=1-2!/2^4=14/16=7/8`,结果相符;
如果三选一,即代入 `n=3` 得 `P=573/3^6=191/243`,哪位高手编个程序来验证一下?事关我总感觉这概率有点大啊,按照公式,十选一概率也有 0.67 左右……
TOP
返回列表
回复
发帖
[收藏此主题]
[关注此主题的新回复]
[通过 QQ、MSN 分享给朋友]