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 (variations, permutations, combinations, …). 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 |
[math]\displaystyle{ V_{n,k} }[/math] | [math]\displaystyle{ VR_{n,k} }[/math] |
| Non ordered
sample |
[math]\displaystyle{ C_{n,k} }[/math] | [math]\displaystyle{ CR_{n,k} }[/math] |
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 [math]\displaystyle{ k=2 }[/math] and [math]\displaystyle{ n=50 }[/math]. A pair will be the same no matter the order of the two people. A handshake must be carried out by two different people (no repetition). 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:
- [math]\displaystyle{ C_{50,2}=\frac{50!}{2!\cdot(50-2)!}=1225 }[/math]
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 (base 10), so [math]\displaystyle{ k=4 }[/math] and [math]\displaystyle{ n=10 }[/math]. 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:
- [math]\displaystyle{ V_{10,4}=\frac{10!}{(10-4)!}=5040 }[/math]
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 [math]\displaystyle{ k=20 }[/math] and [math]\displaystyle{ n=3 }[/math]. 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 ([math]\displaystyle{ k=20 }[/math]) out of a set of 3 elements ([math]\displaystyle{ n=3 }[/math]), in which repetition is allowed. That is all we need to know to choose the right operation, and the result is:
- [math]\displaystyle{ CR_{3,20}=C_{22,20}=\frac{22!}{20!\cdot(22-20)!}=231 }[/math]
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:
- Whether the objects are distinguishable or not.
- Whether the boxes are distinguishable or not.
- If the order in which the objects are placed in a box matters.
- The conditions that the distribution must meet. Depending on this, the distribution can be:
- Injective distribution: every box must have at most 1 object ([math]\displaystyle{ k\leq n }[/math])
- Surjective distribution: every box must have at least 1 object ([math]\displaystyle{ k\geq n }[/math])
- Bijective distribution: every box must exactly 1 object ([math]\displaystyle{ k=n }[/math])
- Distribution with no restrictions
Injective distribution
Surective distribution
Bijective distribution
Distribution with no restrictions
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:
| Non ordered distribution | Ordered distribution | |||||
|---|---|---|---|---|---|---|
| Distinguishable objects | Indistinguishable objects | Distinguishable objects | ||||
| Distinguishable boxes | Indistinguishable boxes | Distinguishable boxes | Indistinguishable boxes | Distinguishable boxes | Indistinguishable boxes | |
| Any
distribution |
[math]\displaystyle{ VR_{n,k} }[/math] | [math]\displaystyle{ \sum_{i=1}^n S(k,i) }[/math] | [math]\displaystyle{ CR_{n,k} }[/math] | [math]\displaystyle{ \sum_{i=1}^n P(k,i) }[/math] | [math]\displaystyle{ k!\cdot CR_{n,k} }[/math] | [math]\displaystyle{ \sum_{i=1}^n L(k,i) }[/math] |
| Injective
distribution |
[math]\displaystyle{ V _{n,k} }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ C_{n,k} }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ V _{n,k} }[/math] | [math]\displaystyle{ 1 }[/math] |
| Surjective
distribution |
[math]\displaystyle{ n!\cdot S(k,n) }[/math] | [math]\displaystyle{ S(k,n) }[/math] | [math]\displaystyle{ CR_{n,k-n} }[/math] | [math]\displaystyle{ P(k,n) }[/math] | [math]\displaystyle{ k!\cdot CR_{n,k-n} }[/math] | [math]\displaystyle{ L(k,n)=\frac{k!}{n!}\cdot {k-1 \choose n-1} }[/math] |
| Bijective
distribution |
[math]\displaystyle{ n! }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ n! }[/math] | [math]\displaystyle{ 1 }[/math] |
- [math]\displaystyle{ S(k,n)=\left\{ {k \atop n} \right\}: }[/math] Stirling numbers of the second kind
- [math]\displaystyle{ P(k,n): }[/math] Number of partitions of the integer k into n parts
- [math]\displaystyle{ L(k,n): }[/math] Lah numbers (Stirling numbers of the third kind)
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 ([math]\displaystyle{ k=3 }[/math]) into 7 distinguishable boxes ([math]\displaystyle{ n=7 }[/math]). That is all we need to know to choose the right operation, and the result is:
- [math]\displaystyle{ C_{7,3}=\frac{7!}{3!\cdot(7-3)!}=35 }[/math]
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 ([math]\displaystyle{ k=8 }[/math]) into 5 indistinguishable boxes ([math]\displaystyle{ n=5 }[/math]). That is all we need to know to choose the right operation, and the result is:
- [math]\displaystyle{ S(8,5)= \left\{{8 \atop 5}\right\} =\frac {1}{5!}\sum _{i=0}^5(-1)^i \binom {5}{i}(5-i)^8 = 1050 }[/math]
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 ([math]\displaystyle{ k=12 }[/math]) into 4 distinguishable boxes ([math]\displaystyle{ n=4 }[/math]). That is all we need to know to choose the right operation, and the result is:
- [math]\displaystyle{ 12!\cdot CR_{4,12}=12!\cdot C_{15,12}=12!\cdot\frac{15!}{12!\cdot(15-12)!}=217945728000 }[/math]
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 (previous table). 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:
| Distribution | Partition |
|---|---|
| Ordered | Subsets of ordered elements |
| Non ordered | Subsets of non ordered elements |
| Distinguishable objects | Distinguishable elements |
| Indistinguishable objects | Indistinguishable elements |
| Distinguishable boxes | Ordered partitions |
| Indistinguishable boxes | Non ordered partitions |
| Injective distribution | Subsets of 1 element or empty ones |
| Surjective distribution | No empty subsets |
| Bijective distribution | Subsets of exactly 1 element |
| No restrictions | Subsets 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:
| Non ordered elements | , | |||||
|---|---|---|---|---|---|---|
| Distinguishable elements | Indistinguishable elements | Distinguishable elements | ||||
| Ordered subsets | Non ordered subsets | Ordered subsets | Non ordered subsets | Ordered subsets | Non ordered subsets | |
| Any subsets | [math]\displaystyle{ VR_{n,k} }[/math] | [math]\displaystyle{ \sum_{i=1}^n S(k,i) }[/math] | [math]\displaystyle{ CR_{n,k} }[/math] | [math]\displaystyle{ \sum_{i=1}^n P(k,i) }[/math] | [math]\displaystyle{ k!\cdot CR_{n,k} }[/math] | [math]\displaystyle{ \sum_{i=1}^n L(k,i) }[/math] |
| Empty or 1-element subsets | [math]\displaystyle{ V _{n,k} }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ C_{n,k} }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ V _{n,k} }[/math] | [math]\displaystyle{ 1 }[/math] |
| No empty subsets | [math]\displaystyle{ n!\cdot S(k,n) }[/math] | [math]\displaystyle{ S(k,n) }[/math] | [math]\displaystyle{ CR_{n,k-n} }[/math] | [math]\displaystyle{ P(k,n) }[/math] | [math]\displaystyle{ k!\cdot CR_{n,k-n} }[/math] | [math]\displaystyle{ L(k,n)=\frac{k!}{n!}\cdot CR_{n,k-n} }[/math] |
| Subsets of 1 element | [math]\displaystyle{ n! }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ n! }[/math] | [math]\displaystyle{ 1 }[/math] |
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 (topics) 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 ([math]\displaystyle{ k=8 }[/math]) into 3 ordered subsets ([math]\displaystyle{ n=3 }[/math]) of non ordered elements. That is all we need to know to choose the right operation, and the result is:
- [math]\displaystyle{ VR_{3,8}=3^8=6561 }[/math]
See also
Sources
- Dubois, Jean-Guy. Une systématique des configurations combinatoires simples. Educational Studies in Mathematics 15, 37–57 (1984) doi:10.1007/BF00380438
- V. Navarro-Pelayo; Carmen Batanero; Juan D. Godino (1996). Razonamiento Combinatorio en Alumnos de Secundaria.
- Rafael Roa (2000). Razonamiento Combinatorio en Estudiantes con Preparación Matemática Avanzada.
- Tan Mingshu (2011). Some Combinatorial Identities and Explanations Based on Occupancy Model.
 |  |
