免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 择偶问题

男方在336名女生中选取8人作为心仪的候选人,同样女方在336名男生中选取8人作为心仪的候选人,
如果双方的候选人有交叉,则互选成功。请问互选成功的概率有多大?
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

有交叉读不 懂了 ?

TOP

某男选中了某女,同时该女也选中该男,这就是一个交叉,则称之为互选成功。
如果候选的8人中有多名候选人交叉,则以互选时的排名为准,排名靠前的优先。

TOP

男方在336名女生中选取8人作为心仪的候选人的概率是8/336=1/42

同样女方在336名男生中选取8人作为心仪的候选人,其概率也是8/336=1/42

那么这两个选择匹配的概率是1/42X1/42=0.00056689



如果双方的候选人有交叉,则互选成功。请问互选成功的概率有多大?

由于可以挑选8次,在8次中有一次匹配成功即可,则概率还要乘以8,得0.004535


不知道对不对,请大侠指正。

TOP

回复 4# mproustaervi

这个算法应该不对。
不妨将情况简化到最简单的情形:双方各二人,每人从对方二选一。
按你的算法:1/2X1/2,最后再乘以2,结果就是0.5。
但通过枚举发现,这种最简情形,要使得一个互选都没有,只有两种可能,而总共有16种可能,所以有互选的概率应该是 14/16,结论不符。

TOP

先尝试解决每人只选一人的简单情形,即:

双方各 `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

回复 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

返回列表 回复 发帖