Spelling Bee - real combinatorics example

Question

The hint section of a puzzle game indicates that are eighteen words starting with G.

The number of words having four, five, six or seven letters are 7,3,7 respectively 1. There are 6, 1, 8 and 3 words starting with GE, GH, GI and GL

For example

\begin{array}{|c|c|c|c|} \hline 7 & 3 & 7 & 1 \\ \hline 2 & 2 & 2 & & GE & 6 \\ \hline 1 & & & & GH & 1 \\ \hline 3 & & 4 & 1 & GI & 8 \\ \hline 1 & 1 & 1 & & GL &3\\ \hline \end{array}

satisfies the eight conditions.

How many non-negative solutions has this system of eight equations ?

I got 1274 solutions by Polya and I see no other way of doing this.

Are there other ideas ?

Answer 1

This is a question about enumerating the number of contingency tables that have prescribed margin sums. This is a topic of interest in statistical design that has inspired much research (by e.g Diaconis, Barvonik, deLoera) and can be tackled with rather sophisticated methods. The following is a sketch of an elementary (but cumbersome) approach whose execution would be straightforward but tedious. It's a divide and conquer strategy. It does not use Polya's method.

1. Consider first as an easier problem any 2x2 contingency table (whose entries are 4 unknowns). Once its four margin sums (denoted $R_1, R_2, C_1, C_2$) are prescribed, you get 4 equations for the four unknown table entries. However, the margin sums are subject to a compatibility condition $R_1+R_2= C_1+C_2$ which reduces the dimensionality of the linear system of constraints by 1. Thus the solution set of this linear system is one-dimensional, parametrized by e.g. the (1,1) entry of the table, which we call $x$. The requirement that all four tabular entries be positive imposes four inequalities on $x$: $ x\geq 0, x\leq C_1, x\leq R_1, x\geq R_1- C_2$. The solution set for $x$ is an interval whose endpoints are explicitly determined by these constraints. Obviously the number of solutions $Q$ is an explicit function of the input data $(R_1, R_2, C_1, C_2)$.

2. Consider now any 4x4 table whose unknown entries have prescribed margin sums. Draw and quarter the table: split the 4x4 table into four disjoint 2x2 sub squares. The vertical and horizontal bisectors form a cross. Consider the margin sums of each of these small 2x2 sub-squares. (There are in all 4x4=16 such small sums).It suffices to know only 8 such small sums to determine all the other small sums. (Specifically it suffices to know all the small sums inside the upper left and lower right subsquares.) These 8 necessary small sums can be entered at locations on the cross.
   Now apply this process in reverse. Imagine filling in the cross with every feasible collection of such 8 small entries. (Tabulating all those possible feasible choices is of course tedious! For example, the top entry in the cross could be any number between 0 and $R_1$). However, once you have assigned values to all the entries in the cross, you can then compute the number of ways to fill in the 2x2 sub squares using the equation in step (1). Because the internal contents of the sub-squares are independent of one another (once the cross entries are prescribed) the number of ways you can create the big 4x4 tables is the product of the ways you fill in each of the four sub-squares. Now sum such products over all possible crosses.