MediumProbabilitypr-166

Probability of Exactly k Fixed Points

Problem

Probability that a uniformly random permutation of n items has exactly k fixed points:

P = C(n, k) * D(n - k) / n!

where D(m) is the number of derangements of m items. Return 0.0 for invalid k.

Hint

Choose the fixed points, then derange the rest.

case 1

in: [3,0]

expected: 0.3333333333333333

case 2

in: [3,1]

expected: 0.5

case 3

in: [3,3]

expected: 0.16666666666666666

case 4

in: [4,0]

expected: 0.375

case 5

in: [2,3]

expected: 0

Starter codePython

import math


def probability_k_fixed_points(n, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor