De Moivreov teorem

De Moivreov teorem u kombinatorici je matematički poučak koji govori o svojstvu multiskupova, odnosno kolekciji objekata koji se smiju ponavljati, za razliku od skupova. Ako se neki element multiskupa ponavlja beskonačno mnogo puta, kažemo da ima beskonačnu kratnost. Teorem je nazvan po francuskom matematičaru Abrahamu de Moivreu.

Teorem glasi:

Neka je $M$ multiskup s $n$ različitih elemenata od kojih svaki ima beskonačnu kratnost. Tada je broj r-kombinacija od $M$ u kojima se svaki od $n$ različitih elemenata pojavljuje barem jednom jednak ${\binom {r-1}{n-1}}$.

Dokaz

Neka je $M=\{\infty \cdot a_{1},\infty \cdot a_{2},...,\infty \cdot a_{n}\}$. Zanima nas koliko ima r-kombinacija od $M$ koje su oblika $A=\{k_{1}\cdot a_{1},k_{2}\cdot a_{2},...,k_{n}\cdot a_{n}\}$ gdje je $k_{i}\geq 1,k_{1}+k_{2}+...+k_{n}=r$. Treba uočiti da je skup svih takvih r-kombinacija u bijekciji sa svim uređenim n-torkama $(k_{1}-1,k_{2}-1,...,k_{n}-1)$ nenegativnih cijelih brojeva čija je suma $(k_{1}-1)+...+(k_{n}-1)=r-n$, a njih ima koliko i rješenja jednadžbe $x_{1}+x_{2}+...+x_{n}=r-n$ u skupu ${\mathbb {N} _{0}}^{n}$, a njih ima ${\binom {n+(r-n)-1}{r-n}}={\binom {r-1}{r-n}}={\binom {r-1}{n-1}}.$