Cho k và n. Xét hoán vị ngẫu nhiên p₁...pₙ của 1..n. Định nghĩa biến chỉ thị Xᵢ = 1 nếu pᵢ₋₁ < pᵢ > pᵢ₊₁ (đỉnh) hoặc pᵢ₋₁ > pᵢ < pᵢ₊₁ (đáy), ngược lại 0. Tính kỳ vọng của F = (X₂+...+Xₙ₋₁)ᵏ.
Kết quả cho k=1, n=1000 là 1996/3.
Cách giải
Sử dụng công thức đóng (closed-form) cho k = 1..5 được tính toán trước. Hàm exp_factor(n,k) trả về tử/mẫu của kỳ vọng. Rút gọn phân số bằng GCD.
Ví dụ mã nguồn
from math import gcd
def exp_factor(n, k):
if k == 1:
return (2*(n-2), 3)
elif k == 2:
return (40*n**2 - 144*n + 131, 90)
elif k == 3:
return (280*n**3 - 1344*n**2 + 2063*n - 1038, 945)
elif k == 4:
return (2800*n**4 - 15680*n**3 + 28844*n**2 - 19288*n + 4263, 14175)
elif k == 5:
return (12320*n**5 - 73920*n**4 + 130328*n**3 - 29568*n**2 - 64150*n - 5124, 93555)
return (1, 1)
def solve(k, n):
num, den = exp_factor(n, k)
g = gcd(num, den)
return f'{num//g}/{den//g}'
k = 1
n = 1000
print(solve(k, n)) # 1996/3
Đầu vào / Đầu ra
Input: 1, 1000
Output: 1996/3