如何使用计算方法(例如使用Python)找到下列期望的概率？

Question

我们班有64名学生。我们有一轮随机小组任务，很快就会有第二轮。在每一轮中，我们将学生随机分成16组，每组4人。

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

Answer 1

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

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

不受限制地分配第二轮团队的方法有：

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

分配第二轮团队的方法数量很复杂，因为我们分配第一组的方式改变了第二组可用的组合(以此类推)。但它仍然应该处理巧妙的数学和仔细的回忆录！

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

Answer 2

如果你所说的“计算”指的是“用模拟”：

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个例子的样本是很小的，但它应该给你一个想法。您可以运行这几次，看看频率(作为概率的估计)的变化，以及计算置信限等。