Heads, Tails And Beans |S|=2

Doc Mike Finnley, Going Postal

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 distinct (non-repeating) elements. 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 combinationsa 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