Counting with Venn diagrams, tree diagrams and tables

1How many, without counting one by one?

A class teacher in Musanze has a list of 45 students. 28 belong to the football club, 20 to the debate club, and 9 belong to both. How many students belong to neither club? Adding 28 and 20 gives 48, more than the whole class: the 9 students in both clubs have been counted twice. Combinatorics is the mathematics of counting correctly, without listing every case and without counting anything twice. Its results are the raw material of probability, where you will divide one count by another. This lesson uses three tools that make a count visible: the Venn diagram, the tree diagram and the table.

2Venn diagrams

A Venn diagram shows every region at once. Fill it from the inside out: first the intersection (9), then each "only" region ($28-9=1928\; -\; 9\; =\; 19$ and $20-9=1120\; -\; 9\; =\; 11$), and last the region outside both circles ($45-19-9-11=645\; -\; 19\; -\; 9\; -\; 11\; =\; 6$).

For three sets the same reasoning gives

$$n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(A\cap C)-n(B\cap C)+n(A\cap B\cap C)\mathrm{.}n(A\; \backslash cup\; B\; \backslash cup\; C)\; =\; n(A)\; +\; n(B)\; +\; n(C)\; -\; n(A\; \backslash cap\; B)\; -\; n(A\; \backslash cap\; C)\; -\; n(B\; \backslash cap\; C)\; +\; n(A\; \backslash cap\; B\; \backslash cap\; C).$$

The elements in all three sets are added three times and subtracted three times, which is why the last term adds them back once.

3Tree diagrams

When an experiment happens in stages, a tree diagram lists every outcome in order: each stage adds a column of branches, and each path from the root to a tip is one outcome. A canteen that offers a lunch of one starch (rice, cassava bread or plantain) with one sauce (beans or peas) has a tree with 3 branches, each splitting into 2, so $3\times 2=63\; \backslash times\; 2\; =\; 6$ different meals.

Trees are most useful when the stages are not all the same. In a best-of-three match, the match stops as soon as one team has won two games:

4Tables: outcome tables and contingency tables

For two stages with many choices, a table is neater than a tree. Throwing a red die and a blue die gives $6\times 6=366\; \backslash times\; 6\; =\; 36$ outcomes; the table shows each sum:

The 5 shaded cells give a sum of 8: (2, 6), (3, 5), (4, 4), (5, 3) and (6, 2). A table also makes it easy to see that a sum of 7 happens in 6 ways, more than any other sum.

A contingency table (two-way table) counts a group classified in two ways at once. A school's 160 S4 students, by pathway and sex (illustrative data):