364 gifts

On Christmas Day I alluded to the fact that there are 364 gifts in the song “The Twelve Days of Christmas”. Is there a way to prove this that doesn’t require adding everything up?

As a reminder, on day k of Christmas (k = 1, 2, …, 12) the singer receives 1 of gift 1, 2 of gift 2, …, k of gift k. Christmas has 12 days. (Gift 1 is “a partridge in a pear tree”, gift 2 is “turtle doves”, and so on up to gift 12 which is “drummers drumming”, but this is irrelevant.)

So on day k there are total of 1 + 2 + \ldots + k gifts; this is k(k+1)/2 = {k+1 \choose 2}. The total number of gifts received is therefore

{2 \choose 2} + {3 \choose 2} + \cdots + {13 \choose 2}

and by the hockey-stick identity (sometimes also called the Christmas stocking identity) this is {14 \choose 3}. The identity can be proven by induction, but I prefer a combinatorial proof. Consider the subsets of \{1, 2, \ldots, 14\} of size 3 and group them according to their largest element. Then there are {k \choose 2} sets whose largest element is k+1, for each of k = 2, \ldots 13.

This suggests another identity – what if we group according to the middle element of the subset instead? For example, there are 5 × 8 = 40 3-subsets of [14] whose middle element is 6; each one has one element chosen from 1, 2, …, 5 and one element chosen from 7, 8, …, 14. More generally there are k(13-k) 3-subsets of [14] with middle element k. Thus we have

1 \times 12 + 2 \times 11 + 3 \times 10 + \cdots + 12 \times 1 = {14 \choose 3}.

In terms of the song, this is actually a natural way to count. k(13-k) is the number of gifts of type k, since such gifts get given on the last 13-k days – there are 12 total partridges in pear trees, 2 × 11 = 22 total turtle doves, 3 × 10 = 30 total calling birds, and so on until we get back down to 12 drummers drumming. (The most frequent gifts? 42 swans and 42 geese. Maybe that was the question.)

A couple tidbits of Georgia election math

As you may have heard, there are runoff elections going on in Georgia today (January 5, 2021). You don’t need me to tell you this, and it’s probably too late, but if you live in Georgia, vote.

Also the presidential election in Georgia in 2020 was very close, as you may have heard: 49.47% for Biden, 49.24% for Trump. (The law does not allow for runoffs in presidential elections.)

But here’s the surprising thing. Below are two maps of the state of Georgia. Can you spot the difference?

There is one county with a different winner in the two maps – Burke County, in the east-central part of the state. And Burke was won by Clinton in 2016 (left map), but by Trump in 2020 (right map). The only county that switched winners switched in the opposite direction of the state as a whole.

(2020 results from the state’s official election results site, map by me. 2016 results from opendatasoft, map by me.)

Furthermore, what if Georgia had an electoral college made up of counties?

Historically this is not entirely crazy; Georgia used to have something called the County Unit System for statewide primaries. In this system the largest eight counties were classified as “Urban”, the next-largest 30 counties were classified as “Town”, and the remaining 121 counties were classified as “Rural”; urban, town, and rural counties got 6, 4, and 2 votes respectively, awarded on a winner-take-all basis. This benefited rural candidates.

With current population statistics, the “urban” counties would be Fulton, Gwinnett, Cobb, DeKalb, Clayton, Chatham, Cherokee, and Forsyth. These are the county containing most of Atlanta, six suburban Atlanta counties, and the county containing Savannah; this category would better be called “suburban”.). Trump would have won 308 of the 410 county unit votes in 2020 – he won 2 of the 8 “urban” counties, 21 of the 30 “town” counties, and 106 of the 121 “rural” counties. In 2016 he would have won 310 of 410.

Unsurprisingly, a system this biased was found unconstitutional. But what if we had an electoral college? We can start with a simple calculation:

  • in 2020, Biden won 30 of 159 counties, making a total of 53.69% of the state’s population (5,643,569 in Biden counties, 4,867,562 in Trump counties)
  • in 2016, Clinton won 31 of 159 counties, making a total of 53.90% of the state’s population (5,666,008 to 4,845,123) – the difference being Burke, mentioned above.

(Populations are census estimates from the Governor’s Office of Planning and Budget; I used 2018 estimates.)

This surprised me, but upon reflection, it makes sense – the red counties in Georgia are really red. But we all know a real electoral college gives smaller units undue influence. We can simulate that by adjusting the population of each county. In 2020 Biden won counties with 776,007 more people, but he won 99 fewer counties. So if we give each county eight thousand more “people” – analogous to the electoral votes that correspond to Senators – then Trump wins this state-level electoral college. Also in this world he’d be calling county commissioners instead of the Secretary of State.

But in any case we would not be talking about Georgia “flipping” from Republicans to Democrats between 2016 and 2020. The actual flipping was caused, mostly, by Atlanta suburbs moving to the left – but they happened to do so in a way where no counties crossed over. (The flipping of Gwinnett and Cobb, the two largest purely suburban counties, already happened between 2012 and 2016.). I haven’t explored this in-depth but it’s interesting to think about how an electoral college of counties distorts state-level results as a proxy for how an electoral college of states distorts national results.


2021 x 1202 = 2429242, a palindrome.

That is, when you take 2021 and multiply it by its digit-reversal, you get a palindrome.

This is rare – you (if you are young) will see it again in 2101, 2102, 2111, 2201, and then not until five-digit years. It follows from the digits in 2021 being small – according to the Encyclopedia of Integer Sequences, this is a property of integers not ending in 0 with sum of squares of digits < 10.

In general we can view an integer as a polynomial – in the case of 2021, 2x^3 + 2x + 1 – evaluated at x = 10. Call this polynomial f(x). Then its coefficient-reversal is x^{deg(f(x))} f(1/x) where deg(f(x)) is the degree of the polynomial f(x). For eample, if f(x) = 2x^3 + 2x + 1 then we get the reversal x^3 (2/x^3 + 2/x + 1) = 2 + 2x^2 + x^3. Then we can show that g(x) = latex f(x) f(1/x) x^{deg(f(x))} is its own coefficient-reversal. It has degree deg g(x) = 2 deg f(x). Upon substituting 1/x for x and multiply by x^{2 deg f(x)} we get

f(1/x) f(x) (1/x)^{deg f(x)} x^{2 deg f(x)} = f(x) f(1/x) x^{deg f(x)}$

which is g(x) itself.

Now if the coefficients of g(x) are all less than 10, we can interpret this as a fact about integers. The middle coefficient of g(x) is just the sum of the squares of the coefficients of f(x) – for example,

(x^3 + 2x + 1) (x^3 + 2x^2 + 2) = 2x^6 + 4x^5 + 2x^4 + 9x^3 + 2x^2 + 4x + 2

with middle coefficient 2^2 + 2^2 + 1^2 = 9.

For the proof that the sum of the squares is the largest coefficients, wave your hands and say “Cauchy-Schwarz”, then look at Proposition 10 of On Polynomial Pairs of Integers by Martianus Frederic Ezerman, Bertrand Meyer, and Patrick Sole.

Some other interesting properties of the number 2021: it’s a product of two consecutive primes and a value of Euler’s prime-generating polynomial. These don’t contradict each other – the polynomial n^2 + n + 41 is prime when evaluated at 0, 1, 2, …, 39, and 2021 = 44^2 + 44 + 41.

Applied circle packing

Twelve circular muffins fit nicely on a circular plate.

Twelve muffins on a plate.

Yes, I know they’re not quite uniform in size. What do you want? My sous-chef is two years old. Also she was not helping but rather running around under the dining room table.

Anyway, this apparently is not the optimal packing – that is, the one that maximizes the ratio (muffin radius)/(plate radius), although it is a piece of the optimal packing in the infinite plane. You could fit slightly larger muffins if you packed them like this:

File:Disk pack12.svg
Optimal packing of twelve circles in a circle

Image from the Wikipedia article Circle packing in a circle. The proof is due to Ferenc Fodor, The Densest Packing of 12 Congruent Circles in a Circle, Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry 41 (2000) ?, 401–409. The radius of the plate is 4.029… times the radius of the muffin. (This is {2 \over \sqrt{3} x_0} + 1 where x_0 is the smallest positive root of 9x^5 - 15x^4 + 7x^3 - 3x + 1.)

As it turns out, the packing I discovered isn’t all that far off from this constant. Let the radius of the muffin be 1, and draw triangles as below.

The center of the plate is at the center of the packing, which is the center of the red equilateral triangle. If this triangle has side 2, then the distance from its center to any of its vertices is 2/\sqrt{3}. This is the length of the shortest side of the blue triangle.

The blue triangle therefore has sides of length 2/\sqrt{3} and 2, with an angle of 150 degrees between them. The long side of the blue triangle, by the law of cosines, is given by

\sqrt{(2/\sqrt{3})^2 + 2^2 - 2 (2/\sqrt{3}) (2) \cos 5\pi/6} = \sqrt{4/3 + 4 - (8/\sqrt{3}) (-\sqrt{3}/2)} = \sqrt{4/3 + 4 + 4} = \sqrt{28/3}.

The distance from the center to the edge of the plate is then $latex\sqrt{28/3} + 1$, the length of the long side of the blue triangle plus the green line segment which is a single muffin radius. If you’re working this out in your head while watching the aforementioned sous-chef run around at the park, though, you wonder about the numerical value of this constant and think maybe you shouldn’t pull out your phone-calculator. Fortunately it’s easy to work out approximately: \sqrt{28/3} = 3 \sqrt{1 + 1/27}, and remembering \sqrt{1+x} \approx 1 + x/2 for small x this is very close to $3 (1 + 1/54) = 3 + 1/18 \approx 3.055$. So the radius of the (idealized) plate is about 4.055 times the radius of the (idealized) muffin, not all that far off from the 4.029\cdots due to Fodor.

44 candles

Hanukkah candles can be bought in sets of 44. My older daughter came home from preschool with a box, which is how I came to know this.

That number surprised me at first – but on each of the eight nights of Hanukkah you light one candle (the shamash) and then use it to light the number of candles corresponding to the night. So you need 2 + 3 + … + 9 candles; summing the series gives 11 x 8 / 2 = 44.

It does seem like they should give you a few extras in the box, though, in case something goes wrong.

Difference of cubes

My partner and I tried to have “When I’m Sixty-Four” played at our wedding, but we didn’t because I couldn’t find the sheet music.

It’s my birthday. When I’m sixty-four our second child, who will arrive in a few days, will also have an age which is a cube.

We’ll never be prime at the same time, though.

Another odd crossword clue

Actually posted on Tuesday, November 3. Not election news!

Thursday, October 29 New York Times crossword, by Kurt Weller. 36 Across: “Like all prime numbers except one”, three letters.

Answer: same as yesterday’s 34 Across no.

Of course 1 isn’t prime! But I think in mathematical discourse if you spell out the number you’re not referring to it directly. (This week’s posts notwithstanding, mathematical content doesn’t come up enough in crosswords to be sure what the conventions are there.) There is one prime number that is not odd, namely two.

Hopefully this post sees the light of day on Thursday; my cell service is spotty due to Zeta. Not the function having to do with primes, the storm. (I did say there would be a lot of storms.)

Two-thirds of all Fibonacci numbers are…

Today’s New York Times crossword puzzle (October 28, 2020), by Peter Gordon, 34 across. Three letters, “like two-thirds of all Fibonacci numbers”.

The answer is this sequence.

To get the Fibonacci numbers you start with 1 and 1, and then each number is the sum of the two before it. I’ve bolded the even numbers.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

So it’s not just some random smattering of these numbers that happens to be odd, but every third one. To see this, let’s build an addition table for odd and even numbers:

Addition table for even and odd numbers

Then if you start with two odd numbers, just following this gets you

odd, odd, even, odd, odd, even, …

and this will repeat itself forever. (If you started with “odd, even” or “even, odd” you’d get the same pattern, but shifted; if you start with “even, even” then the sequence stays even forever.

(The Twitter hashtag #NYTXW mostly missed this, preferring to focus on, and complain about, the fact that the puzzle was built around a too-long quote from Sex and the City.)

Note that 34 (the position of this clue in the puzzle) is a Fibonacci number. I’d like to think this was intentional.

Which party will be president if there’s a 50-50 Senate?

FiveThirtyEight currently gives Joe Biden an 88% chance of winning the US presidential election, and Donald Trump 12%.

The Economist gives Biden 92, Trump 7.

Both have Biden ahead by 8.4 percent in the popular vote. FiveThirtyEight has 53.6 to 45.2 (with 1.2 percent to third parties), while the Economist has 54.2 to 45.8 (with no third parties – I presume they’re measuring share o the two-party vote). My assumption is that the difference in these odds is due to FiveThirtyEight’s model putting a larger correlation between states than the Economist’s, and therefore giving a wider distribution around that center point.

Both sites also have a model of the Senate election. FiveThirtyEight expects the Democrats to have 51.5 seats after the election, with a 74% chance of control; the Economist expects 52.5 seats for the Democrats, with a 76% chance of control. Recall that if the Senate is tied, 50-50, then the Vice President (Kamala Harris for the Democrats, or Mike Pence for the Republicans) breaks the tie; that is, Senate control belongs to the party holding the White House. So what do the models say about that tie?

FiveThirtyEight presents the diagram below, where the 50/50 bar is split between the parties:

If you hover over the red part of the 50-50 bar you get “1.7% chance” (of a 50-50 Senate and Republican president); if you hover over the blue part you get “11.2% chance” (of a 50-50 Senate and Democratic president). That is, conditional on a 50-50 Senate, FiveThirtyEight gives a probability of 0.112/0.129, or about 87%, of a Democratic president. (This is different from the 88% figure above.)

The Economist, on the other hand, explicitly says that conditional on a 50-50 Senate, there’s an 18% chance of a Democratic presidency:

Which one of these probabilities is more realistic? Where do they come from?

The Economist writes, on their methodology page:

In presidential-election years, the model also simulates which party will control the vice-presidency, which casts the tiebreaking vote in case of a 50-50 split, based on the simulated national popular vote for the House.

FiveThirtyEight’s Senate forecast methodology page doesn’t seem to make a statement about this; they mention that the 2020 Senate model is “mostly unchanged since 2018”, and of course there was no presidential election in 2018.

My instinct is that 50-50 is a bad night for Democrats. The Democrats start with 35 seats not up re-election. Both sites agree on the 15 most Democratic-leaning Senate seats that are up for election. So let’s say that Democrats win those 15 states and no others, for a 50-50 Senate. For the sake of argument, assume that every state that has a Senate seat up for grabs chooses the same party for the Senate and the presidency. So let’s fill in an Electoral College map with those 15 states in blue, and the nineteen other states with Senate seats at stake in red, to get the map below. (15 + 19 = 34, you say? Well, Georgia has two Senate seats at stake.)

Click the map to create your own at 270toWin.com

Next let’s fill in those states that don’t have a Senate election, but are safe for one party or the other. For the Democrats, California, Washington, Hawaii, New York, Maryland, Vermont, Connecticut (and DC). For the Republicans, Utah, North Dakota, Missouri, and Indiana. (I’m old enough to remember when Missouri was a swing state.) Here’s the map you get.

Click the map to create your own at 270toWin.com

So in a world where the Senate is 50-50 in what is probably the most likely way, it looks like the Democrats are right on the cusp of winning the presidency – FiveThirtyEight is probably right after all, to color the 50-50 bar mostly blue. I just hope we don’t get that 269-269 map, partially because it’ll be exhausting and partially because then I should have written a post on how a tied Electoral College gets thrown to the house instead of writing this one.