Counting the elements of a set

We are going to deal with counting problems like how many ways there are to distribute 20 distinguishable or indistinguishable objects to eight people or form an anagram of a word or form an anagram of a word in which no initial letters remains at its place, form a hand of five cards from a deck of 52 in which, for instance, all suites are present. These are counting problems related to real life events and our effort will be to translate these problems into a mathematical model. The first step in this direction is to count the numbers of elements of a set.

Let me recall that a set is something in such a way that for any given object, you can decide whether or not

it belongs to the set: here we have the set of the islands of Venice for instance, and Crete does not belong anymore to the islands of Venice, for instance; or, two is an element of the set 1, 2, 3, 4.

Counting the elements of a set could sound an easy task, it’s just enough to count, but actually, there are very big sets and some sets can be characterized through some properties and it would take a very long time to count every element of the set.

Let us look at some examples: the sets of five cards among 52 cards that had all the four suites. How many are there of these sets? Or look at the sequences of 25 birth data of 25 people and how many of these sequences of 25 birth dates contains at least two equal birth dates? So you have a very, very huge set of sequences.

Now, let us introduce some notation. We write for a set X, we insert two bars to indicate to denote the number of elements of the set X (sometimes the diesis will replace the two bars) and there are some obvious properties of the number of elements

or cardinality also of finite sets: the empty set is irrelevant; if one set is included in the other, the number of elements of the smaller is less than the number of elements of the bigger; the Cartesian product has as many elements as the product of the elements of the two sets. The Cartesian product is the set of sequences of pairs X, Y, where X belongs to the first set and Y belongs to the second set;

there is a precise order: the first element is an element of the first set, and the second is an element of the second set. And finally, what is called “the inclusion-exclusion” principle for two sets, the cardinality of the union of X and Y is the sum of the cardinalities of the first of X and Y minus the cardinality of the intersection. You can see, the reason is that when you count the number of elements of X and the number of elements of Y, you count twice the number of elements of the intersection.

There is a principle that is widely used in combinatorics and it is the fact that if there is a one-to-one correspondence between two sets, X and Y, then they have exactly the same number of elements, the same cardinality. And it is an obvious principle, but it is fundamental in order to show sometimes that a set has a given cardinality. For example, consider the sets of five cards in a poker deck. The cardinality of this set is the same of the cardinality of the sets of five numbers among the number from one to 52, there is an obvious correspondence between the numbers 1 to 52 with the cards of a poker deck.