The Known Sizes of Grid Metagraphs

At MGGG, we think that one of the reasons that redistricting is hard to study is that the space of possibilities (i.e., valid districting plans) is so huge it’s unthinkable by humans. And relatedly, the number of ways to achieve any simple objective is overwhelmingly large.

We think that to study districting plans in context, you need to understand the space of alternatives. So we are working on the science of sampling from these universes of districting plans. As a simplified warmup problem, we can ask how many ways there would be to district a jurisdiction made up of a small number of units with equal population arranged in a perfect grid. We can then build up the complexity from there. But this problem is already formidable!

In this table, the row marked nxn → d shows the number of ways to partition an n by n grid into d districts (or connected pieces). The columns describe how much size difference is tolerated among the districts. The two halves of the table distinguish whether, to be considered contiguous, the districts would have to be transitable by a chess rook (making only NSEW moves) or a chess queen (which can also move diagonally). Queen contiguity allows many more district shapes.

Rook Queen
equal size ± 1 ± 2 ± 3 all, non-∅ equal size ± 1 ± 2 ± 3 all, non-∅
2x2 → 2 2 6 6 6 6 3 7 7 7 7
3x3 → 3 10 58 170 226 258 36 224 622 746 782
4x4 → 2 70 206 338 454 627 1,718 4,690 6,630 7,598 8,171
4x4 → 4 117 1,953 8,849 29,069 62,741 2,620 46,456 222,398 710,622 1,130,612
4x4 → 8 36 34,444 153,094 251,230 340,198 280 567,725 2,629,081 4,262,917 5,362,109
5x5 → 5 4,006 193,128 1,472,750 6,194,822 72,137,699 1,397,790 70,491,206 565,708,110 2,467,619,460 19,258,645,522
6x6 → 2 80,518 241,218 400,727 557,031 1,123,743 ? ? ? ? 2,668,525,423
6x6 → 3 264,500 1,848,872 5,006,968 9,714,644 99,699,033 ? ? ? ? 981,728,132,977
6x6 → 4 442,791 8,313,719 36,716,529 98,715,441 2,872,166,677 ? ? ? ? 33,178,431,625,979
6x6 → 6 451,206 61,412,106 787,941,042 4,564,190,094 356,612,826,084 6,025,727,349 ? ? ? 3,628,666,881,233,030
6x6 → 9 178,939 600,896,399 44,824,927,867 1,246,776,785,419 27,173,118,202,682 1,411,875,619 ? ? ? 193,647,162,942,941,072
6x6 → 12 80,092 4,555,902,726 2,994,170,540,354 19,290,275,421,883 217,674,971,893,169 245,410,623 ? ? ? 1,045,944,428,847,211,954
6x6 → 18 6,728 321,276,916,270 13,415,885,335,894 49,804,910,882,006 146,904,919,330,547 3,037,561 ? ? ? 240,051,309,075,264,719
7x7 → 7 158,753,814 ? ? ? 7,146,137,621,219,723 ? ? ? ? 7,291,155,679,611,862,880,190
8x8 → 8 187,497,290,034 ? ? ? 556,983,247,769,141,192,388 ? ? ? ? ?
9x9 → 9 706,152,947,468,301 ? ? ? 163,738,881,245,258,156,011,991,945 ? ? ? ? ?

The initial generation of the numbers in this table was overseen by MGGG’s Zach Schutzman and Daryl DeFord, using a combination of python code and an algorithm coded by Bob Harris (code, writeup; OEIS) in C in 2010. This work was extended in 2021 by Amy Becker, Gabe Schoenbach, and Bhushan Suwal, using their own Julia code and the enumpart algorithm outlined here.

As of April 2021, the missing values on this table are expected to take weeks of computation time and hundreds of gigabytes of RAM.

An earlier version of the table, which appears in November’s print version of Scientific American, used partition enumeration code that was included with the R package redist— that code turns out to be buggy. As a result, some of the numbers have since been corrected.