繁體
|
簡體
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版)
»
初等数学讨论
» 择偶问题
返回列表
发帖
mproustaervi
发短消息
加为好友
mproustaervi
当前离线
UID
2867
帖子
3
主题
1
精华
0
积分
15
威望
0
阅读权限
10
在线时间
0 小时
注册时间
2018-11-3
最后登录
2018-11-6
1
#
跳转到
»
倒序看帖
打印
字体大小:
t
T
发表于 2018-11-3 15:43
|
只看该作者
[组合]
择偶问题
男方在336名女生中选取8人作为心仪的候选人,同样女方在336名男生中选取8人作为心仪的候选人,
如果双方的候选人有交叉,则互选成功。请问互选成功的概率有多大?
收藏
分享
分享到:
QQ空间
腾讯微博
腾讯朋友
realnumber
发短消息
加为好友
realnumber
当前离线
UID
37
帖子
1723
主题
405
精华
0
积分
10201
威望
2
阅读权限
90
性别
男
在线时间
2772 小时
注册时间
2013-6-21
最后登录
2022-4-25
2
#
发表于 2018-11-4 08:51
|
只看该作者
有交叉读不 懂了 ?
TOP
mproustaervi
发短消息
加为好友
mproustaervi
当前离线
UID
2867
帖子
3
主题
1
精华
0
积分
15
威望
0
阅读权限
10
在线时间
0 小时
注册时间
2018-11-3
最后登录
2018-11-6
3
#
发表于 2018-11-4 16:33
|
只看该作者
某男选中了某女,同时该女也选中该男,这就是一个交叉,则称之为互选成功。
如果候选的8人中有多名候选人交叉,则以互选时的排名为准,排名靠前的优先。
TOP
mproustaervi
发短消息
加为好友
mproustaervi
当前离线
UID
2867
帖子
3
主题
1
精华
0
积分
15
威望
0
阅读权限
10
在线时间
0 小时
注册时间
2018-11-3
最后登录
2018-11-6
4
#
发表于 2018-11-6 22:56
|
只看该作者
男方在336名女生中选取8人作为心仪的候选人的概率是8/336=1/42
同样女方在336名男生中选取8人作为心仪的候选人,其概率也是8/336=1/42
那么这两个选择匹配的概率是1/42X1/42=0.00056689
如果双方的候选人有交叉,则互选成功。请问互选成功的概率有多大?
由于可以挑选8次,在8次中有一次匹配成功即可,则概率还要乘以8,得0.004535
不知道对不对,请大侠指正。
TOP
kuing
发短消息
加为好友
kuing
当前离线
UID
1
帖子
8832
主题
619
精华
0
积分
66354
威望
113
阅读权限
200
性别
男
来自
广东广州
在线时间
21788 小时
注册时间
2013-6-13
最后登录
2024-3-9
5
#
发表于 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
6
#
发表于 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
7
#
发表于 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 分享给朋友]