这是17-18赛季欧冠十六强抽签中，任意两支球队相遇概率的计算结果，我想知道这是如何计算出来的。

　　下面用通俗语言描述一下问题，就不涉及具体球队了，也顺便介绍下欧足联的抽签机制。

　　如上图，有16支球队，来自8个小组，A1表示该球队来自A组，属于国家1，大写字母表示是小组第一，同一国家的球队不会出现在同一个小组。。十六强抽签就是要使这16支球队两两相遇，相遇的两支球队要满足：一只是小组第一，一只是小组第二；来自同一个小组的球队不能相遇；来自同一国家球队不能相遇。

　　抽签的流程是：有两个桶，甲桶和乙桶，甲桶中放着8个小组第二。每一轮里，先从甲桶中随机抽出一个小组第二，不放回，根据抽出的这个小组第二，工作人员确定哪几只小组第一是“可行”的，并把它们放进乙桶，然后从乙桶中随机抽出一只，这一轮的配对就结束了，清空乙桶，再进行下一轮，进行完8轮之后，抽签就结束了。

　　但对“可行”的判定还有点小复杂，比如下图，黄色标记表示已经被抽走了。假设此时h3被抽出了，那么在剩下的四个小组第一中，H1肯定不可行，因为是同小组的，C3肯定也不行，因为是同国家的。但其实D4也是不可行的，因为一旦h3D4配对了，那么c1就没有任何可行解了！所以当h3从甲桶中被抽出时，只有A1这一个是可以放进乙桶，与之配对的。我们看那个欧足联抽签的直播，有位工作人员带着耳机负责把小球放进乙桶，应该就是后面有个程序在运行着。

　　这里给出一位球迷做的模拟抽签系统http://inker.github.io/cl-draw/

　　#######################################分割线

　　我想问的是如何求出某两支球队相遇的概率。我也抛砖引玉地说一下我目前的思路吧，我觉着首先是要证明“所有合法的抽签结果，是等概率出现的”，然后就变成了求“在某两支球队相遇的情况下，共有多少种合法的抽签结果”，只是这两个子问题，我都不会做。。。。

　　1.“所有合法的抽签结果，是等概率出现的”，我只是这样猜测，也可能不是等概率的，请不要被我误导。。我只是觉着如果抽签结果不是等概率出现的，那这个抽签的机制就不太好了。

　　2.“在某两支球队相遇的情况下，共有多少种合法的抽签结果”，我只知道如果不考虑同国家回避时该怎么求，可又拓展不到同国家要回避的情况里。。还有就是，靠枚举的话，在O(n!)的时复里肯定是能数出来，当然还是希望有一种不这么暴力的解法啦～

　　16支球队的分组，共有分组可能性总数为A，去掉不符合规则的分组后剩余总数为B，这其中特定两支球队的交手的子集为Cn，则概率即Cn/B。

　　我来自问自答一下吧，感谢前舍友的提点

　　首先说一下结论，我后来计算出的概率，与问题的中图片里的并不一样。不知道是哪边出了问题。我的计算结果是

　　下面说下计算过程。核心就是，这是一个二部图完全匹配问题。二分图的最大匹配、完美匹配和匈牙利算法

　　讲二部图的文章里，经常会举相亲这个例子：一个相亲活动，有8个女嘉宾8个男嘉宾，他们各自有若干个心仪的对象，这个相亲活动要保证这16个嘉宾都找到对象，问总共有多少种可能的配对方案。其实这个跟欧冠抽签是一会事，不同小组不同国家就是心仪的对象。问题1.“在某两支球队相遇的情况下，共有多少种合法的抽签结果”

　　那么这就相当于是求，一个二部图所有的完全匹配的个数。首先用邻接矩阵（记为矩阵A）来表示这个二部图：

　　1-表示这两队可以匹配，0-表示不可以匹配，上面的邻接矩阵基于“同小组回避”，“同国家回避”这两个匹配的原则。

　　红色数字表示了现实中的抽签结果，这当然是一种合法的抽签结果。可以发现，一个抽签结果合法的充要条件就是：从邻接矩阵中，选出8个"1"（对应8对匹配），且邻接矩阵矩阵的每一行上有且仅有1个"1"，邻接矩阵矩阵的每一列上有且仅有1个"1"。

　　那么，求合法的抽签结果的数目，就是求从邻接矩阵中选取满足条件的8个"1"有多少种可能性。那么这就要靠枚举了，比较直接的办法就是生成1~8的全排列，对一种排列，判断对应元素是不是1。比如对58637124这个排列，就是去验证A[1][5],A[2][8],A[3][6],A[4][3],A[5][7],A[6][1],A[7][2],A[8][4]这8个数是否都是1（这8个元素就是图上的红色数字）。

　　用数学公式表示一下，就是

　　Sn是1~n的全排列，这个问题里n就等于8。

　　特别的，上面公式的右边也是早有定义的，叫做矩阵A的积和式（permanent），之前听都没听说过。。积和式的定义比行列式还要简洁，行列式里求和的时候还要去算逆序数。但积和式的性质就没有行列式那么好了，以至于一个矩阵的积和式是无法在多项式时间内计算的。

　　说了这么多，其实二部图的研究里早有结论了：二部图的完全匹配个数等于这个二部图的邻接矩阵的积和式。

　　需要说明的是，尽管引入了二部图、积和式乱七八糟这么多，但我觉着，其实在求解“在某两支球队相遇的情况下，共有多少种合法的抽签结果”这个问题上，本质上还是在枚举，时间复杂度还是O(n!)，只不过是描述起来更简洁、更抽象罢了。好在，这至少说明抽签这个问题不存在多项式复杂度的解法了，因为在多项式时间里计算矩阵积和式是不可能的。。问题2.“所有合法的抽签结果，是否是等概率出现的”

　　只有证明了“所有合法的抽签结果，是等概率出现的”，才能得到

　　但我一直都想出来应该如何证明这个命题。。。

　　不过我觉着这个命题应该是正确的，因为我试验了好几种待抽签的邻接矩阵，仿真的结果都显示所有合法的抽签结果，是等概率出现的。

　　仿真的思路大概是：求出每种抽签结果出现的概率，一共有8的阶乘40320种抽签结果，其中有一些是非法的，那么他们出现的概率是0，而所有出现概率不是0的抽签结果，概率应该要是相同的。而对于某一种给定的抽签结果，计算其在“每一种小组第二抽出顺序”下，出现的概率，然后把他们加起来，就得到了这种抽签结果的出现概率。这个仿真的时复就要n的阶乘的平方了，半天才能仿一次，我随便试了几个，结论都是成立的。

　　8分之一决赛抽签规则：小组第一球队匹配一支小组第二球队同联赛球队回避，例如小组第一尤文图斯不会抽到小组第二的国际米兰同小组球队回避，例如小组第一曼联不会抽到同一个小组的比利亚雷亚尔

　　所有的可能抽签形式可以用下面这张图表示，绿色方块代表能够抽到的对手，红色方块代表依照规则回避的对手，纵轴是小组第一，横轴是小组第二

　　那么，概率要怎么计算呢？

　　一个思路是把上面这张图抽象成一个8*8的方阵，所有元素都是0或1

　　1代表抽签结果，

　　0自然就是没有抽中

　　以左上角作为原点，

　　红色方块例如（1，1），（1，8）元素一定是0

　　即曼城一定不会抽到切尔西和巴黎圣日耳曼

　　这个方阵每一行每一列都有且仅有1个1

　　这个方阵满秩

　　一旦这一行（列）有一个元素为1，后面这一行（列）的所有元素都是0

　　这样就可以得到抽签的所有情形啦！

　　统计每个元素出现1的次数，除以所有的情形，就可以获得抽签的概率

　　

　　与媒体结果对比一下，完全相同

　　从这个结果看，我车32.3%的概率要抽皇马，21%的概率抽贾府，21.38%的概率抽拜仁。哭了呀5555555555