A probability problem suitable for ProblemBased Learning
Un problema de probabilidad adecuado para el Aprendizaje Basado en Problemas
Fecha de recepción y aceptación: 17 de febrero de 2021 y 30 de abril de 2021
DOI: 10.46583/nereis_2021.13.782
J. L. GonzálezSantander^{1*}
^{1} Department of Mathematics. University of Oviedo.
^{*} Correspondecia: University of Oviedo. Department of Mathematics. Calle Federico García Lorca, 18. 33007 Oviedo. Asturias. Spain. Email: gonzalezmarjuan@uniovi.es. ORCID ID: 0000000153484967
abstract 

We propose a simple probability problem for undergraduate level. This problem involves different branches of Mathematics, such as graph theory, linear algebra and hypergeometric sums hence it is quite suitable to be used as an example of ProblemBased Learning. In addition, the problem allows several variations so that it may be introduced to different groups of students at the same time. 

KEYWORDS: ProblemBased Learning, vertex matrix, ChuVandermonde summation formula. 

Resumen 

Se propone un sencillo problema de probabilidad para nivel de grado universitario. Este problema involucra distintas ramas de las matemáticas, como la teoría de grafos, el álgebra lineal o las sumas hipergeométricas, por lo que resulta muy apto para ser usado como aprendizaje basado en problemas. Además, el problema admite diversas variantes, por lo que puede ser propuesto a diferentes grupos de estudiantes simultáneamente. 

PALABRAS CLAVE: Aprendizaje basado en problemas, matriz de incidencia, fórmula de suma de ChuVandermonde. 
INTRODUCTION
We propose a simple probability problem whose solution involves different mathematical areas. The main aim of this problem is to show to the students that although these areas are taught in separate subjects, in fact, they are quite connected to real problems. Therefore, it is quite suitable for ProblemBased Learning [1]. Next, we present the statement of the problem.
Problem If we choose a sequence of m natural numbers, a_{1}, a_{2}, …, a_{m}, at random, such that 1 ≤ ai ≤ n, what is the probability of obtaining a_{1} ≤ a_{2} ≤ ··· ≤ a_{m}?
According to Laplace’s first principle of probability [2], the problem leads straightforwardly to a combinatorial problem to count the number of “favoured events”. This combinatorial problem can be tackled by using the vertex matrix of Graph Theory. Since we have to calculate a certain power of the vertex matrix, we may resort to Linear Algebra diagonalization. However, in this case, diagonalization fails, so that we must perform heuristic reasoning wherein we calculate a hypergeometric sum. Therefore, the solution to this problem entails Probability Theory, Combinatorics, Graph Theory, Linear Algebra, and hypergeometric sums.
Therefore, the problem stated above is quite suitable for ProblemBased Learning at undergraduate level, wherein the solution unfolds in different stages and students are encouraged to go over the properties and relations of different topics. Moreover, the problem admits different variations for which, the students may apply similar strategies.
From probability to linear algebra
According to Laplace’s first principle of probability, the probability p of a certain event to occur is the ratio of the “favoured events” f to the total possible events N, assuming that all events are equally likely. The latter assumption is reasonable since the sequence of natural numbers of the problem are chosen at random.
(1) 
The number of total possible events N is straightforwardly calculated by using the variations with repetition formula. Indeed, for each natural number a_{i} we have n possible natural numbers. Since we have a sequence of m numbers, then
N=VR_{n}^{m}=n^{m} 
(2) 
The number of favoured events is more complicated to calculate because it is subject to some restrictions, i.e. a_{1} ≤ a_{2} ≤ ··· ≤ am. For simplicity, we start considering n = m = 3. In this case, the 10 favoured events are listed below.
111, 112, 113, 122, 123,
133, 222, 223, 233, 333.
We can visualize these sequences as the allowed paths of length 2 in the directed graph shown in figure 1.
Fig.1. Graph for 3 vertices
The element matrix r_{ij} of the vertex matrix R is equal to the number of edges joining vertices i and j [3]. Thereby, the vertex matrix of the graph of figure 1 is
Clearly, the vertex matrix for n ∈ N is the following triangular matrix of order n.
(3) 
The number of different paths going from vertex i to vertex j of length q is the matrix element s_{ij}, where S=R_{n}^{q}, [4]. In our case, q = m – 1. Therefore, the number of favourable events f is given by the sum of all the matrix elements of R_{n}^{m}^{1},
(4) 
In order to calculate the matrix R_{n}^{m}^{1}, we may attempt to get R_{n} in diagonal form, thus
R_{n}=PDP^{1} → R_{n}^{m}^{1}= PD^{m}^{1}P^{1},
where P is a square matrix with the eigenvectors set in columns and D is a diagonal matrix with the eigenvalues set in the main diagonal [4]. However, R_{n} cannot be obtained in diagonal form since R_{n} has got one eigenvalue, λ = 1, and one eigenvector, =(1,0,…,0) . Therefore, let us make another attempt with the following definition.
Definition. Consider the following set of sequences a_{n}^{(0)},a_{n}^{(1)},…a_{n}^{(m)} such that
(5) 
Theorem. The m + 1 power of the R_{n} matrix is given by
(6) 
Proof. Let us prove (6) by induction. For m = 0, equation (6) follows straightforwardly
Assume that (6) is true for m. Let us prove that is also true for m + 1 we have
as we wanted to prove. ■
Therefore, according to (4) and (6), we can sum up all the diagonals of the R_{n}^{m}^{1} matrix, to obtain
(7) 
In summary, our problem would be solved, if we could calculate the set of sequences a_{n}^{(0)},a_{n}^{(1)},…a_{n}^{(m)} satisfying (5). The latter leads us to calculate a hypergeometric sum.
A useful hypergeometric sum
Let us define first a hypergeometric series [5].
Definition. A hypergeometric series is a series ∑c_{k} such that
(8) 
so that
(9) 
where (α)_{k}=Γ(α+k)/ Γ(α) denotes the Pochhammer symbol and Γ(z) is the gamma function.
Lemma. The following summation formula holds true:
(10) 
Proof. Perform variable substitution in (8) to obtain
(11) 
where the upper limit of the sum can be extended to infinity because l/n!=0 for n ∉ Z^{}.
According to (89), rewrite (11) as a hypergeometric series. Indeed,
Thereby,
(12) 
Now, apply ChuVandermonde summation formula [5],
and the following property of the Pochhammer symbol, [6] in combination with the factorial property of the gamma function, Γ(n+1)=n!, n ∈ N, [6],
thus, after some simplification, (12) becomes
as we wanted to prove. ■
Corollary. The following summation formula holds true:
(13) 
Proof. Divide both sides of (10) by s! and rewrite the result in terms of binomial coefficients, shifting the sum index to start at k = 1. ■
Notice that (13) fits in the set of sequences (5) we were looking for. Indeed, take
(14) 
thus
Once we have obtained (14), we calculate the number of favourable events from (7), thereby,
Applying (10), we have
(15) 
Curiously, note that, according to (14), f=a_{n}^{(m)}. As a consistency test, we recover the number of favoured events for n = m = 3, i.e. f=a_{3}^{(3)}= =10 , as aforementioned in the Introduction.
Finally, substitute (2) and (15) in (1), to obtain the probability,
conclusions
We have proposed a simple probability problem whose solution involves Graph Theory, Linear Algebra and hypergeometric sums, hence it is quite suitable for ProblemBased Learning. This problem admits several variations. For instance, we can modify the restrictions of the favoured events, i.e. a_{1} < a_{2} < ··· < a_{m}, so that these variations may be proposed to different groups of students at the same time.
Also, it connects different branches of Mathematics in a very natural way. This is important in an undergraduate level of education since these topics are usually studied separately, but many times they appear intertwined in real problems.
Literature cited
 Boud D, Feletti G. The Challenge of ProblemBased Learning. London: Psychology Press; 1997.
 Laplace PS. Essai philosophique sur les probabilités. 5th ed. Cambridge: Cambridge University Press; 2009.
 Brualdi RA. Introductory to Combinatorics. 5th. ed. Pearson Educational; 2009.
 Anton H, Rorres C. Elementary Linear Algebra. 9th ed. John Wiley & Sons; 2005.
 Andrews GE, Askey R, Roy R. Special Functions. Encyclopedia of Mathematics 71. Cambridge: Cambridge University Press; 1999.
 Oldham K, Myland J, Spanier J. An Atlas of Functions. 2nd ed. New York: Springer; 2009.