Combinaisons

let rec combinaisons k l =
  if k = 0 then [[]]
  else
    match l with
    | [] -> []
    | x :: reste ->
        List.map (fun c -> x :: c) (combinaisons (k - 1) reste)  (* avec x *)
        @ combinaisons k reste                                    (* sans x *)

Même dichotomie de choix que parties, mais en contraignant la taille : prendre x (il reste k-1 à choisir) ou non (toujours k à choisir). Les cas de base : k = 0 (une seule combinaison, vide) et liste vide avec k > 0 (aucune). On obtient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ combinaisons.