Combinatorial modelling


Combinatorial modelling is the process which lets us identify a suitable mathematical model to reformulate a problem. These combinatorial models will provide, through the combinatorics theory, the operations needed to solve the problem.

Implicit combinatorial models

Simple combinatorial problems are the ones that can be solved by applying just one combinatorial operation. These problems can be classified into three different models, called implicit combinatorial models.

Selection

A selection problem requires to choose a sample of k elements out of a set of n elements. It is needed to know if the order in which the objects are selected matters and whether an object can be selected more than once or not. This table shows the operations that the model provides to get the number of different samples for each of the selections:
Repetition
not allowed		Repetition
allowed
Ordered
sample
Non ordered
sample

Examples

1.- At a party there are 50 people. Everybody shakes everybody’s hand once. How often are hands shaken in total?
What we need to do is calculate the number of all possible pairs of party guests, which means, a sample of 2 people out of the 50 guests, so and. A pair will be the same no matter the order of the two people. A handshake must be carried out by two different people. So, it is required to select an ordered sample of 2 elements out of a set of 50 elements, in which repetition is not allowed. That is all we need to know to choose the right operation, and the result is:
2.- Unfortunately, you can’t remember the code for your four-digit lock. You only know that you didn’t use any digit more than once. How many different ways do you have to try?
We need to choose a sample of 4 digits out of the set of 10 digits, so and. The digits must be ordered in a certain way to get the correct number, so we want to select an ordered sample. As the statement says, no digit was chosen more than once, so our sample will not have repeated digits. So, it is required to select an ordered sample of 4 elements out of a set of 10 elements, in which repetition is not allowed. That is all we need to know to choose the right operation, and the result is:
3.- A boy wants to buy 20 invitation cards to give to their friends for his birthday party. There are 3 types of cards in the store, and he likes them all. In how many ways can he buy the 20 cards?
It is required to choose a sample of 20 invitation cards out of the set of 3 types of cards, so and. The order in which you choose the different types of invitations does not matter. As a type of card must be selected more than once, there will be repetitions in our invitation cards. So, we want to select a non ordered sample of 20 elements out of a set of 3 elements, in which repetition is allowed. That is all we need to know to choose the right operation, and the result is:

Distribution

In a distribution problem it is required to place k objects into n boxes or recipients.  In order to choose the right operation out of the ones that the model provides, it is necessary to know:
The following table shows the operations that the model provides to get the number of different ways of distributing the objects for each of the distributions:

Examples

1.- A maths teacher has to give 3 studentships among his students. 7 of them got an 'outstanding' grade, so they are the candidates to get them. In how many ways can he distribute the grants?
Let's consider the 3 studentships are objects that have to be distributed into 7 boxes, which are the students. As the objects are identical studentships, they are indistinguishable. The boxes are distinguishable, as they are different students. Every studentship must be given to a different student, so every box must have at most 1 object. Furthermore, the order in which the objects are placed in a boxes does not matter, because there cannot be more than one on each box. So, it is a non ordered injective distribution of 3 indistinguishable objects into 7 distinguishable boxes. That is all we need to know to choose the right operation, and the result is:
2.- A group of 8 friends rent a 5-room cottage to spend their holidays. If the rooms are identical and no one can be empty, in how many ways can they be distributed in the cottage?
Let's consider the friends are objects that have to be distributed into 5 boxes, which are the rooms. As the objects are different people, they are distinguishable. The boxes are indistinguishable, as they are identical rooms. We can consider it as a non ordered distribution, because the ordered in which everyone is placed in the rooms does not matter. No room can be empty, so every box must have at least 1 object. So, it is a non ordered surjective distribution of 8 distinguishable objects into 5 indistinguishable boxes. That is all we need to know to choose the right operation, and the result is:
3.- 12 people are done shopping in a supermarket where 4 cashiers are working at the moment. In how many different ways can they be distributed into the checkouts?
Let's consider the people are objects that have to be distributed into boxes, which are the check-outs. As the people and the checkouts are different, the objects and the boxes are distinguishable. The order in which the objects are placed in the boxes matter, because they are people getting into queues. The statement does not mention any restriction. So, it is an ordered distribution with no restrictions of 12 distinguishable objects into 4 distinguishable boxes. That is all we need to know to choose the right operation, and the result is:

Partition

A partition problem requires to divide a set of k elements into n subsets. This model is related to the distribution one, as we can consider the objects inside every box as subsets of the set of objects to distribute. So, each of the 24 distributions described previously has a matching kind of partition into subsets. So, a partition problem can be solved by transforming it into a distribution one and applying the correspondent operation provided by the distribution model. Following this method, we will get the number of possible ways of dividing the set. The relation between these two models is described in the following table:
DistributionPartition
OrderedSubsets of ordered elements
Non orderedSubsets of non ordered elements
Distinguishable objectsDistinguishable elements
Indistinguishable objectsIndistinguishable elements
Distinguishable boxesOrdered partitions
Indistinguishable boxesNon ordered partitions
Injective distributionSubsets of 1 element or empty ones
Surjective distributionNo empty subsets
Bijective distributionSubsets of exactly 1 element
No restrictionsSubsets of 1 or more elements or empty ones

This relation let us transform the table provided by the distribution model into a new one that can be used to know the different ways of dividing a set of k elements into n subsets:

Examples

1.- A group of 3 classmates have to make a thesis about 8 different maths topics. In how many ways can they split the work to do?
We need to divide the set of 8 topics into 3 subsets. These subsets will be the topics that each of the students will work on. The elements in the set are distinguishable. The partitions must be ordered because each one will correspond to a different student, but the topics inside every subset do not have to be ordered because each student can decide which order to follow when working on the thesis. The statement does not mention any restriction of the subsets. So, it is required to divide a set of 8 elements into 3 ordered subsets of non ordered elements. That is all we need to know to choose the right operation, and the result is: