# 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 | 147,250 | 6,194,822 | ? | 1,397,790 | 70,491,206 | ? | ? | ? |

6x6 → 2 | 80,518 | 241,218 | 400,474 | 557,031 | 1,123,743 | ? | ? | ? | ? | ? |

6x6 → 3 | 264,500 | 1,848,872 | ? | ? | ? | ? | ? | ? | ? | ? |

6x6 → 4 | 442,791 | 8,313,719 | ? | ? | ? | ? | ? | ? | ? | ? |

6x6 → 6 | 451,206 | 61,412,106 | ? | ? | ? | ? | ? | ? | ? | ? |

6x6 → 9 | 178,939 | 600,896,399 | ? | ? | ? | ? | ? | ? | ? | ? |

6x6 → 12 | 80,092 | ? | ? | ? | ? | ? | ? | ? | ? | ? |

6x6 → 18 | 6,728 | ? | ? | ? | ? | 3,037,561 | ? | ? | ? | ? |

7x7 → 7 | 158,753,814 | ? | ? | ? | ? | ? | ? | ? | ? | ? |

8x8 → 8 | 187,497,290,034 | ? | ? | ? | ? | ? | ? | ? | ? | ? |

9x9 → 9 | 706,152,947,468,301 | ? | ? | ? | ? | ? | ? | ? | ? | ? |

The generation of the numbers in this table was overseen by MGGG’s Zach Schutzman and Daryl DeFord. We used a combination of our own python code and an algorithm coded by Bob Harris (code, writeup; OEIS) in C in 2010. We’ve checked the math behind both algorithms and are confident in both implementations.

As of October 2018, we’ve got runs going on MIT’s OpenStack to extend the coverage of this table. Each missing value is expected to take at least a day, and sometimes weeks or more, of computer time.

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.