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	${\displaystyle V_{n,k}}$	${\displaystyle VR_{n,k}}$
Non ordered sample	${\displaystyle C_{n,k}}$	${\displaystyle CR_{n,k}}$

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 ${\displaystyle k=2}$ and ${\displaystyle n=50}$. 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:

${\displaystyle C_{50,2}={\frac {50!}{2!\cdot (50-2)!}}=1225}$

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 ${\displaystyle k=4}$ and ${\displaystyle n=10}$. 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:

${\displaystyle V_{10,4}={\frac {10!}{(10-4)!}}=5040}$

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 ${\displaystyle k=20}$ and ${\displaystyle n=3}$. 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 (${\displaystyle k=20}$) out of a set of 3 elements (${\displaystyle n=3}$), in which repetition is allowed. That is all we need to know to choose the right operation, and the result is:

${\displaystyle CR_{3,20}=C_{22,20}={\frac {22!}{20!\cdot (22-20)!}}=231}$

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:
  1. Injective distribution: every box must have at most 1 object (${\displaystyle k\leq n}$)
  2. Surjective distribution: every box must have at least 1 object (${\displaystyle k\geq n}$)
  3. Bijective distribution: every box must exactly 1 object (${\displaystyle k=n}$)
  4. 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:

Distribution of k objects into n boxes

	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	${\displaystyle VR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}S(k,i)}$	${\displaystyle CR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}P(k,i)}$	${\displaystyle k!\cdot CR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}L(k,i)}$
Injective distribution	${\displaystyle V_{n,k}}$	${\displaystyle 1}$	${\displaystyle C_{n,k}}$	${\displaystyle 1}$	${\displaystyle V_{n,k}}$	${\displaystyle 1}$
Surjective distribution	${\displaystyle n!\cdot S(k,n)}$	${\displaystyle S(k,n)}$	${\displaystyle CR_{n,k-n}}$	${\displaystyle P(k,n)}$	${\displaystyle k!\cdot CR_{n,k-n}}$	${\displaystyle L(k,n)={\frac {k!}{n!}}\cdot {k-1 \choose n-1}}$
Bijective distribution	${\displaystyle n!}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle n!}$	${\displaystyle 1}$

${\displaystyle S(k,n)=\left\{{k \atop n}\right\}:}$ Stirling numbers of the second kind

${\displaystyle P(k,n):}$ Number of partitions of the integer k into n parts

${\displaystyle L(k,n):}$ 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 (${\displaystyle k=3}$) into 7 distinguishable boxes (${\displaystyle n=7}$). That is all we need to know to choose the right operation, and the result is:

${\displaystyle C_{7,3}={\frac {7!}{3!\cdot (7-3)!}}=35}$

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 (${\displaystyle k=8}$) into 5 indistinguishable boxes (${\displaystyle n=5}$). That is all we need to know to choose the right operation, and the result is:

${\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}$

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 (${\displaystyle k=12}$) into 4 distinguishable boxes (${\displaystyle n=4}$). That is all we need to know to choose the right operation, and the result is:

${\displaystyle 12!\cdot CR_{4,12}=12!\cdot C_{15,12}=12!\cdot {\frac {15!}{12!\cdot (15-12)!}}=217945728000}$

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:

Partition of 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	${\displaystyle VR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}S(k,i)}$	${\displaystyle CR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}P(k,i)}$	${\displaystyle k!\cdot CR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}L(k,i)}$
Empty or 1-element subsets	${\displaystyle V_{n,k}}$	${\displaystyle 1}$	${\displaystyle C_{n,k}}$	${\displaystyle 1}$	${\displaystyle V_{n,k}}$	${\displaystyle 1}$
No empty subsets	${\displaystyle n!\cdot S(k,n)}$	${\displaystyle S(k,n)}$	${\displaystyle CR_{n,k-n}}$	${\displaystyle P(k,n)}$	${\displaystyle k!\cdot CR_{n,k-n}}$	${\displaystyle L(k,n)={\frac {k!}{n!}}\cdot CR_{n,k-n}}$
Subsets of 1 element	${\displaystyle n!}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle n!}$	${\displaystyle 1}$

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 (${\displaystyle k=8}$) into 3 ordered subsets (${\displaystyle n=3}$) of non ordered elements. That is all we need to know to choose the right operation, and the result is:

${\displaystyle VR_{3,8}=3^{8}=6561}$

See also

• Twelvefold way

Sources

• Dubois, Jean-Guy. Une systématique des configurations combinatoires simples. Educational Studies in Mathematics15, 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.