How to count, and what?

The purpose of this MOOC is to let you solve problems of counting like:
– In how many ways can one form a hand of 5 cards chosen among 52?
– In how many ways can one give 25 chocolates to 8 kids? – What is that, in a class of 25 students, at least two of them have a same birthday?
– What is the probability that, if everybody leaves his own hat at the entrance of a club, and takes one randomly going ot, that nobody takes his own hat?

One of the main difficulties is the variety of situations that one has to deal with. None of us is an expert in combinatorics, Alberto is an algebrist and Carlo is an analyst. When we were asked to deliver a course on the topic, from the basic elements to high level topics, we weren’t able to find a suitable book to follow: most of the times every computation seemed to be obtained with a ad hoc tric. We found that the terminology itself was misleading. e.g., calling combination a collection of elements in which the order does not count whereas in the common language a combination is a precisely ordered sequence like (1, 2, 3, 4) (so (1, 2, 3, 4), but not (2, 1, 3, 4) , may unlock your padlock).

During the years we developed the method in order to solve combinatorial problems in two steps:
1) convert every combinatorial problem into that of counting a precise family of mathematical elements like sequences, sets, collections (multisets);
2) Count the number of elements of the mathematical structure by means of some precise counting principles.

For instance, suppose we want to count in how many ways we can distribute 4 different books to 3 students. We identify that the problem is what we call a 3-sharing of the 4 books. We then know, via a counting principle, that these are as many as the number of the sequences of length 4 from {1, 2, 3}: the basic principles permit us to conclude.

We wrote down the material in a convincing way, which is now published in the form of the Springer textbook

C. Mariconda & A. Tonolo, Discrete Calculus – Methods for counting, Springer (2016).

It took us 15 years, the main reason being the fact that we disagree on almost everything, so whatever appears in the final version was approved from both of us after several discussions.

The MOOC is based on the first chapters of the book, though it is self contained.

In this first week we define the mathematical structures and principles that we will encounter all over the MOOC. Welcome to Combinatorics!

Alberto & Carlo