# Expected maximums and fun with Faulhaber’s formula

A recent Futility Closet post inspired this one. There, Greg Ross mentioned a 2020 paper by P Sullivan titled “Is the Last Banana Game Fair?” in Mathematics Teacher. (BTW, it’s behind a paywall and I haven’t seen that paper). I’m not going to define the last banana game, but instead look at a related question.

Let’s define things more generally. Let $I_n=\{1,2,...,n\}$, let $X,Y$ be two independent, uniform random variables taken from $I_n$, and let $Z=max(X,Y)$. The last banana game post above concerns the case $n=6$. Here, I’m interested in investigating the question: What is $E(Z)$?

Computing this isn’t hard. By definition of independent and max, we have
$P(Z\leq z)=P(X\leq z)P(Y\leq z)$.
Since $P(X\leq z)=P(Y\leq z)={\frac{z}{n}}$, we have
$P(Z\leq z)={\frac{z^2}{n^2}}$.
The expected value of $Z$ is defined as $\sum kP(Z=k)$, but there’s a handy-dandy formula we can use instead:
$E(Z)=\sum_{k=0}^{n-1} P(Z>k)=\sum_{k=0}^{n-1}[1-P(Z\leq k)]$.
Now we use the previous computation to get
$E(Z)=n-{\frac{1}{n^2}}\sum_{k=1}^{n-1}k^2=n-{\frac{1}{n^2}}{\frac{(n-1)n}{6}}={\frac{2}{3}}n+{\frac{1}{2}}-{\frac{1}{6n}}.$
This solves the problem as stated. But this method generalizes in a straightforward way to selecting m independent r.v.s in $I_n$, so let’s keep going.

First, let’s pause for some background and history. Notice how, in the last step above, we needed to know the formula for the sum of the squares of the first n consecutive positive integers? When we generalize this to selecting m integers, we need to know the formula for the sum of the m-th powers of the first n consecutive positive integers. This leads to the following topic.

Faulhaber polynomials are, for this post (apparently the terminology is not standardized) the sequence of polynomials $F_m(n)$ of degree m+1 in the variable n that gives the value of the sum of the m-th powers of the first n consecutive positive integers:

$\sum_{k=1}^{n} k^m=F_m(n)$.

(It is not immediately obvious that they exist for all integers $m\geq 1$ but they do and Faulhaber’s results establish this existence.) These polynomials were discovered by (German) mathematician Johann Faulhaber in the early 1600s, over 400 years ago. He computed them for “small” values of m and also discovered a sort of recursive formula relating $F_{2\ell +1}(n)$ to $F_{2\ell}(n)$. It was about 100 years later, in the early 1700s, that (Swiss) mathematician Jacob Bernoulli, who referenced Faulhaber, gave an explicit formula for these polynomials in terms of the now-famous Bernoulli numbers. Incidentally, Bernoulli numbers were discovered independently around the same time by (Japanese) mathematician Seki Takakazu. Concerning the Faulhaber polys, we have
$F_1(n)={\frac{n(n+1)}{2}}$,
$F_2(n)={\frac{n(n+1)(2n+1)}{6}}$,
and in general,
$F_m(n)={\frac{n^{m+1}}{m+1}}+{\frac{n^m}{2}}+$ lower order terms.

With this background aside, we return to the main topic of this post. Let $I_n=\{1,2,...,n\}$, let $X_1,X_2,...,x_m$ be m independent, uniform random variables taken from $I_n$, and let $Z=max(X_1,X_2,...,X_m)$. Again we ask: What is $E(Z)$? The above computation in the $m=2$ case generalizes to:

$E(Z)=n-{\frac{1}{n^m}}\sum_{k=1}^{n-1}k^m=n-{\frac{1}{n^m}}F_m(n-1).$

For m fixed and n “sufficiently large”, we have

$E(Z)={\frac{m}{m+1}}n+O(1).$

I find this to be an intuitively satisfying result. The max of a bunch of independently chosen integers taken from $I_n$ should get closer and closer to n as (the fixed) m gets larger and larger.

# Harmonic morphisms to P_4 – examples

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph $\Gamma_2=P_4$.

We only consider the cyclic graph on k vertices, $C_k$ as the domain in this post. There are no non-trivial harmonic morphisms $C_5 \to P_4$, so we start with $C_6$. We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: $\phi:\Gamma_1\to \Gamma_2=P_4$ sends the red vertices in $\Gamma_1$ to the red vertex of $\Gamma_2=P_4$ (we let 3 be the numerical notation for the color red), the blue vertices in $\Gamma_1$ to the blue vertex of $\Gamma_2=P_4$ (we let 2 be the numerical notation for the color blue), the green vertices in $\Gamma_1$ to the green vertex of $\Gamma_2=P_4$ (we let 1 be the numerical notation for the color green), and the white vertices in $\Gamma_1$ to the white vertex of $\Gamma_2=P_4$ (we let 0 be the numerical notation for the color white).

To get the following data, I wrote programs in Python using SageMath.

Example 1: There are only the 4 trivial harmonic morphisms $C_6 \to P_4$, plus that induced by $f = (1, 2, 3, 2, 1, 0)$ and all of its cyclic permutations (4+6=10). This set of 6 permutations is closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2) (so total = 10).

Example 2: There are only the 4 trivial harmonic morphisms, plus $f = (1, 2, 3, 2, 1, 0, 0)$ and all of its cyclic permutations (4+7=11). This set of 7 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (2, 1, 0, 1, 2, 3, 3)$ and all 7 of its cyclic permutations (total = 7+11 = 18).

Example 3: There are only the 4 trivial harmonic morphisms, plus $f = (1, 2, 3, 2, 1, 0, 0, 0)$ and all of its cyclic permutations (4+8=12). This set of 8 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (1, 2, 3, 3, 3, 2, 1, 0)$ and all of its cyclic permutations (12+8=20). In addition, there is $f = (1, 2, 3, 3, 2, 1, 0, 0)$ and all of its cyclic permutations (20+8 = 28). The latter set of 8 cyclic permutations of $(1, 2, 3, 3, 2, 1, 0, 0)$ is closed under the transposition (0,3)(1,2) (total = 28).

Example 4: There are only the 4 trivial harmonic morphisms, plus $f = (1, 2, 3, 2, 1, 0, 0, 0, 0)$ and all of its cyclic permutations (4+9=13). This set of 9 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (1, 2, 3, 3, 2, 1, 0, 0, 0)$ and all 9 of its cyclic permutations (9+13 = 22). This set of 9 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (1, 2, 3, 3, 3, 2, 1, 0, 0)$ and all 9 of its cyclic permutations (9+22 = 31). This set of 9 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (1, 2, 3, 3, 3, 3, 2, 1, 0)$ and all 9 of its cyclic permutations (total = 9+31 = 40).

# Harmonic morphisms to P_3 – examples

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph $\Gamma_2=P_3$.

If $\Gamma_1 = (V_1, E_1)$ and $\Gamma_2 = (V_2, E_2)$ are graphs then a map $\phi:\Gamma_1\to \Gamma_2$ (that is, $\phi: V_1\cup E_1\to V_2\cup E_2$) is a morphism provided

1. if $\phi$ sends an edge to an edge then the edges vertices must also map to each other: $e=(v,w)\in E_1$ and $\phi(e)\in E_2$ then $\phi(e)$ is an edge in $\Gamma_2$ having vertices $\phi(v)\in V_2$ and $\phi(w)\in V_2$, where $\phi(v)\not= \phi(w)$, and
2. if $\phi$ sends an edge to a vertex then the edges vertices must also map to that vertex: if $e=(v,w)\in E_1$ and $\phi(e)\in V_2$ then $\phi(e) = \phi(v) = \phi(w)$.

As a non-example, if $\Gamma_1$ is a planar graph, if $\Gamma_2$ is its dual graph, and if $\phi:\Gamma_1\to\Gamma_2$ is the dual map $V_1\to E_2$ and $E_1\to V_2$, then $\phi$ is not a morphism.

Given a map $\phi_E : E_1 \rightarrow E_2 \cup V_2$, an edge $e_1$ is called horizontal if $\phi_E(e_1) \in E_2$ and is called vertical if $\phi_E(e_1) \in V_2$. We say that a graph morphism $\phi: \Gamma_1 \rightarrow \Gamma_2$ is a graph homomorphism if $\phi_E (E_1) \subset E_2$. Thus, a graph morphism is a homomorphism if it has no vertical edges.

Suppose that $\Gamma_2$ has at least one edge. Let $Star_{\Gamma_1}(v)$ denote the star subgraph centered at the vertex v. A graph morphism $\phi : \Gamma_1 \to \Gamma_2$ is called harmonic if for all vertices $v \in V(\Gamma_1)$, the quantity
$\mu_\phi(v,f)= |\phi^{-1}(f) \cap Star_{\Gamma_1}(v)|$
(the number of edges in $\Gamma_1$ adjacent to $v$ and mapping to the edge $f$ in $\Gamma_2$) is independent of the choice of edge $f$ in $Star_{\Gamma_2}(\phi(v))$.

An example of a harmonic morphism can be described in the plot below as follows: $\phi:\Gamma_1\to \Gamma_2=P_3$ sends the red vertices in $\Gamma_1$ to the red vertex of $\Gamma_2=P_3$, the green vertices in $\Gamma_1$ to the green vertex of $\Gamma_2=P_3$, and the white vertices in $\Gamma_1$ to the white vertex of $\Gamma_2=P_3$.

Example 1:

Example 2:

Example 3:

# Michael Reid’s Happy New Year Puzzles, 2018

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some New Year’s puzzles to help start out 2018.

1. Arrange the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 in the
expression $a^b + c^d + e^f + g^h + i^j$ to make 2018.

2. (a) Express $2018 = p^q + r^s$ where p, q, r, s are primes.
(b) Express $2018 = p^q - r^s$ where p, q, r, s are primes.

3. (a) Is it possible to put the first 9 primes, 2, 3, 5, 7, 11, 13,
17, 19 and 23 into a 3×3 matrix that has determinant 2018?
(b) Is it possible to put the first 16 primes, 2, 3, 5, … , 53,
into a 4×4 matrix that has determinant 2018?

4. (a) Express 2018 = A / B using the fewest number of distinct
digits.
For example, the expression 7020622 / 3479 uses only seven
different digits. But it is possible to do better than this.
(b) Express $2018 = (A_1 \cdot A_2 \cdot ... \cdot A_m) / (B_1 \cdot B_2 \cdot ... \cdot B_n)$ using the fewest number of distinct digits.

# Michael Reid’s Happy New Year Puzzle, 2017

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some interesting puzzles to start the New Year; hopefully they are not too easy!

1. Express 2017 as a quotient of palindromes.

2. (a) Are there two positive integers whose sum is 2017 and whose product
is a palindrome?
(b) Are there two positive integers whose difference is 2017 and whose
product is a palindrome?

3. Is there a positive integer n such that both 2017 + n and
2017 n are palindromes?

4. What is the smallest possible sum of the decimal digits of 2017 n ,
where n is …
(a) … a positive integer?
(b) … a prime number?
(c) … a palindrome?

5. Consider the following two operations on a positive integer:
(i) replace a string of consecutive digits by its square,
(ii) if a string of consecutive digits is a perfect cube,
replace the string by its cube root.

Neither the string being replaced, nor its replacement, may have
have “leading zeros”. For example, from 31416 , we may change it to
319616 , by squaring the 14 . From 71253 , we may change it to
753 by taking the cube root of 125 .

(a) Starting from the number 2017 , what is the smallest number we
can reach with a sequence of these operations?
(b) What is the smallest number from which we can start, and reach
the number 2017 with a sequence of these operations?

6. Find a list of positive rational numbers, q_1 , q_2 , … , q_n
whose product is 1 , and whose sum is 2017 . Make your list as
short as possible.
Extra Credit: Prove that you have the shortest possible list.

# Michael Reid’s Happy New Year Problems, 2020

Posted by permission of Michael Reid. Enjoy!

New Year’s Greetings!

Here are some fun puzzles to start the year.

1. Substitute the numbers 1, 2, … , 9 for the letters
a, b, … , i in the expression $a^b + c^d + (e + f + g - h)^i$
to get 2020.

2. Use the digits 1, 2, … , 9 in order, and any of the usual
arithmetic operations and parentheses to get a number that is
as close as possible to, but not exactly equal to 2020.

3. Express 2019/2020 as a sum of distinct Egyptian fractions,
i.e. $1 / n_1 + 1 / n_2 + ... + 1 / n_k$ for integers $0 < n_1 < n_2 < ... n_k < 202049$
(but 202049 is not square).

5. Make a 4×4 matrix of single-digit integers (0-9) with digits
2, 0, 2, 0 on the main diagonal, and having determinant 2020.
Is it possible to do it with a symmetric matrix?

If you liked this one, check out other puzzles ont this blog tagged with “Michael Reid”.

# Differential equations and SageMath

The files below were on my teaching page when I was a college teacher. Since I retired, they disappeared. Samuel Lelièvre found an archived copy on the web, so I’m posting them here.

1. Partial fractions handout, pdf
2. Introduction to matrix determinants handout, pdf
3. Impulse-response handout, pdf
4. Introduction to ODEs, pdf
5. Initial value problems, pdf
6. Existence and uniqueness, pdf
7. Euler’s method for numerically approximating solutions to DEs, pdf.
Includes both 1st order DE case (with Euler and improved Euler) and higher order DE and systems of DEs cases, without improved Euler.
8. Direction fields and isoclines, pdf
9. 1st order ODEs, separable and linear cases, pdf
10. A falling body problem in Newtonian mechanics, pdf
11. A mixing problem, pdf
12. Linear ODEs, I, pdf
13. Linear ODEs, II, pdf
14. Undetermined coefficients for non-homogeneous 2nd order constant coefficient ODEs, pdf
15. Variation of parameters for non-homogeneous 2nd order constant coefficient ODEs, pdf.
16. Annihilator method for non-homogeneous 2nd order constant coefficient ODEs, pdf.
I found students preferred (the more-or-less equivalent) undetermined coefficient method, so didn’t put much effort into these notes.
17. Springs, I, pdf
18. Springs, II, pdf
19. Springs, III, pdf
20. LRC circuits, pdf
21. Power series methods, I, pdf
22. Power series methods, II, pdf
23. Introduction to Laplace transform methods, I, pdf
24. Introduction to Laplace transform methods, II, pdf
25. Lanchester’s equations modeling the battle between two armies, pdf
26. Row reduction/Gauss elimination method for systems of linear equations, pdf.
27. Eigenvalue method for homogeneous constant coefficient 2×2 systems of 1st order ODEs, pdf.
28. Variation of parameters for first order non-homogeneous linear constant coefficient systems of ODEs, pdf.
29. Electrical networks using Laplace transforms, pdf
30. Separation of variables and the Transport PDE, pdf
31. Fourier series, pdf.
32. one-dimensional heat equation using Fourier series, pdf.
33. one-dimensional wave equation using Fourier series, pdf.
34. one-dimensional Schroedinger’s wave equation for a “free particle in a box” using Fourier series, pdf.
35. All these lectures collected as one pdf (216 pages).
While licensed Attribution-ShareAlike CC, in the US this book is in the public domain, as it was written while I was a US federal government employee as part of my official duties. A warning – it has lots of typos. The latest version, written with Marshall Hampton, is a JHUP book, much more polished, available on amazon and the JHUP website. Google “Introduction to Differential Equations Using Sage”.

Course review: pdf

Love, War, and Zombies, pdf
This set of slides is of a lecture I would give if there was enough time towards the end of the semester