Chương trình Python kỳ vọng tần suất lớn nhất của kết quả biểu thức

Có M biểu thức, kết quả mỗi biểu thức là số từ 1 đến N. Xét x = max(f(i)) với f(i) là tần suất xuất hiện của giá trị i. Tính kỳ vọng E[x].

Ví dụ: M=3, N=3 → E[x] = 2.2 (22/10).

Phương pháp tổ hợp - Container Principle

• Dùng hàm nCr với memoization tính tổ hợp.
• Với mỗi k = 2..M+1, tính số cách mà tần suất max < k (dùng nguyên lý bao hàm - loại trừ).
• Từ đó suy ra phân phối xác suất của max frequency, tính kỳ vọng.

Ví dụ mã nguồn

combination = {}

def nCr(n, k_in):
    k = min(k_in, n - k_in)
    if n < k or k < 0:
        return 0
    elif (n, k) in combination:
        return combination[(n, k)]
    elif k == 0 or n == k:
        return 1
    else:
        a = 1
        for cnt in range(k):
            a *= (n - cnt)
            a //= (cnt + 1)
            combination[(n, cnt + 1)] = a
        return a

def solve(M, N):
    arr = []
    for k in range(2, M + 2):
        a = 1
        s = 0
        for i in range(M // k + 2):
            if M < i * k:
                break
            s += a * nCr(N, i) * nCr(N - 1 + M - i * k, M - i * k)
            a *= -1
        arr.append(s)
    total = arr[-1]
    diff = [arr[0]] + [arr[cnt + 1] - arr[cnt] for cnt in range(M - 1)]
    output = sum(diff[cnt] * (cnt + 1) / total for cnt in range(M))
    return output

M = 3
N = 3
print(solve(M, N))  # 2.2

Đầu vào / Đầu ra

Input:  3, 3
Output: 2.2