Metode de numărare

Combinări

Fie A o mulțime finită cu n elemente \((n\in \mathbb{N}^{*})\) și k un număr natural, \(k\leq n.\)
Numim combinări de n elemente luate câte k totalitatea submulțimilor de k elemente ale mulțimii A.
Numărul combinărilor de n elemente ale mulțimii A este:

\(C_{n}^{k}=\frac{n!}{k!(n-k)!}\)

Are loc relația:
\(C_{n}^{k}=\frac{A_{n}^{k}}{P_{k}}.\)

Proprietățile combinărilor

Fie \(n\in \mathbb{N}^{*}, k\in \mathbb{N}, k\leq n.\)

1. Formula combinărilor complementare:
\(C_{n}^{k}=C_{n}^{n-k}\)

     Caz particular:
     \(C_{n}^{0}=C_{n}^{n}=1\)

2. Fomula de recurență în calculul cu combinări:
\(C_{n}^{k}=C_{n-1}^{k}+C_{n-1}^{k-1}\)

3. \(C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+...+C_{n}^{n}=2^{n}\)
(numărul submulțimilor unei mulțimi cu n elemente).