Combinatorics in Python

MediumPython

Problem

Citadel Securities analytics may need to count possible order arrangements and selections without enumerating them. Implement a function that returns both the number of ordered arrangements and unordered selections of r items chosen from n distinct items.

Formal Specification

Implement count_permutations_and_combinations(n, r):

Return [P(n, r), C(n, r)].
P(n, r) = n! / (n-r)!.
C(n, r) = n! / (r!(n-r)!).
Use exact integer arithmetic. Do not generate the arrangements or selections.
The inputs satisfy 0 <= r <= n, so the function must also handle r = 0.

Example 1: n = 5, r = 2 returns [20, 10]. There are 5 choices for the first ordered position and 4 for the second, while unordered selections divide those 20 arrangements by 2!.

Example 2: n = 6, r = 0 returns [1, 1]. There is exactly one empty arrangement and one empty selection.

Constraints

0 <= r <= n
0 <= n <= 1000
Results may exceed 64-bit integer range
Inputs are integers

Function Signature

def count_permutations_and_combinations(n, r):

Formal Specification

Implement count_permutations_and_combinations(n, r):

Return [P(n, r), C(n, r)].
P(n, r) = n! / (n-r)!.
C(n, r) = n! / (r!(n-r)!).
Use exact integer arithmetic. Do not generate the arrangements or selections.
The inputs satisfy 0 <= r <= n, so the function must also handle r = 0.

Example 1: n = 5, r = 2 returns [20, 10]. There are 5 choices for the first ordered position and 4 for the second, while unordered selections divide those 20 arrangements by 2!.

Example 2: n = 6, r = 0 returns [1, 1]. There is exactly one empty arrangement and one empty selection.