如何使用计算方法（例如使用Python）找到以下期望概率？

Question

我们 class 有 64 名学生。我们进行了一轮随机团队分配，很快就会进行第二轮。在每一轮中，我们将学生随机分成 16 组，每组 4 人。

第 1 轮没有一对队友在第 2 轮再次成为队友的概率是多少？

Answer 1

如果 "computationally" 你的意思是 "with a simulation":

import random

def make_teams(teamsize, numteams):
    students = list(range(teamsize * numteams))  # Py2 & Py3 compatible
    random.shuffle(students)
    teammates = {}
    for i in range(0, len(students), teamsize):
        team = set(students[i:i+teamsize])
        for t in team: teammates[t] = team.difference([t])
    return teammates

ref_tms = make_teams(4, 16)
common_teammates = 0
for i in range(10000):
    new_tms = make_teams(4, 16)
    if any(ref_tms[t].intersection(new_tms[t]) for t in ref_tms):
        common_teammates += 1
print('Common teammates seen in {} cases out of 10000'.format(
      common_teammates)

当然，10000 个示例的样本很小，但它应该开始给您一个想法。您可以运行这几次，看看频率（作为概率的估计值）如何变化，并计算置信区间等。

Answer 2

让我们根据第 1 轮的球队给学生贴上标签：

0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 AAAA BBBB CCCC DDDD EEEE FFFF

无限制分配第2轮球队的方式是

64! / ((4! ** 16) * (4! ** 16)) == 864285371844932000669608560277139342915848604
 ^        ^            ^
 |        |        ways of rearranging each round-2 team
 |     indistinguishable arrangements for round-1 team members
raw number of permutations

分配第 2 轮球队的方式数量没有每个球队的重复是复杂的，因为我们如何分配第一支球队改变了第二支球队可用的组合（等等在）。但它应该仍然可以通过巧妙的数学运算和仔细的记忆来处理！

from functools import lru_cache

# lookup table for `choose(n, k)` for n up to 16 and k up to 4
ncr = {}
for n in range(17):
    nn   = n
    ntok = 1
    ktok = 1
    ncr[n, 0] = 1
    for k in range(1, min(n, 4) + 1):
        ntok *= nn
        nn -= 1
        ktok *= k
        ncr[n, k] = ntok // ktok

@lru_cache(maxsize=None)
def team_combos(zeros, ones, twos, threes, fours):
    """
    Calculate the number of unique second-round 4-person
      team combinations such that no team has members from
      the same first-round team.
    """
    if ones or twos or threes or fours:
        total_ways = 0
        # number of members to take from teams having one person remaining
        for b in range(min(ones, 4) + 1):
            zeros_ = zeros + b
            b_ways = ncr[ones, b]
            b_rem = 4 - b   # number of members yet to be chosen
            # number of members to take from teams having two persons remaining
            for c in range(min(twos, b_rem) + 1):
                ones_ = ones - b + c
                bc_ways = b_ways * ncr[twos, c]
                bc_rem = b_rem - c  # number of members yet to be chosen
                # number of members to take from teams having three persons remaining
                for d in range(min(threes, bc_rem) + 1):
                    e = bc_rem - d  # number of members yet to be chosen
                    # ... all of which _must_ now come from
                    #   teams having four persons remaining
                    if e <= fours:
                        bcde_ways = bc_ways * ncr[threes, d] * ncr[fours, e]
                        total_ways += bcde_ways * team_combos(zeros_, ones_, twos - c + d, threes - d + e, fours - e)
        return total_ways
    else:
        return 1

然后

>>> team_combos(0, 0, 0, 0, 16)   # start with 16 four-person teams
6892692735539278753058456514221737762215000

那么最后的概率就是正好

>>> 6892692735539278753058456514221737762215000 / 864285371844932000669608560277139342915848604
0.0079750195480295

如何使用计算方法（例如使用Python）找到以下期望概率？

How to find the following desired probability using computational method (e.g. using Python)?

python

statistics

probability

computation