RSS preview of John D. Cook

Rss preview of Blog of John D. Cook

Trinomial Coefficients and Kings

2025-05-16 17:11:28

The term trinomial coefficient is used a couple different ways. The most natural use of the term is a generalization of bionomial coefficients to three variables, i.e. numbers of the form

$\frac{n!}{i! \, j! \, k!}$

where i + j + k = n. These numbers are the coefficients of y^jz^k in the expansion of (x + y + z)ⁿ.

But there’s another use of the term trinomial coefficient, the one that we are interest in for this post, and that is the coefficients of x^k in the expansion of (1 + x + 1/x)ⁿ. These numbers can be visualized in a triangle analogous to Pascal’s triangle.

In Pascal’s triangle, each entry is the sum of the two entries above it. In the trinomial triangle, each entry is the sum of the three entries above it.

If you’ve been reading this blog regularly you know I’ve been interested in chess puzzles lately. The thing that make me interested in trinomial coefficients is that they relate to moves of a king on a chessboard.

If you note the number paths a king can take to a square using the minimal number of moves, you get the trinomial triangle. The reason is simple: the number of ways to get to a square equals the number of ways to get there via the square up and to the left, plus the number of ways to get their via the square above, plus the number of ways to get their via the square up and to the right.

The post Trinomial Coefficients and Kings first appeared on John D. Cook.

Riff on an integration bee integral

2025-05-16 15:27:05

I saw an integral posted online that came from this year’s MIT Integration Bee.

$\int_0^1 x^{2024} (1 - x^{2025})^{2025}\, dx$

My thoughts on seeing this were, in order:

It looks like a beta function.
The answer is a small number.
You can evaluate the integral using the substitution u = 1 − x²⁰²⁵.

I imagine most students’ reactions would be roughly the opposite. They’d first see the substitution. Some might think of the value being small, and none would think of beta functions.

Size estimate

The value of the integral is small because you have numbers between 0 and 1 being raised to large powers. In real applications, being able to estimate the size of integral may be more valuable than being able to compute the integral.

But on a quiz, like the Integration Bee, knowing that the result is small would be worthless, except possibly to check a result. You know from the context of the problem being on a timed quiz that there must be a trick [1].

Incidentally, if you changed the problem slightly, say by replacing one of the instances of 2025 with 2025.03, the integration problem becomes much harder, but you could still estimate that the value is small.

Beta functions

The first time I saw someone evaluate an integral by recognizing a beta function it seemed like he was pulling a rabbit out of a hat. I was completely surprised that he thought something was common knowledge that I’d never seen.

Years later I went to work in biostatistics at MDACC and worked with the beta function and beta random variables all the time. If you look through my publications, you’ll see the word “beta” appears several times.

The beta function is defined as follows. You could take the first equality as the definition and the second as a theorem.

$B(x, y) = \int_0^1 t^{x-1} (1 - t)^{y-1} \,dx = \frac{\Gamma(x) \, \Gamma(y)}{\Gamma(x+y)}$

The integrand in the definition of the beta function is the probability density function for a beta(x, y) random variable, and so B(x, y) is the normalizing constant for a beta(x, y) probability distribution.

The integral in the Integration Bee question is not a beta function. I thought maybe it could be turned into a beta function, but the u substitution is simpler.

If you change the integrand above to

$\int_0^1 x^{2024} (1 - x)^{2025}\, dx$

then you do have a beta function. The value of this integral is B(2025, 2026) which equals 2024! 2025! / 4050!, which is an extremely small number.

Numerical estimation

The integral in the previous section is roughly the same as that of x²⁰²⁴ (1 − x)²⁰²⁴. This function has its maximum at ½, and so the integrand is less than 2⁻⁴⁰⁴⁸ ≈ 10⁻¹²¹⁹.

If we want to evaluate 2024! 2025! / 4050! numerically we’ll need to be indirect about it because 2024! would overflow and the final result would underflow. We could calculate the log base 10 of the value using Python as follows.

>>> from scipy.special import gammaln
>>> from math import log
>>> (gammaln(2025) + gammaln(2026) - gammaln(4051))/log(10)
-1220.576093208249

So our upper bound got us to within an order of magnitude or two of the result.

[1] When you see the current year used in a math problem, the quiz writer is winking at you. The year is often meant to suggest that a number is large but somewhat arbitrary. Here you suspect that the key to the question would be the same if 2024 and 2025 were replaced with 1997 and 1998. Also, the year is often a hint that you don’t want to use brute force. In this case, it’s a warning not to expand the integrand using the binomial theorem.

The post Riff on an integration bee integral first appeared on John D. Cook.

Another little chess puzzle

2025-05-15 08:06:48

Here’s another little chess puzzle by Martin Gardner, taken from the same paper as earlier.

The task is to place two rooks, two bishops, and two knights on a 4 by 4 chessboard so that no piece attacks any other.

As before, there are two basic solutions, here and here, plus symmetries.

The post Another little chess puzzle first appeared on John D. Cook.

Multiplying by quaternions on the left and right

2025-05-15 04:57:26

The map that takes a quaternion x to the quaternion qx is linear, so it can be represented as multiplication by a matrix. The same is true of the map that takes x to xq, but the two matrices are not the same because quaternion multiplication does not commute.

Let q = a + bi + cj + dk and let _qM be the matrix that represents multiplication on the left by q. Then

$_qM = \begin{bmatrix} a & -b & -c & -d \\ b & a & -d & c \\ c & d & a & -b \\ d & -c & b & a \\ \end{bmatrix}$

Now let M_q be the matrix that represents multiplication on the right by q. Then

$M_q = \begin{bmatrix} a & -b & -c & -d \\ b & a & d & -c \\ c & -d & a & b \\ d & c & -b & a \\ \end{bmatrix}$

Can prove both matrix representations are correct by showing that they do the right thing when q = 1, i, j, and k. The rest follows by linearity.

You might speculate that the matrix representation for multiplying on the right by q might be the transpose of the matrix representation for multiplying on the left by q. You can look at the matrices above and see that’s not the case.

In this post I talk about how to represent rotations with quaterions, and in this post I give an equation for the equivalent rotation matrix for a rotation described by a quaternion. You can prove that the matrix representation is correct by multiplying out _qM and M_q* . Keep in mind that q in that case is a unit quaterion, so the sum of the squares of its components add to 1.

The post Multiplying by quaternions on the left and right first appeared on John D. Cook.

Embeddings, Projections, and Inverses

2025-05-15 00:38:42

I just revised a post from a week ago about rotations. The revision makes explicit the process of embedding a 3D vector into the quaternions, then pulling it back out.

The 3D vector is embedded in the quaternions by making it the vector part of a quaternion with zero real part:

(p₁, p₂, p₃) → (0, p₁, p₂, p₃)

and the quaternion is returned to 3D by cutting off the real part:

(p₀, p₁, p₂, p₃) → (p₁, p₂, p₃).

To give names to the the process of moving to and from quaterions, we have an embedding E : ℝ³ to ℝ⁴ and a projection P from ℝ⁴ to ℝ³.

We can represent E as a 4 × 3 matrix

$E = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}$

and P by a 3 × 4 matrix

$P = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$

We’d like to say E and P are inverses. Surely P undoes what E does, so they’re inverses in that sense. But E cannot undo P because you lose information projecting from ℝ⁴ to ℝ³ and E cannot recover information that was lost.

The rest of this post will look at three generalizations of inverses and how E and P relate to each.

Left and right inverse

Neither matrix is invertible, but PE equals the identity matrix on ℝ³ , and so P is a left inverse of E and E is a right inverse of P.

$PE = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}$

On the other hand, EP is not an identity matrix, and so E is not a left inverse of E, and neither is P a right inverse of E.

$EP = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$

Adjoint

P is the transpose of E, which means it is the adjoint of E. Adjoints are another way to generalize the idea of an inverse. More on that here.

Pseudo-inverse

The Moore-Penrose pseudo-inverse acts a lot like an inverse, which is somewhat uncanny because all matrices have a pseudo-inverse, even rectangular matrices.

Pseudo-inverses are symmetric, i.e. if A⁺ is the pseudo-inverse of A, then A is the pseudo-inverse of A⁺.

Given an m by n matrix A, the Moore-Penrose pseudoinverse A⁺ is the unique n by m matrix satisfying four conditions:

A A⁺ A = A
A⁺ A A⁺ = A⁺
(A A⁺)* = A A⁺
(A⁺ A)* = A⁺ A

To show that A⁺ = P we have to establish

EPE = E
PEP = A⁺
(EP)* = EP
(PE)* = PE

We calculated EP and PE above, and both are real and symmetric, so properties 3 and 4 hold.

We can also compute

$EPE = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} = E$

and

$PEP = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} =P$

showing that properties 1 and 2 hold as well.

The post Embeddings, Projections, and Inverses first appeared on John D. Cook.

Alternative exp and log notation

2025-05-14 03:34:01

The other day I stumbled on an article [1] that advocated writing a^b as a↑b and log_a(b) as a↓b.

$\begin{align*} a &\uparrow b \equiv a^b \\ a &\downarrow b \equiv \log_a b \end{align*}$

This is a special case of Knuth’s up arrow and down arrow notation. Knuth introduces his arrows with the intention of repeating them to represent hyperexponentiation and iterated logarithms. But the emphasis in [1] is more on the pedagogical advantages of using a single up or down arrow.

Advantages

One advantage is that the notation is more symmetric. Exponents and logs are inverses of each other, and up and down arrows are visual inverses of each other.

Another advantage is that the down arrow notation makes the base of the logarithm more prominent, which is sometimes useful.

Finally, the up and down arrow notation is more typographically linear: a↑b and a↓b stay within a line, whereas a^b and log_a(b) extend above and below the line. LaTeX handles subscripts and superscripts well, but HTML doesn’t. That’s one reason I usually write exp(x) rather than e^x here.

Comparison

Here are the basic properties of logs and exponents using conventional notation.

$\begin{align} a^b = c &\iff \log_a c = b \\ \log_b 1 &= 0 \\ \log_b b &= 1 \\ \log_b(b^x) &= x \\ b^{\log_b x} &= x \\ \log_b xy &= \log_b x + \log_b y \\ \log_b \frac{x}{y} &= \log_b x - \log_by \\ a^{\log_b c} &= c^{\log_b a} \\ \log_a b^c &= c (\log_a b) \\ (\log_b a) (\log_a x) &= \log_b x \end{align}$

Here are the same properties using up and down arrow notation.

$\begin{align} a \uparrow b = c &\iff a \downarrow c = b \\ b \downarrow 1 &= 0 \\ b \downarrow b &= 1 \\ b \downarrow (b \uparrow x) &= x \\ b \uparrow (b \downarrow x) &= x \\ b \downarrow xy &= b \downarrow x + b \downarrow y \\ b \downarrow \frac{x}{y} &= b \downarrow x - b \downarrow y \\ a \uparrow (b \downarrow c) &= c \uparrow (b \downarrow a ) \\ a \downarrow (b \uparrow c) &= c (a \downarrow b) \\ (b \downarrow a) (a \downarrow x) &= b \downarrow x \end{align}$

[1] Margaret Brown. Some Thoughts on the Use of Computer Symbols in Mathematics. The Mathematical Gazette, Vol. 58, No. 404 (Jun., 1974), pp. 78-79

The post Alternative exp and log notation first appeared on John D. Cook.

John D. Cook Modify

Rss preview of Blog of John D. Cook

Related posts

Size estimate

Beta functions

Numerical estimation

Related posts

Left and right inverse

Adjoint

Pseudo-inverse

Related posts

Advantages

Comparison

Related posts

John D. CookModify

Rss preview of Blog of John D. Cook

Related posts

Size estimate

Beta functions

Numerical estimation

Related posts

Left and right inverse

Adjoint

Pseudo-inverse

Related posts

Advantages

Comparison

Related posts

The author's social media

John D. Cook Modify