Before we can start to solve some counting problems we need to know a little of combinatorics’ notation. Luckily, a few simple rules should get us started. Don’t worry if it doesn’t make sense, that will be my fault. I’ll try to explain it through the examples in later articles.

This notation comes from another branch of mathematics called *set theory*. When we start to count stuff I think that it helps to visualise what the mathematics is doing. In any case, it’s an interesting subject in itself.

### Sets

To count *things* we need a convenient way of organising them. Like a shopping list. Suppose that such a list has written on it: bacon, bread, butter and booze. A good list, I hear you say. We could describe that list as a *set* of food items.

In the world of combinatorics it would be written like this: \(S=\{\text{bacon, bread, butter, booze}\}\). That reads: *set* \(S\) *contains* bacon, bread, butter and booze.

Some other examples of sets:

\[S=\{3,2,5,1,4\}\]

\[S=\{\text{G, F, E, D, C, B, A}\}\]

\[S=\{\text{Cat, Dog, Fox, Tiger, Horse, Mouse}\}\]

\[S=\{(3,1),(1,3),(2,2)\}\]

A set can be identified by a single capital letter, in this case \(S\). Each of the *things* inside of the set are called *elements*. For instance, the third element in the first set, above, is the number 5. The fifth element in the letters set is C. The fourth element in the animals set is Tiger. The *second* element in the last set is (1,3). Notice how the numbers have been grouped together, with parenthesis, to form a single element.

There are three types of sets:

Standard sets are a list of *unordered** **and distinc**t** **(non-repeating) **element**s.** *Set \(A=\{1,2,3\}\) is *equal* to set \(B=\{3,2,1\}\) as all of the elements are the same in each set and the order does not matter. Repetition does not count in a standard set. Set \(A=\{1,1,2,2,3,3\}\) is the same as \(A=\{1,2,3\}\). *With our** shopping list**,** the order in which **we** purchase the items does not matter. The result is still a good evening**.** *

A *multi-set* is a set that contains *unordered and repeated elements*. Set \(A=\{1,1,1,2,2\}\) is equal to \(B=\{1,2,1,2,1\}\). *Again, it does not matter **for **the order in which **we** purchase **the** goods but **we** can now buy as much booze** **and** bacon** as **we** want**.*

A *tuple* is a set that contains both *ordered and **(possibly) **repeated elements*. Tuple \(A=(1,2,2,3)\) is *not equal* to tuple \(B=(2,3,2,1)\) as the order of the elements are different. *We’re* *that wealthy **we** don’t care how much of anything **we** buy **but the booze and bacon have a high priority!*

Sets and multi-sets are enclosed within braces {}. Tuples are enclosed within parenthesis ().

Why is this important? Think about the horse race question from the first part. We need to know not only the horse’s name but also the position (or order) it finished in. For example: suppose three horses are labeled A,B and C. Then the different ways in which they could finish in the 1st, 2nd and 3rd positions would look like this:

\[H=\{(A,B,C),(A,C,B),(B,A,C),(B,C,A),(C,A,B),(C,B,A)\}\]

The order of the letters tells you their position. The third element of set \(H\) tells you that horse B came first, A second and C third. On the other hand think of a lottery ticket. Say, \(T=\{2,6,24,34,45,56\}\). If the lottery machine picks out \(M=\{34,56,2,45,6,24\}\) then you still win. The order of the numbers does not matter.

### Set Cardinality

Don’t panic, it’s not as bad as it sounds! It means *how many* *elements are there in a set*. Take the lottery ticket example, above. Set \(T\) has six elements in it. In combinatorics we write it thus:

\[|T|=6\]

If you see the two vertical bars | | we are asking for the size of the set. With the horse race example \(|H|=6\), NOT 18. Each tuple counts as a single element in the set \(H\). Tuple \(S=(A,B,C)\) would have the size \(|S|=3\). Set \(T=\{(A,B,C)\}\) has the size \(|T|=1\), as tuple \((A,B,C)\) is enclosed in the larger set \(T=\{ \}\).

Individually, tuple \(S=(A,B,C)\) is equal to set \(T=\{A,B,C\}\), and both have the size \(|S|=|T|=3\).

Clear as mud, right? I know, but let’s stick with it…

This leads us to an example of an annoying notation problem when reading mathematics – the two vertical bars.

Simply, if the letter between the two bars is a capital then we are counting the size of a set. If the letter is lower-case then it’s a *variable* with the *sign* removed or the *absolute* value. Example: \(x=-5.6, Y=\{8,4,9\}\) therefore, \(|x|=5.6, |Y|=3\), unless otherwise stated!. Context is important in the art of reading mathematics.

When we count the number of *ordered* elements in a set we are said to be counting the *permutations** *– a horse race*. *When we count the *unordered* elements we are counting the *combinations** – *a lottery.* *It’s funny that a bicycle lock is called a combination lock rather than a permutation lock. Strictly speaking, a combination lock wouldn’t be very secure as {123} would be the same as {321}, {213}, {312}, {132} and {231} to unlock it.

In the next lesson we’ll look at the Labour party’s postal votes – or how a set can magically appear out of nowhere. Seriously.

© Doc Mike Finnley 2019