Diskretna matematika se pretežno ukvarja s končnimi in števnimi množicami ter relacijami na njih. Na kratko, ukvarja se z različnimi tipi diskretnih struktur. Med bolj poznane naloge, s katerimi se ukvarja diskretna matematika, so naloge preštevanja. Delu diskretne matematike, ki obravnave takšne naloge, rečemo preštevalna kombinatorika. Poleg preštevalne kombinatorike pa moderna diskretna matematika združuje še vrstno drugih matematičnih področij, kot so:

• teorija grafov,
• teorija končnih geometrij,
• teorija kombinatoričnih načrtov itd.

Če matematik želi prešteti kake objekte s predpisanimi lastnostmi, to običajno stori v dveh korakih: Najprej objekte, ki jih prešteva, združi v množico, nato pa tej množici določi njeno moč (tudi kardinalnost). Pri določanju moči dane množice, si večkrat pomagamo z nekaj preprostimi načeli. Navedimo tri izmed njih.

Mnogokrat si lahko elemente množice $A$ predstavljamo kot urejene $n$-terice, katerih $i$-ta komponenta pripada množici $A_i$. V tem primeru si lahko pomagamo z načelom produkta, ki pravi, da je moč kartezičnega produkta danih množic enaka produktu njihovih moči:

Tipičen zgled uporabe tega načela so naloge z večfaznim izbiranjem. Denimo, da je kombinatorični objekt podan z zaporedjem $n$ izbir, pri čemer v $i$-tem koraku izbiramo izmed možnostmi v množici $A_i$. Takšnen kombinatorični objekt lahko enačimo z urejeno $n$-terico izbir $A_1 \times ... \times A_n$. Število vseh takšnih objektov je tedaj enako produktu moči množic $A_i$. Oglejmo si že konkretno nalogo.

Zgled
Študentsko kosilo je sestavljeno iz predjedi, glavne jedi in sladice. Za predjed si lahko izberemo govejo juho z rezanci ali zelenjavno juho z jušnimi kroglicami. Za glavno jed imamo na razpolago puranji zrezek v gobovi omaki, sardele na žaru ali ocvrt sir. Sladica je bodisi jabolko bodisi čokoladna rezina. Koliko različnih kosil si lahko sestavi študent?

Rešitev

Kadar elemente množice $A$ (katere moč želimo določiti) razporedimo v nekaj med seboj disju A_nktnih podmnožic $A_1, A_2, ..., A_n$, katerih moči poznamo, lahko moč množice A določimo na podlagi načela vsote, ki pravi, da je moč unije paroma disjunktnih množic enaka vsoti njihovih moči:

S tem preprostim načelom lahko na videz zapleteno nalogo (preštevanje elementov množice $A$) prevedemo na več nekoliko manj zapletenih kombinatoričnih nalog (preštevanje elementov podmnožic $A_i$).

Zgled
Varnostni geslo je sestavljeno iz osmih znakov. Vsaj en in največ trije znaki gesla morajo biti številke (med $0$ in $9$), ostali pa črke slovenske abecede. Koliko različnih gesel lahko sestavimo?

Rešitev

Iz definicije moči (kardinalnosti) množice sledi, da imata množici $A$ in $B$ enako moč, brž ko njima obstaja bijektivna preslikava.

Na tem dejstvu sloni morda najpogosteje uporabljen prijem v kombinatoriki: Če želimo prešteti elemente množice $A$, je dovolj poiskati bijektivno preslikavo iz množice $A$ v kako množico $B$, katere moč že poznamo.

Zgled
Naj bo $X$ množica z $n$ elementi. Koliko podmnožic premore množica $A$?

Rešitev