{'fraction_non_alphanumeric': 0.05252385196923179, 'fraction_numerical': 0.012974150737842924, 'mean_word_length': 4.149948996939816, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Untying The Gordian Knot via Experimental Mathematics

In this methodological article on experimental-yet-rigorous enumerative combinatorics, we use two instructive case studies, to show that often, just like Alexander the Great before us, the simple,"cheating"solution to a hard problem is the best. So before you spend days (and possibly years) trying to answer a mathematical question by analyzing and trying to 'understand' its structure, let your computer generate enough data, and then let it guess the answer. Often its guess can be proved by a quick 'hand-waving' (yet fully rigorous) 'meta-argument'. Since our purpose is to illustrate a methodology, we include many details, as well as Maple source-code.


Introduction
Once upon a time there was a knot that no one could untangle, it was so complicated. Then came Alexander the Great and, in one second, cut it with his sword.
Analogously, many mathematical problems are very hard, and the current party line is that in order for it be considered solved, the solution, or answer, should be given a logical, rigorous, deductive proof.
Suppose that you want to answer the following question: Find a closed-form formula, as an expression in n, for the real part of the n-th complex root of the Riemann zeta function, ζ(s) . Let's call this quantity a(n). Then you compute these real numbers, and find out that a(n) = 1 2 for n ≤ 1000. Later you are told by Andrew Odlyzko that a(n) = 1 2 for all 1 ≤ n ≤ 10 10 . Can you conclude that a(n) = 1 2 for all n? We would, but, at this time of writing, there is no way to deduce it rigorously, so it remains an open problem. It is very possible that one day it will turn out that a(n) (the real part of the n-th complex root of ζ(s)) belongs to a certain ansatz, and that checking it for the first N 0 cases implies its truth in general, but this remains to be seen.
On the other hand, in order to (rigorously) prove that 1 3 + 2 3 + 3 3 + · · · + n 3 = (n(n + 1)/2) 2 , for every positive integer n, it suffices to check it for the five special cases 0 ≤ n ≤ 4, since both sides are polynomials of degree 4, hence the difference is a polynomial of degree ≤ 4, given by five 'degrees of freedom'. This is an example of what is called the 'N 0 principle'. In the case of a polynomial identity (like this one), N 0 is simply the degree plus one.
But our favorite ansatz is the C-finite ansatz. A sequence of numbers {a(n)} (0 ≤ n < ∞) is C-finite if it satisfies a linear recurrence equation with constant coefficients. For example the Fibonacci sequence that satisfies F(n) − F(n − 1) − F(n − 2) = 0 for n ≥ 2.
The C-finite ansatz is beautifully described in Chapter 4 of the masterpiece 'The Concrete Tetrahedron' ( [KP]), by Manuel Kauers and Peter Paule, and discussed at length in [Z1].
Here the 'N 0 principle' also holds (see [Z3]), i.e. by looking at the 'big picture' one can determine a priori, a positive integer, often not that large, such that checking that a(n) = b(n) for 1 ≤ n ≤ N 0 implies that a(n) = b(n) for all n > 0.
A sequence {a(n)} ∞ n=0 is C-finite if and only if its (ordinary) generating function f (t) := ∞ n=0 a(n) t n is a rational function of t, i.e. f (t) = P(t)/Q(t) for some polynomials P(t) and Q(t). For example, famously, the generating function of the Fibonacci sequence is t/(1 − t − t 2 ).
Phrased in terms of generating functions, the C-finite ansatz is the subject of chapter 4 of yet another masterpiece, Richard Stanley's 'Enumerative Combinatorics' (volume 1) ( [S]). There it is shown, using the 'transfer matrix method' (that originated in physics), that in many combinatorial situations, where there are finitely many states, one is guaranteed, a priori, that the generating function is rational.
Alas, finding this transfer matrix, at each specific case, is not easy! The human has to first figure out the set of states, and then using human ingenuity, figure out how they interact.
A better way is to automate it. Let the computer do the research, and using 'symbolic dynamical programming', the computer, automatically, finds the set of states, and constructs, all by itself (without any human pre-processing) the set of states and the transfer matrix. But this may not be so efficient for two reasons. First, at the very end, one has to invert a matrix with symbolic entries, hence compute symbolic determinants, that is time-consuming. Second, setting up the 'infra-structure' and writing a program that would enable the computer to do 'machine-learning' can be very daunting.
In this article, we will describe two case studies where, by 'general nonsense', we know that the generating functions are rational, and it is easy to bound the degree of the denominator (alias the order of the recurrence satisfied by the sequence). Hence a simple-minded, empirical, approach of computing the first few terms and then 'fitting' a recurrence (equivalently rational function) is possible.
The first case-study concerns counting spanning trees in families of grid-graphs, studied by Paul Raff ([R]), and F.J. Faase ([F]). In their research, the human first analyzes the intricate combinatorics, manually sets up the transfer matrix, and only at the end lets a computer-algebra system evaluate the symbolic determinant.
Our key observation, that enabled us to 'cut the Gordian knot' is that the terms of the studied sequences are expressible as numerical determinants. Since computing numerical determinants is so fast, it is easy to compute sufficiently many terms, and then fit the data into a rational function. Since we easily have an upper bound for the degree of the denominator of the rational function, everything is rigorous.
The second case-study is computing generating functions for sequences of determinants of 'almost diagonal Toeplitz matrices'. Here, in addition to the 'naive' approach of cranking enough data and then fitting it into a rational function, we also describe the 'symbolic dynamical programming method', that surprisingly is faster for the range of examples that we considered. But we believe that for sufficiently large cases, the naive approach will eventually be more efficient, since the 'deductive' approach works equally well for the analogous problem of finding the sequence of permanents of these almost diagonal Toeplitz matrices, for which the naive approach will soon be intractable.
This article may be viewed as a tutorial, hence we include lots of implementation details, and Maple code. We hope that it will inspire readers (and their computers!) to apply it in other situations

Accompanying Maple Packages
This article is accompanied by three Maple packages, GFMatrix.txt, JointConductance.txt, and SpanningTrees.txt, all available from the url http://sites.math.rutgers.edu/˜zeilberg/mamarim/mamarimhtml/gordian.html In that page there are also links to numerous sample input and output files.

The human approach to enumerating spanning trees of grid graphs
In order to illustrate the advantage of "keeping it simple", we will review the human approach to the enumeration task that we will later redo using the 'Gordian knot' way. While the human approach is definitely interesting for its own sake, it is rather painful.
Our goal is to enumerate the number of spanning trees in certain families of graphs, notably grid graphs and their generalizations. Let's examine Paul Raff's interesting approach described in his paper Spanning Trees in Grid Graph [R]. Raff's approach was inspired by the pioneering work of F. J. Faase ([F]).
The goal is to find generating functions that enumerate spanning trees in grid graphs and the product of an arbitrary graph and a path or a cycle.
Grid graphs have two parameters, let's call them k and n. For a k × n grid graph, let's think of k as fixed while n is the discrete input variable of interest.
Definition The k × n grid graph G k (n) is the following graph given in terms of its vertex set V and edge set E: The main idea in the human approach is to consider the collection of set-partitions of [k] = {1, 2, . . . , k} and figure out the transition when we extend a k × n grid graph to a k × (n + 1) one.
Let B k be the collection of all set-partitions of [k]. B k = |B k | is called the k-th Bell number. Famously, the exponential generating function of B k , namely ∞ k=0 B k k! t k , equals e e t −1 .
A lexicographic ordering on B k is defined as follows: Definition Given two partitions P 1 and P 2 of [k], for i ∈ [k], let X i be the block of P 1 containing i and Y i be the block of P 2 containing i. Let j be the minimum number such that X i Y i . Then P 1 < P 2 iff 1. |P 1 | < |P 2 | or 2. |P 1 | = |P 2 | and X j ≺ Y j where ≺ denotes the normal lexicographic order. For example, here is the ordering for k = 3: For simplicity, we can rewrite it as follows: , 1/23, 12/3, 13/2, 1/2/3}.
Definition Given a spanning forest F of G k (n), the partition induced by F is obtained from the equivalence relation i ∼ j ⇐⇒ v n,i , v n, j are in the same component of F.
For example, the partition induced by any spanning tree of G k (n) is 123 . . . k because by definition, in a spanning tree, all v n,i , 1 ≤ i ≤ k are in the same component. For the other extreme, where every component only consists of one vertex, the corresponding set-partition is 1/2/3/. . . /k − 1/k because no two v n,i , v n, j are in the same component for 1 ≤ i < j ≤ k.
Definition Given a spanning forest F of G k (n) and a set-partition P of [k], we say that F is consistent with P if: 1. The number of trees in F is precisely |P|. 2. P is the partition induced by F. Let E n be the set of edges E(G k (n))\E(G k (n − 1)), then E n has 2k − 1 members. Given a forest F of G k (n − 1) and some subset X ⊆ E n , we can combine them to get a forest of G k (n) as follows. We just need to know how many subsets of E n can transfer a forest consistent with some partition to a forest consistent with another partition. This leads to the following definition: Definition Given two partitions P 1 and P 2 in B k , a subset X ⊆ E n transfers from P 1 to P 2 if a forest consistent with P 1 becomes a forest consistent with P 2 after the addition of X. In this case, we write X ⋄ P 1 = P 2 .
With the above definitions, it is natural to define a B k × B k transfer matrix A k by the following: Let's look at the k = 2 case as an example. We have For simplicity, let's call the edges in E n+1 e 1 , e 2 , e 3 . Then to transfer the set-partition P 1 = 12 to itself, we have the following three ways: {e 1 , e 2 }, {e 1 , e 3 }, {e 2 , e 3 }. In order to transfer the partition P 2 = 1/2 into P 1 , we only have one way, namely: {e 1 , e 2 , e 3 }. Similarly, there are two ways to transfer P 1 to P 2 and one way to transfer P 2 to itself Hence the transfer matrix is the following 2 × 2 matrix: Let T 1 (n), T 2 (n) be the number of forests of G k (n) which are consistent with the partitions P 1 and P 2 , respectively. Let then v n = Av n−1 .
The characteristic polynomial of A is

By the Cayley-Hamilton Theorem, A satisfies
Hence the recurrence relation for T 1 (n) is 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, . . . } (OEIS A001353) and the generating function is Similarly, for the k = 3 case, the transfer matrix The transfer matrix method can be generalized to general graphs of the form G × P n , especially cylinder graphs.
As one can see, we had to think very hard. First we had to establish a 'canonical' ordering over set-partitions, then define the consistence between partitions and forests, then look for the transfer matrix and finally worry about initial conditions. Rather than think so hard, let's compute sufficiently many terms of the enumeration sequence, and try to guess a linear recurrence equation with constant coefficients, that would be provable a posteriori just because we know that there exists a transfer matrix without worrying about finding it explicitly. But how do we generate sufficiently many terms? Luckily, we can use the celebrated Matrix Tree Theorem.

The Matrix Tree Theorem
Matrix Tree Theorem If A = (a ij ) is the adjacency matrix of an arbitrary graph G, then the number of spanning trees is equal to the determinant of any co-factor of the For instance, taking the (n, n) co-factor, we have that the number of spanning trees of G equals −a n−1,1 −a n−1,2 . . . a n−1,1 + · · · + a n−1,n .
Since computing determinants for numeric matrices is very fast, we can find the generating functions for the number of spanning trees in grid graphs and more generalized graphs by experimental methods, using the C-finite ansatz.

The GuessRec Maple procedure
Our engine is the Maple procedure GuessRec(L) that resides in the Maple packages accompanying this article. We used the 'vanilla', straightforward, linear algebra approach for guessing, using undetermined coefficients. A more efficient way is via the celebrated Berlekamp-Massey algorithm ([Wi]). Since the guessing part is not the bottle-neck of our approach ( it is rather the data-generation part), we preferred to keep it simple. Naturally, we need to collect enough data. The input is the data (given as a list) and the output is a conjectured recurrence relation derived from that data.
Procedure GuessRec(L) inputs a list, L, and attempts to output a linear recurrence equation with constant coefficients satisfied by the list. It is based on procedure GuessRec1(L,d) that looks for such a recurrence of order d.
Here is the Maple code: GuessRec1:=proc(L,d) local eq,var,a,i,n: if nops(L)<=2*d+2 then print('The list must be of size >=', 2*d+3 ): The idea is that having a long enough list L (|L| > 2d + 2) of data, we use the data after the d-th one to discover whether there exists a linear recurrence relation, the first d data points being the initial condition. With the unknowns a 1 , a 2 , . . . , a d , we have a linear systems of no less than d + 3 equations. If there is a solution, it is extremely likely that the recurrence relation holds in general. The first list of length d in the output constitutes the list of initial conditions while the second list, R, codes the linear recurrence, where [R[1], . . . R[d]] stands for the following recurrence: This procedure inputs a sequence L and tries to guess a recurrence equation with constant coefficients satisfying it. It returns the initial values and the recurrence equation as a pair of lists. Since the length of L is limited, the maximum degree of the recurrence cannot be more than ⌊|L|/2 − 2⌋. With this procedure, we just need to input L = [1,4,15,56,209,780,2911,10864,40545,151316] to get the recurrence (and initial conditions) [[1, 4] Once the recurrence relation, let's call it S, is discovered, procedure CtoR(S,t) finds the generating function for the sequence. Here is the Maple code: CtoR:=proc(S,t) local D1,i,N1,L1,f,f1,L: if not (type (S,list) and nops(S)=2 and type (S[1],list) and type (S[2],list) and nops (S[1])=nops (S[2]) and type(t, symbol) ) then print('Bad input'): Procedure SeqFromRec used above (see the package) simply generates many terms using the recurrence.
Procedure CtoR(S,t) outputs the rational function in t, whose coefficients are the members of the C-finite sequence S. For example: Briefly, the idea is that the denominator of the rational function can be easily determined by the recurrence relation and we use the initial condition to find the starting terms of the generating function, then multiply it by the denominator, yielding the numerator.

Application of GuessRec for enumerating spanning trees of grid graphs and G × P n
With the powerful procedures GuessRec and CtoR, we are able to find generating functions for the number of spanning trees of generalized graphs of the form G × P n . We will illustrate the application of GuessRec to finding the generating function for the number of spanning trees in grid graphs. First, using procedure GridMN(k,n), we get the k × n grid graph. Then, procedure SpFn uses the Matrix Tree Theorem to evaluate the determinant of the co-factor of the Laplacian matrix of the grid graph which is the number of spanning trees in this particular graph. For a fixed k, we need to generate a sufficiently long list of data for the number of spanning trees in G k (n), n ∈ [l(k), u(k)]. The lower bound l(k) can't be too small since the first several terms are the initial condition; the upper bound u(k) can't be too small as well since we need sufficient data to obtain the recurrence relation. Notice that there is a symmetry for the recurrence relation, and to take advantage of this fact, we modified GuessRec to get the more efficient GuessSymRec (requiring less data). Once the recurrence relation, and the initial conditions, are given, applying CtoR(S,t) will give the desirable generating function, that, of course, is a rational function of t. All the above is incorporated in procedure GFGridKN(k,t) which inputs a positive integer k and a symbol t, and outputs the generating function whose coefficient of t n is the number of spanning trees in G k (n), i.e. if we let s(k, n) be the number of spanning trees in G k (n), the generating function We now list the generating functions F k (t) for 1 ≤ k ≤ 7: Except for k = 7, these were already found by Raff [R] and Faase[F], but it is reassuring that, using our new approach, we got the same output. The case k = 7 seems to be new.

Theorem 1
The generating function for the number of spanning trees in G 1 (n) is: Theorem 2 The generating function for the number of spanning trees in G 2 (n) is: Theorem 3 The generating function for the number of spanning trees in G 3 (n) is:
For 5 ≤ k ≤ 7, since the formulas are too long, we present their numerators and denominators separately.
Note that, surprisingly, the degree of the denominator of F 7 (t) is 48 rather than the expected 64 since the first six generating functions' denominator have degree 2 k−1 , 1 ≤ k ≤ 6. With a larger computer, one should be able to compute F k for larger k, using this experimental approach.
Generally, for an arbitrary graph G, we consider the number of spanning trees in G × P n . With the same methodology, a list of data can be obtained empirically with which a generating function follows.

Joint Resistance
The original motivation for the Matrix Tree Theorem, first discovered by Kirchhoff (of Kirchhoff's laws fame) came from the desire to efficiently compute joint resistances in an electrical network.
Suppose one is interested in the joint resistance in an electric network in the form of a grid graph between two diagonal vertices [1, 1] and [k, n]. We assume that each edge has resistance 1 Ohm. To obtain it, all we need is, in addition for the number of spanning trees (that's the numerator), the number of spanning forests SF k (n) of the graph G k (n) that have exactly two components, each component containing exactly one of the members of the pair {[1, 1], [k, n]} (this is the denominator). The joint resistance is just the ratio.
In principle, we can apply the same method to obtain the generating function S k . Empirically, we found that the denominator of S k is always the square of the denominator of F k times another polynomial C k . Once the denominator is known, we can find the numerator in the same way as above. So our focus is to find C k .
Remark By looking at the output of our Maple package, we conjectured that R(k, n), the resistance between vertex [1, 1] and vertex [k, n] in the k × n grid graph, G k (n), where each edge is a resistor of 1 Ohm, is asymptotically n/k, for any fixed k, as n → ∞. We proved it rigorously for k ≤ 6, and we wondered whether there is a human-generated "electric proof". Naturally we emailed Peter Doyle, the coauthor of the delightful masterpiece [DS], who quickly came up with the following argument.
We thank Peter Doyle for his kind permission to reproduce this electrifying argument.

The statistic of the number of vertical edges in spanning trees of grid graphs
Often in enumerative combinatorics, the class of interest has natural 'statistics', like height, weight, and IQ for humans. Recall that the naive counting is where f := A → Z is the statistic of interest. To go from the weighted enumeration (a certain Laurent polynomial) to straight enumeration, one simply plugs-in x = 1, i.e. | A| 1 = | A|.
The scaled random variable is defined as follows. Let E( f ) and Var( f ) be the expectation and variance, respectively, of the statistic f defined on A, and define the scaled random variable, for a ∈ A, by In this section, we are interested in the statistic 'number of vertical edges', defined on spanning trees of grid graphs. For given k and n, let, as above, G k (n) denote the k × n grid-graph. Let F k,n be its set of spanning trees. If the weight is 1, then f ∈F k, n 1 = |F k,n | is the naive counting. Now let's define a natural statistic ver(T ) = the number of vertical edges in the spanning tree T , and the weight w(T ) = v ver(T ) , then the weighted counting follows: where F k,n is the set of spanning trees of G k (n). We define the bivariate generating function Ver k,n t n .
More generally, with our Maple package GFMatrix.txt, and procedure VerGF, we are able to obtain the bivariate generating function for an arbitrary graph of the form G × P n . The procedure VerGF takes inputs G (an arbitrary graph), N (an integer determining how many data we use to find the recurrence relation) and two symbols v and t.
The main tool for computing VerGF is still the Matrix Tree Theorem and GuessRec. But we need to modify the Laplacian matrix for the graph. Instead of letting a ij = −1 for i j and {i, j} ∈ E(G × P n ), we should consider whether the edge {i, j} is a vertical edge. If so, we let a i, j = −v, a j,i = −v. The diagonal elements which are (−1)× (the sum of the rest entries on the same row) should change accordingly. The following theorems are for grid graphs when 2 ≤ k ≤ 4 while k = 1 is a trivial case because there are no vertical edges.

Theorem 8
The bivariate generating function for the weighted counting according to the number of vertical edges of spanning trees in G 2 (n) is: Theorem 9 The bivariate generating function for the weighted counting according to the number of vertical edges vertical edges of spanning trees in G 3 (n) is: Theorem 10 The bivariate generating function for the weighted counting according to the number of vertical edges of spanning trees in G 4 (n) is: With the Maple package BiVariateMoms.txt and its Story procedure from http://sites.math.rutgers.edu/˜zeilberg/tokhniot/BiVariateMoms.txt, the expectation, variance and higher moments can be easily analyzed. We calculated up to the 4th moment for G 2 (n). For k = 3, 4, you can find the output files from http://sites.math.rutgers.edu/˜yao/OutputStatisticVerticalk=3.txt http://sites.math.rutgers.edu/˜yao/OutputStatisticVerticalk=4.txt

Theorem 11
The moments of the statistic: the number of vertical edges in the spanning trees of G 2 (n) are as follows: Let b be the largest positive root of the polynomial equation b 2 − 4b + 1 = 0 whose floating-point approximation is 3.732050808, then the size of the n-th family (i.e. straight enumeration) is very close to The average of the statistics is, asymptotically The variance of the statistics is, asymptotically The skewness of the statistics is, asymptotically The kurtosis of the statistics is, asymptotically

Application of the C-finite Ansatz to computing generating functions of determinants (and permanents) of almost-diagonal Toeplitz matrices
So far, we have seen applications of the C-finite ansatz methodology for automatically computing generating functions for enumerating spanning trees/forests for certain infinite families of graphs. The second case study is completely different, and in a sense more general, since the former framework may be subsumed in this new context.
Definition Diagonal matrices A are square matrices in which the entries outside the main diagonal are 0, i.e. a ij = 0 if i j.
Definition An almost-diagonal Toeplitz matrix A is a square matrices in which a i, j = 0 if j − i ≥ k 1 or i − j ≥ k 2 for some fixed positive integers k 1 , k 2 and For simplicity, we use the notation L =[n, [the first k 1 entries in the first row], [the first k 2 entries in the first column]] to denote the n×n matrix with these specifications. Note that this notation already contains all information we need to reconstruct this matrix. For example, [6, [1,2,3], [1,4]] is the matrix The following is the Maple procedure DiagMatrixL (in our Maple package GFMatrix.txt), which inputs such a list L and outputs the corresponding matrix. For this matrix, k 1 = 3 and k 2 = 2. Let k 1 , k 2 be fixed and M 1 , M 2 be two lists of numbers or symbols of length k 1 and k 2 respectively, A k is the almost-diagonal Toeplitz matrix represented by the list L k = [k, M 1 , M 2 ]. Note that the first elements in the lists M 1 and M 2 must be identical.
Having fixed two lists M 1 of length k 1 and M 2 of length k 2 , (where M 1 [1] = M 2 [1]), it is of interest to derive automatically, the generating function (that is always a rational function for reasons that will soon become clear), ∞ k=0 a k t k , where a k denotes the determinant of the k × k almost-diagonal Toeplitz matrix whose first row starts with M 1 , and first column starts with M 2 . Analogously, it is also of interest to do the analogous problem when the determinant is replaced by the permanent.
Here is the Maple procedure GFfamilyDet which takes inputs (i) A: a name of a Maple procedure that inputs an integer n and outputs an n × n matrix according to some rule, e.g., the almost-diagonal Toeplitz matrices, (ii) a variable name t, (iii) two integers m and n which are the lower and upper bounds of the sequence of determinants we consider. It outputs a rational function in t, say R(t), which is the generating function of the sequence. Then GFfamilyDet(SampleB, t, 10, 50) will return the generating function − 1 45 t 3 − 12 t 2 + 2 t − 1 .
It turns out, that for this problem, the more 'conceptual' approach of setting up a transfer matrix also works well. But don't worry, the computer can do the 'research' all by itself, with only a minimum amount of human pre-processing.
We will now describe this more conceptual approach, that may be called symbolic dynamical programming, where the computer sets up, automatically, a finite-state scheme, by dynamically discovering the set of states, and automatically figures out the transfer matrix.

The Transfer Matrix method for almost-diagonal Toeplitz matrices
Recall from Linear Algebra 101, the Cofactor Expansion Let | A| denote the determinant of an n × n matrix A, then where M ij is the (i, j)-minor.
We'd like to consider the Cofactor Expansion for almost-diagonal Toeplitz matrices along the first row. For simplicity, we assume while a i, j = 0 if j − i ≥ k 1 or i − j ≥ k 2 for some fixed positive integers k 1 , k 2 , and if −k 2 < j 1 − i 1 < j 2 − i 2 < k 1 , then a i 1 j 1 a i 2 j 2 . Under this assumption, for any minors we obtain through recursive Cofactor Expansion along the first row, the dimension, the first row and the first column should provide enough information to reconstruct the matrix. Our goal in this section is the same as the last one, to get a generating function for the determinant or permanent of almost-diagonal Toeplitz matrices A k with dimension k. Once we have those almost-diagonal Toeplitz matrices, the first step is to do a one-step expansion as follows: ExpandMatrixL:=proc(L,L1) local n,R,C,dim,R1,C1,i,r, S,candidate,newrow,newcol,gu,mu,temp,p,q We would like to generate all the "children" of an almost-diagonal Toeplitz matrix regardless of the dimension, i.e., two lists L represent the same child as long as their first_rows and first_columns are the same, respectively. The set of "children" is the scheme of the almost diagonal Toeplitz matrices in this case.
The following is the Maple procedure ChildrenMatrixL which inputs a data structure L and outputs the set of its "children" under Cofactor Expansion along the first row: After we have the scheme S, by the Cofactor Expansion of any element in the scheme, a system of algebraic equations follows. For children in S, it's convenient to let the almost-diagonal Toeplitz matrix be the first one C 1 and for the rest, any arbitrary ordering will do. For example, if after Cofactor Expansion for C 1 , c 2 "copies" of C 2 and c 3 "copies" of C 3 are obtained, then the equation will be C 1 = 1 + c 2 tC 2 + c 3 tC 3 .
However, if the above equation is for C i , i 1, i.e. C i is not the almost-diagonal Toeplitz matrix itself, then the equation will be slightly different: Here t is a symbol as we assume the generating function is a rational function of t.
Compared to empirical approach, the 'symbolic dynamical programming' method is faster and more efficient for the moderate-size examples that we tried out. However, as the lists will grow larger, it is likely that the former method will win out, since with this non-guessing approach, it is equally fast to get generating functions for determinants and permanents, and as we all know, permanents are hard. The advantage of the present method is that it is more appealing to humans, and does not require any 'meta-level' act of faith. However, both methods are very versatile and are great experimental approaches for enumerative combinatorics problems. We hope that our readers will find other applications.

Summary
Rather than trying to tackle each enumeration problem, one at a time, using ad hoc human ingenuity each time, building up an intricate transfer matrix, and only using the computer at the end as a symbolic calculator, it is a much better use of our beloved silicon servants (soon to become our masters!) to replace 'thinking' by 'metathinking', i.e. develop experimental mathematics methods that can handle many different types of problems. In the two case studies discussed here, everything was made rigorous, but if one can make semi-rigorous and even non-rigorous discoveries, as long as they are interesting, one should not be hung up on rigorous proofs. In other words, if you can find a rigorous justification (like in these two case studies) that's nice, but if you can't, that's also nice!