竞争规划算法Sock图概率问题

Question

先让我把问题贴上。

这个问题是基于一个（几乎）真实的故事。一个无名的孩子有一大堆干净的袜子。这一堆包含了m双有图片和图案的袜子和n只纯白的袜子。每双袜子由两只相同的袜子组成，每一双都是独一无二的--没有两双看起来是一样的。所有纯白的袜子都是一样的。每天，孩子们从袜子堆里随机挑选两只，穿上，然后去上学。但今天是照相日，孩子需要穿两只一模一样的袜子。于是孩子随机挑选了两只袜子，如果两只袜子都一样，孩子就穿上它们走出家门。如果两只袜子不完全相同，孩子就把袜子扔进洗衣篮里（它们现在很脏--不要问为什么），继续同样的过程，从剩余的干净袜子堆里随机挑选两只袜子。随着这一过程的继续，家长们开始担心：这个孩子今天还能上学吗？请帮助他们计算孩子在这个过程中找不到一双相同袜子的概率。这个问题是基于一个（几乎）真实的故事。

首先，限制是n<=500双袜子，m<=200只白袜子。我真的尽我所能去解决问题。我用了7的排列！然后数成对的袜子。在测试问题，有3个白色和2对袜子。我只能把所有成对的袜子数成7来解决这个问题！排列。这是O(n^n)而且效率很低。你能帮我解决这个问题吗？我顺便用了python，这是一个竞争性编程问题。

在最初的测试答案，有3个白袜子和2个配对袜子（共7只袜子）。答案是：0.457142857142857

Answer 1

高级策略：另一种看待问题的方法是，孩子拉出一双袜子，直到剩下零双或一双，然后检查匹配的一双。计算Pr（没有对是白匹配）和Pr（没有对是图案化匹配没有对是白匹配），然后使用概率101计算答案。

Pr（没有一对是白匹配）：保证白匹配当且仅当m+2≥2n。 如果m+2<2n，则没有一对是白匹配当且仅当恰好有m对正好有一只白袜子，或者m为奇数且恰好有m−1对正好有一只白袜子且剩的袜子是白的。

在此计算中，将图案袜子视为不可区分的。有(m+2n)选择m种方法画袜子。当m为偶数时，将绘制没有白袜子的袜子的方法数计算为(m/2+n)选择m种方法来选择有白袜子的袜子乘以2^m种方法来绘制那些袜子。当m为奇数时，我们得到(((m−1)/2+n)选择(m−1))×2^m-1种方式，其中剩袜为白色，加上((m−1)/2选择m)×2^m种方式，其中剩袜为图案。

Pr（no pair is a patterned match no pair is a white match）：我将处理m为偶数的情况，而将另一种情况留给您或其他人处理。我们有m/2+n对，其中m正好包含一只白色袜子，所以n−m/2对有两只图案袜子。匹配模式子集上的包含-排除给出了交替和

        i                    1            1                  1
 ∑  (−1)  (m choose i) (---------- × ---------- × … × ---------------)
i≥0                     2n + m − 1   2n + m - 3       2n + m - 2i + 1

其中，m choose i是选择i模式的方式数，乘积是所有i都匹配的概率（对于每个模式，我们按一定顺序显示第一只袜子，然后计算其配偶匹配的概率）。

奇数情况的工作原理类似，只是和前面一样，我们根据剩袜子是否是白色的情况拆分为几个情况。