Elemente de combinatorica si aplicatii

Observaţie:

Dacă este un număr natural prim, iar un număr natural care nu este multiplu de , atunci se divide cu .

Exemple:

1) Deoarece este număr prim, atunci se divide cu .

2) Deoarece este număr prim, iar nu este multiplu de , atunci se divide cu .

(2). Principiul includerii şi excluderii.

Considerăm mulţimile finite.

Dacă sunt două mulţimi nevide, atunci egalitatea

se numeşte formula includerii şi excluderii, numită aşa deoarece unele elemente se includ şi într-o mulţime şi în alta, iar altele se elimină.

Această formulă este adevărată, deoarece în intră de două ori elementele comune ale lui şi , iar în o singură dată. De aceea, în membrul drept se scade numărul acestor elemente comune.

Formula rămâne adevărată şi dacă se înlocuieşte cu şi cu , când avem, de asemenea, formula includerii şi excluderii:

, ceea ce se vede uşor şi se obţine din formula precedentă. Pentru cazul a trei mulţimi formula includerii şi excluderii are forma:

Formula corespunzătoare se obţine uşor de aici prin dualitate.

Materiale Didactice Asemanatoare

Bibliografie