Mathematics

High-school summary

Prepa / Concours

CPGE Paradise - Some files saved in bucket
Combinatoire / Arrangements

// [fr] permutation sans repetition : https://fr.m.wikiversity.org/wiki/Combinatoire/Permutations_sans_r%C3%A9p%C3%A9tition
fn f(n: i32) -> i32 {
    match n {
        0 | 1 => 1,
        _ => n * f(n-1)
    }
}

// [en] k-permutations of n (also called arrangements) without repetition https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n
// [fr] arrangement sans repetitions : https://fr.m.wikiversity.org/wiki/Combinatoire/Arrangements_sans_r%C3%A9p%C3%A9tition
fn k_permut_of_n(n: i32, k: i32) -> i32 {
    if k > n {
        return 0
    }

    f(n) / f(n-k)
}

// [en] permutations wt repetition (order) : https://en.wikipedia.org/wiki/Permutation#Permutations_with_repetition
// [fr] arrangement av repetition (ordre) : https://fr.m.wikiversity.org/wiki/Combinatoire/Arrangements_avec_r%C3%A9p%C3%A9tition
fn n_pow_k(n: i32, k: u32) -> i32 {
    n.pow(k)
}


// also called binomial coefficient
// [en] combination : https://en.wikipedia.org/wiki/Combination
// [fr] combinaison sans repetition : https://fr.m.wikiversity.org/wiki/Combinatoire/Combinaisons_sans_r%C3%A9p%C3%A9tition
fn combination(n: i32, k: i32) -> i32 {
    if k > n {
        return 0
    }

    f(n) / (f(k) * f(n-k))
}

// [en] permutation of multisets : https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets
// [fr] permutations avec répétition : https://fr.m.wikiversity.org/wiki/Combinatoire/Permutations_avec_r%C3%A9p%C3%A9tition
fn multiset_permut(nk: Vec<i32>) -> i32 {
    let mut mul = 1;

    for v in nk.iter() {
        mul *= f(*v);
    }

    f(nk.iter().sum::<i32>()) / mul
}


// [en] combination with repetition : https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition
// [fr] combinaison avec repetition : https://fr.m.wikiversity.org/wiki/Combinatoire/Combinaisons_avec_r%C3%A9p%C3%A9tition
fn combination_repetition(n: i32, k: i32) -> i32 {
    combination(n+k-1, k)
}