Generating Permutation-Respecting Partitions

One of the fun things about being specifically an applied mathematician is knowing when my colleagues are dealing with a combinatorial explosion. Recently, a friend of mine asked me if there were an easy way to determine how many of the partitions of a set of sixteen fixed elements obeyed a certain set of conditions. Doing this with brute force was a non-starter: there were over \(10^{10}\) of them, and if we were able to check sixteen thousand partitions per second the calculation would still have taken more than a week.

Read More

Sales Tax and Geometric Series

It is known that, for \(\vert r \vert<1\), \(\sum_{n=0}^\infty ar^n=\frac{a}{1-r}\). The usual proof goes something as follows: let \(S=\sum_{n=0}^\infty ar^n\). Then \(rS=\sum_{n=0}^\infty ar^{n+1}=\sum_{n=1}^\infty ar^n\). Subtracting, \(S-rS=\sum_{n=0}^\infty ar^n-\sum_{n=1}^\infty ar^n=a\), so \(S=\frac{a}{1-r}\) as required. It’s very elegant, but it seems a little bit magical.

Read More

A Linear Independence Problem from Mrs. Perrett

Back in high school, I had a math teacher called Shirley J. Perrett. (She would introduce herself as “Mrs. \(Pe^2r^2t^2\), but not in that order.”) She had a textbook called A2 Core Maths for Edexcel, by Emanuel, Wood, and Crawshaw. And that textbook had a problem in chapter 15 that none of the students Mrs. Perrett had ever taught had solved without hints.

Read More

Fourier Interpolation and Zero-Padding in the Middle

Let \(f\) be a function that you want to interpolate on the interval \([0, 1]\). Let \(k\) be some number of points. Say you know the values of \(f_i=f(i/k)\) for \(i=0, \dots, k-1\). If you knew that \(f\) were periodic with period \(1\), or in general if you knew that \(f\) decomposed into a sum of sinusoids with low frequencies, how might you leverage that knowledge to estimate \(f_{i+1/2}=f((i+1/2)/k)\)? (I’m assuming that the interpolation you have in mind exactly doubles the density of the grid. If you want to interpolate even more points, just repeat your procedure.)

Read More

How to Drink Boba

When I was young, I consumed a piece of media – I’m being vague because I genuinely don’t remember any more than this – starring a dogmatic food critic who had published a book called How to Eat Food: A Comprehensive Guide to the Food You Should Like and the Food You Shouldn’t. Ever since, I’ve thought that this would be a fantastic title for something sufficiently tongue-in-cheek to pull it off. I don’t know anywhere near enough about food to write that, but I do drink quite a lot of bubble tea, and I’ve been told that my thoughts about it are more systematic than those of the average bear, so here goes. This is my comprehensive guide to the boba you should like and the boba you shouldn’t.

Read More

Tensor Network Diagrams for People in a Hurry

A tensor is a multidimensional array. A vector is a \(1\)-tensor; a matrix is a \(2\)-tensor. \(3\)-tensors, \(4\)-tensors, and so on also exist, and we treat them very similarly. If \(v\) is a vector, we might use \(v_i\) to refer to the \(i\)-th element. If \(A\) is a matrix, we might consider elements \(A_{ij}\). For higher-dimensional tensors, we just add more indices: \(T_{ijkl}\) refers to a specific element of the \(4\)-tensor \(T\).

Read More