maths.free › Combinatorics & Graph Theory › The counting principles

The counting principles

Product rule, sum rule, permutations, combinations, and when each applies.

Independent choices multiply; exclusive alternatives add. Ordered selections are permutations, unordered are combinations. Picture it: a tree diagram, each level a choice, each leaf an outcome. Think it: every counting formula is a bijection with something easy to count.

Àwọn ààtò àwọn ìṣàmúlò-ètò · 5 choose 2

Discrete-Math · Counting

5 choose 2

5,\ 2

Àwọn ìṣàmúlò-ètò

\binom{5}{2} = \frac{5!}{2!\,(5-2)!}
Unordered selections: n! / (k! (n−k)!).
= \frac{120}{2 \times 6} = 10

Fi àwọn àgbèwọlé hàn

\binom{5}{2} = 10

Nígbà yìí Yan àwọn àkóónú kan, tàbí tẹ̀ àtí kọ́ àwọn àkóónú rẹ̀. Àwọn ìṣàmúlò-ètò gbogbo, àwòrán, àwọn à

Fi iṣẹ́ rẹ̀ pamọ́

A free account adds notes on every lesson, a record of what you have finished, your solved problems in one place, and a tutor you can ask about this page. The maths itself is open to everyone, signed in or not.

Fikún Àwọn Ìṣàmúlò-ètò

Àwọn àmì-ìwé tí a lo níbẹ̀

Tẹ àwọn àmì-ìwé fún ìṣàfarawé fún àwọn ìṣàmúlò-ètò, àwòrán, àti àwọn àmì-ìwé àwọn àmì-ìwé.

Bii o ṣe le: The counting principles

Decide whether order matters (permutation) or not (combination).
Decide whether repetition is allowed.
Break the count into independent stages (multiply) or exclusive cases (add).
Sanity-check with a tiny case you can list by hand.

Àwọn Àtòjọ-ẹ̀yàn

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Diẹ̀ nínú Combinatorics & Graph Theory

Pigeonhole principle and inclusion, exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs