# Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction-based approach

Frédéric Chyzak, Marni Mishna

► To cite this version:

Frédéric Chyzak, Marni Mishna. Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction-based approach. 2024. hal-04604501

HAL Id: hal-04604501

https://inria.hal.science/hal-04604501

Preprint submitted on 7 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License
# Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction-based approach

Frédéric Chyzak, Marni Mishna

► To cite this version:

Frédéric Chyzak, Marni Mishna. Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction-based approach. 2025. hal-04604501v3

HAL Id: hal-04604501

https://inria.hal.science/hal-04604501v3

Preprint submitted on 27 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# DIFFERENTIAL EQUATIONS SATISFIED BY GENERATING FUNCTIONS OF 5-, 6-, AND 7-REGULAR LABELLED GRAPHS: A REDUCTION-BASED APPROACH

FRÉDÉRIC CHYZAK

Inria, France

MARNI MISHNA

Simon Fraser University, Canada

**ABSTRACT.** By a classic result of Gessel, the exponential generating functions for $k$-regular graphs are D-finite. Using Gröbner bases in Weyl algebras, we compute the linear differential equations satisfied by the generating function for 5-, 6-, and 7- regular graphs. The method is sufficiently robust to consider variants such as graphs with multiple edges, loops, and graphs whose degrees are limited to fixed sets of values.

*Keywords:* regular graph, enumeration, Weyl algebra, reduction-based integration.

2020 MSC: 05C30, 12H05.

## 1. INTRODUCTION

1.1. **The history of $k$-regular graph enumeration.** A graph is said to be *regular* if every vertex is incident to the same number of edges, that is, each vertex has the same degree. If that degree is $k$, we call the graph $k$-regular. One of the earliest graph enumeration problems considered was the number of non-isomorphic unlabelled $k$-regular graphs on $n$ vertices. It is a relatively attainable problem for many reasons, including the fact that the number of edges is fixed in these graphs, which yields a significant simplification. For example, according to Gropp [7], Jan de Vries determined the number of non-isomorphic cubic (3-regular) graphs up to 10 vertices, and shared them in a letter to Vittorio Martinetti, which was eventually published in a journal in 1891. The proofs were descriptions of the graphs. Here we consider the slightly easier problem of labelled graphs, specifically the number of labelled $k$-regular graphs on $n$ vertices, which we denote by $r_n^{(k)}$.

In the labelled case, the work of Read in the 1950s established enumeration formulas using the cycle index series, a relatively new machinery at the time. He gives a compact, structural equation in [11, Eq. 5.11] that is not immediately suitable for enumeration purposes for $k > 3$. He notes,

> "It may readily be seen that to evaluate the above expressions in particular cases may involve an inordinate amount of computation."

For $k = 3$, the equation is sufficiently manageable to give rise to a nice asymptotic formula.

One can distill from his work a formula in terms of coefficient extraction of a multivariable polynomial. This is the starting point of most modern approaches as it is easy to interpret, and there are numerous possibilities for analysis. We can write

$$ (1) \qquad r_n^{(k)} = [x_1^k x_2^k \dots x_n^k] \prod_{1 \le i < j \le n} (1 + x_i x_j). $$

<footnote>E-mail addresses: frederic.chyzak@inria.fr, mmishna@sfu.ca.</footnote>

<footnote>Date: June 5, 2024.</footnote>
# DIFFERENTIAL EQUATIONS SATISFIED BY GENERATING FUNCTIONS OF 5-, 6-, AND 7-REGULAR LABELLED GRAPHS: A REDUCTION-BASED APPROACH

FRÉDÉRIC CHYZAK

Inria, France

MARNI MISHNA

Simon Fraser University, Canada

**ABSTRACT.** By a classic result of Gessel, the exponential generating functions for $k$-regular graphs are D-finite. Using Gröbner bases in Weyl algebras, we compute the linear differential equations satisfied by the generating function for 5-, 6-, and 7- regular graphs. The method is sufficiently robust to consider variants such as graphs with multiple edges, loops, and graphs whose degrees are limited to fixed sets of values.

**Keywords:** regular graph, enumeration, Weyl algebra, reduction-based integration.

**2020 MSC:** 05C30, 12H05.

## 1. INTRODUCTION

1.1. **A short history of $k$-regular graph enumeration.** A graph is said to be *regular* if every vertex is incident to the same number of edges, that is, each vertex has the same degree. If that degree is $k$, we call the graph $k$-regular. One of the earliest graph enumeration problems considered was the number of non-isomorphic unlabelled $k$-regular graphs on $n$ vertices. It is a relatively attainable problem for many reasons, including the fact that the number of edges is fixed in these graphs, which yields a significant simplification. For example, according to Gropp [7], Jan de Vries determined the number of non-isomorphic cubic (3-regular) graphs up to 10 vertices, and shared them in a letter to Vittorio Martinetti, which was eventually published in a journal in 1891. The proofs were descriptions of the graphs. Here we consider the slightly easier problem of labelled graphs, specifically the number of labelled $k$-regular graphs on $n$ vertices, which we denote by $r_n^{(k)}$.

In the labelled case, the work of Read in the 1950s established enumeration formulas using the cycle index series, a relatively new machinery at the time. He gives a compact, structural equation in [13, Eq. 5.11] that is not immediately suitable for enumeration purposes for $k > 3$. He notes,

> "It may readily be seen that to evaluate the above expressions in particular cases may involve an inordinate amount of computation."

For $k = 3$, the equation is sufficiently manageable to give rise to a nice asymptotic formula.

One can distill from his work a formula in terms of coefficient extraction of a multivariable polynomial. This is the starting point of most modern approaches as it is easy to interpret, and there are numerous possibilities for analysis. Using the notation of square brackets to isolate the coefficient of the indicated term in a series expansion of the product we can write

$$ (1) \qquad r_n^{(k)} = [x_1^k x_2^k \dots x_n^k] \prod_{1 \le i < j \le n} (1 + x_i x_j). $$

<footnote>E-mail addresses: frederic.chyzak@inria.fr, mmishna@sfu.ca.</footnote>

<footnote>Date: June 27, 2025.</footnote>
The square brackets indicate that the answer is the coefficient of the indicated term in a series expansion of the product. The multiplication accounts for all possibilities of an edge {$i, j$} to be in the graph or not. The coefficient of the indicated monomial is the number of graphs that have vertices 1 to $n$, such that each vertex is incident to exactly $k$ other vertices: this is precisely $r_n^{(k)}$.

To approximate $r_n^{(k)}$, one could write the coefficient extraction as a Cauchy integral, and then estimate the integral. Remarkably, a sufficiently refined analysis succeeds even when $k$ is given as a non-constant function of $n$, and can also be adapted to examine other kinds of degree sequences. Wormald's 2018 ICM survey has many details on the state of asymptotic enumeration of regular graphs and related objects [14].

In this 2018 survey, Wormald notes that no new exact enumeration results have appeared since the recurrences for 4-regular graphs published in the early 1980s. The entry point of the present article is also Eq. (1), but we follow a different lineage to contribute fixed-length linear recurrence formulas to count 5-, 6-, and 7-regular graphs, ending the drought.

The fact that there are recurrences to find at all is related to a question of Stanley [13] in his foundational article on P-recursive sequences. The existence of a recurrence is equivalent to asking whether or not the exponential generating function for $r_n^{(k)}$, defined as $R^{(k)}(t) := \sum_{n \ge 0} r_n^{(k)} \frac{t^n}{n!}$, is D-finite. In other words, does $R^{(k)}(t)$ satisfy a linear differential equation with polynomial coefficients? Read had already given a recurrence for 3-regular graphs, and about the same time McKay and Wormald used a combinatorial analysis to produce recurrences for 4-regular graphs. Goulden, Jackson and Reilly [6] were also able to determine explicit linear differential equations satisfied by $R^{(3)}(t)$ and $R^{(4)}$ using tools that dated back to MacMahon at the turn of the 20th century, called Hammond operators. But, they noted that<fnref n="1" />

> "... the H-series theorem enables us to write down the system of partial differential equations for the H-series for arbitrary $p$ without difficulty. However, the reduction of this system to a single ordinary differential equation in $y_p$ is a technical task which we are unable to carry out for the general case."

Their work fuelled speculation that $R^{(k)}$ should be D-finite for all $k$. Gessel compared their approach to his own method the scalar product of symmetric functions and algebraic substitutions [4]:

> "... Hammond operators are undesirable for two reasons. First, they disguise the symmetry of the scalar product. Second, they can be represented as differential operators. Although this might seem like an advantage, it seems to be of little use, but misleads by directing attention in the wrong direction."

Instead of working with differential equations, he recast the extraction in terms of symmetric functions, and used algebraic arguments to establish that indeed $R^{(k)}(t)$ is D-finite for all $k$. His framework is sufficiently simple and robust that it can be used to establish the D-finiteness of many related regular graph and hypergraph cases. Gessel was able to advance on the general case thanks to concurrent work on multivariable P-recursiveness of Lipshitz [8]. The work of Lipshitz was not sufficiently straightforward to convert into an algorithm or even make computation effective beyond $k = 2$. It was over a decade before the computer algebra implementations using differential operators caught up to his theoretical results. In our 2005 work with Salvy [3], we made both the Hammond method and the Gessel strategy effective for any $k$ using Gröbner bases for D-modules and non-commutative polynomial elimination, in a sort of variant of Creative Telescoping. Our implementation quickly found differential equations up to, and including, 4-regular objects. The growth of data in the skew polynomial elimination involved in the 5-regular graph case requires computational resources that even today are insufficient to have the algorithm terminate. However, in the intervening 20 years, improvements and insights to Creative Telescoping have led us to an evolved algorithm that terminates also in practice, and indeed we could find the linear differential equations satisfied by $R^{(5)}(t)$, $R^{(6)}(t)$, and $R^{(7)}(t)$. Our present approach can be applied to find the differential equations satisfied by the other graph, hypergraph and graph-like classes, but for higher degrees of regularity than were previously obtained [9, 10].

## 1.2. The scalar product<fnref n="2" /> of symmetric functions.
The coefficient extraction in Eq. (1) can be placed into an infinite product, symmetric in all variables, which can be readily encoded in terms of symmetric

<footnote n="1">¹In our notation, $p = k$ and $y_p = R^{(k)}$.</footnote>

<footnote n="2">²We follow the usual terminology of a "scalar product" in combinatorics, although the presence of a formal indeterminate $t$ would require to speak more properly of a "pairing".</footnote>
The multiplication accounts for all possibilities of an edge {$i, j$} to be in the graph or not. The coefficient of the indicated monomial is the number of graphs that have vertices 1 to $n$, such that each vertex is incident to exactly $k$ other vertices: this is precisely $r_n^{(k)}$.

There are a variety of strategies to consider for this construction, and other direct arguments in the service of asymptotic enumeration. The problem is well studied, remarkably even for problems with $k$ a function of $n$. Wormald’s 2018 ICM survey has many details on the state of asymptotic enumeration of regular graphs and related objects [18].

In that 2018 survey, Wormald notes that no new exact enumeration results have appeared since the recurrences for 4-regular graphs published in the early 1980s. The entry point of the present article is also Eq. (1), but we follow a different lineage to contribute fixed-length linear recurrence formulas to count 5-, 6-, and 7-regular graphs, ending the drought.

The fact that there are recurrences to find at all is related to a question of Stanley [16] in his foundational article on P-recursive sequences. The existence of a recurrence is equivalent to asking whether or not the exponential generating function for $r_n^{(k)}$, defined as $R^{(k)}(t) := \sum_{n \ge 0} r_n^{(k)} \frac{t^n}{n!}$, is D-finite. In other words, does $R^{(k)}(t)$ satisfy a linear differential equation with polynomial coefficients? Read had already given a recurrence for 3-regular graphs in his PhD thesis [15], and Read and Wormald used a combinatorial analysis to produce recurrences for 4-regular graphs [14]. Goulden, Jackson and Reilly [6] were also able to determine explicit linear differential equations satisfied by $R^{(3)}(t)$ and $R^{(4)}$ using tools that dated back to MacMahon at the turn of the 20th century, called Hammond operators. But, they noted that<fnref n="1" />

> “... the H-series theorem enables us to write down the system of partial differential equations for the H-series for arbitrary $p$ without difficulty. However, the reduction of this system to a single ordinary differential equation in $y_p$ is a technical task which we are unable to carry out for the general case.”

Their work fuelled speculation that $R^{(k)}$ should be D-finite for all $k$. Gessel compared their approach to his own method by the scalar product of symmetric functions and algebraic substitutions [4]:

> “... Hammond operators are undesirable for two reasons. First, they disguise the symmetry of the scalar product. Second, they can be represented as differential operators. Although this might seem like an advantage, it seems to be of little use, but misleads by directing attention in the wrong direction.”

Instead of working with differential equations, he recast the extraction in terms of symmetric functions, and used algebraic arguments to establish that indeed $R^{(k)}(t)$ is D-finite for all $k$. His framework is sufficiently simple and robust that it can be used to establish the D-finiteness of many related regular graph and hypergraph cases. Gessel was able to advance on the general case thanks to concurrent work on multivariable P-recursiveness of Lipshitz [8]. The work of Lipshitz was not sufficiently straightforward to convert into an algorithm or even make computation effective beyond $k = 2$. It was over a decade before the computer algebra implementations using differential operators caught up to his theoretical results. In 2005 Chyzak, Mishna and Salvy [3] made both the Hammond method and the Gessel strategy effective for any $k$ using Gröbner bases for D-modules and non-commutative polynomial elimination, in a sort of variant of Creative Telescoping, a method for symbolic integration. The implementation quickly found differential equations up to, and including, 4-regular objects. The growth of data in the skew polynomial elimination involved in the 5-regular graph case requires computational resources that even today are insufficient to have the algorithm terminate. However, in the intervening 20 years, there have been remarkable improvements and insights to Creative Telescoping. This lead us to an evolved algorithm that terminates also in practice, and indeed we could find the linear differential equations satisfied by $R^{(5)}(t)$, $R^{(6)}(t)$, and $R^{(7)}(t)$. Our present approach can be applied to find the differential equations satisfied by the other graph, hypergraph and graph-like classes for higher degrees of regularity than were previously obtained [10, 11].

The following theorem is the main result of this article. It appears below, rephrased, as Corollary 12(1).

**Theorem 1.** For each graph model in Table 2, there exists a known linear differential equation with polynomial coefficients satisfied by the exponential generating function, with explicit order given by column $\partial_t$ of the table, and maximum coefficient degree given by column $t$ of the table.

<footnote n="1">¹In our notation, $p = k$ and $y_p = R^{(k)}$.</footnote>
functions. The set up of Gessel [5] uses the scalar product in the ring of symmetric functions to model the extraction. Describing the method requires a small detour through symmetric function terminology and basics. There are many excellent introductions. We highlight some notation, but refer readers to Sagan [12] for details.

We say $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_k)$ such that $\sum_{i=1}^k \lambda_i = n$ and $\lambda_i \ge \lambda_{i+1}$ is a partition of $n$ into $k$ parts, and write $\lambda \vdash n$ to indicate that $\lambda$ is a partition of $n$. The monomial symmetric function is defined $m_\lambda(x) := \sum_{\alpha \sim \lambda} x^\alpha$ where $\alpha \sim \lambda$ if the non-zero parts of $\alpha$ are a rearrangement of the parts of $\lambda$. Using $m_\lambda$ we can describe the complete homogeneous symmetric function $h_n := \sum_{\lambda \vdash n} m_\lambda$ and the power sum symmetric function $p_n := m_{(n)} = x_1^n + x_2^n + \dots$. Products are denoted respectively $h_{n_1 n_2 \dots n_\ell} := h_{n_1} h_{n_2} \dots h_{n_\ell}$ and $p_{n_1 n_2 \dots n_\ell} := p_{n_1} p_{n_2} \dots p_{n_\ell}$. The vector space of symmetric functions of order $n$ has numerous bases, including $\{m_\lambda | \lambda \vdash n\}$, $\{h_\lambda | \lambda \vdash n\}$ and $\{p_\lambda | \lambda \vdash n\}$. For any $\lambda \vdash n$, $z_\lambda$ denotes the number

$$ (2) \qquad z_\lambda := 1^{r_1} r_1! 2^{r_2} r_2! \dots n^{r_n} r_n! $$

provided $\lambda$ has $r_1$ ones, $r_2$ twos, etc, and we set $\delta_{\lambda,\nu}$ to 1 if $\lambda = \nu$ and to 0 otherwise. The scalar product of symmetric functions is classically defined by

$$ (3) \qquad \langle p_\lambda, p_\nu \rangle := \delta_{\lambda,\nu} z_\lambda, \quad \text{from which we deduce } \langle m_\lambda, h_\nu \rangle = \delta_{\lambda,\nu}. $$

The connection to the graph enumeration problem is as follows. We can extract the coefficient of a particular monomial in a symmetric function with a judiciously chosen scalar product. Write $\mathbf{G} := \prod_{i<j} (1+x_i x_j)$ and consider an example. Since $r_4^{(3)} = [x_1^3 x_2^3 x_3^3 x_4^3] \mathbf{G}$, to actually compute this write $\mathbf{G}$ as a sum of monomial symmetric functions, and determine the coefficient of $m_{3,3,3,3}$ (which is the only basis element to contain the term $x_1^3 x_2^3 x_3^3 x_4^3$). This coefficient is precisely the result of the scalar product $\langle \mathbf{G}, h_{3,3,3,3} \rangle = \langle \mathbf{G}, h_3^4 \rangle$.

From the formula $\log(1+u) = \sum_{k \ge 1} (-1)^{k+1} u^k/k$ it follows

$$ \begin{aligned} \mathbf{G} &= \exp \left( \log \prod_{i<j} (1+x_i x_j) \right) = \exp \left( \sum_{i<j} \log(1+x_i x_j) \right) \\ &= \exp \left( \sum_{i<j} \sum_{k \ge 1} (-1)^{k+1} \frac{x_i^k x_j^k}{k} \right) = \exp \left( \sum_{k \ge 1} (-1)^{k+1} \frac{p_k^2 - p_{2k}}{2k} \right). \end{aligned} $$

Henceforth we will only work with the power sum basis, specifically, we work in a ring generated by $t$ and a finite number of the $p_i$ variables. To continue the example, to determine $R^{(3)}(t)$ we first write $h_3 = \frac{p_3}{3} + \frac{p_2 p_1}{2} + \frac{p_1^3}{6}$, and thus obtain the following expression for the generating function:

$$ (4) \qquad R^{(3)}(t) = \left\langle \mathbf{G}, \sum_{n \ge 0} h_3^n \frac{t^n}{n!} \right\rangle = \left\langle \exp \left( \sum_{k \ge 1} (-1)^{k+1} \frac{p_k^2 - p_{2k}}{2k} \right), \exp \left( \left( \frac{p_3}{3} + \frac{p_2 p_1}{2} + \frac{p_1^3}{6} \right) t \right) \right\rangle. $$

Since the second argument has only $p_1, p_2, p_3$, all terms with other $p_i$ contribute 0:

$$ (5) \qquad R^{(3)}(t) = \left\langle \exp \left( \frac{p_1^2}{2} - \frac{p_2}{2} - \frac{p_2}{4} + \frac{p_3}{6} \right), \exp \left( \left( \frac{p_3}{3} + \frac{p_2 p_1}{2} + \frac{p_1^3}{6} \right) t \right) \right\rangle. $$

For future reference, we note the following formula, which leads to generalizations of Eqs. (4) and (5):

$$ (6) \qquad R^{(k)}(t) = \left\langle \mathbf{G}, \sum_{n \ge 0} h_k^n \frac{t^n}{n!} \right\rangle = \langle \mathbf{G}, \exp(h_k t) \rangle. $$

### 1.3. Earlier computational approaches.
As we mentioned above, Gessel [5] proved the existence of linear differential equations for scalar products like Eq. (6), and our earlier work [3] proposed algorithms to compute them. In there, for a given series $S$ in the variables $p_1, \dots, p_k$ we consider the set, denoted ann $S$, of all linear differential operators that annihilate $S$. The elements of ann $S$ are non-commutative polynomials in the variables $p_1, \dots, p_k$ and in the corresponding derivatives $\partial_1, \dots, \partial_k$; they possess a well-defined total degree in the $2k$ variables. The set ann $S$ is closed under multiplication by any operator on the left and is thus a left ideal. As is customary in effective literature, such a left ideal is best represented by a non-commutative analogue of a Gröbner basis, that is, by a finite set of non-commutative polynomials that can algorithmically
The graph models in the table include those with

(1) only simple edges permitted (denoted ‘se’ in the table) or multiple edges allowed (denoted ‘me’);

(2) loops forbidden ('ll'), loops allowed and contributing 2 to vertex degrees ('la'), or loops allowed and contributing 1 to vertex degrees ('lh');

(3) degrees restricted to some finite set, including: $\{k\}$ for $2 \le k \le 7$, $\{1, \dots, k\}$ for $2 \le k \le 6$, and $\{k, \ell\}$ for $2 \le k < \ell \le 6$, among others.

In particular, the order of the linear differential equation for simple, loopless k-regular graphs (coded ‘se’ and ‘ll’) is summarized in the table:

$$ \begin{array}{c|ccccccc} k & 2 & 3 & 4 & 5 & 6 & 7 \\ \text{order} & 1 & 2 & 2 & 6 & 6 & 20. \end{array} $$

## 1.2. The scalar product<fnref n="2" /> of symmetric functions.
The coefficient extraction in Eq. (1) can be placed into an infinite product, symmetric in all variables, which can be readily encoded in terms of symmetric functions. The set up of Gessel [5] uses the scalar product in the ring of symmetric functions to model the extraction. Describing the method requires a small detour through symmetric function terminology and basics. There are many excellent introductions. We highlight some notation, but refer readers to Stanley [17, Chapter 7] for details.

We say $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_q)$ such that $\sum_{i=1}^q \lambda_i = n$ and $\lambda_i \ge \lambda_{i+1}$ is a partition of $n$ into $q$ parts, and write $\lambda \vdash n$ to indicate that $\lambda$ is a partition of $n$. The monomial symmetric function is defined as $m_\lambda := \sum_{\alpha \sim \lambda} x^\alpha$ where $\alpha \sim \lambda$ if the non-zero entries of $\alpha$ are a rearrangement of the parts of $\lambda$. Using $m_\lambda$ we can describe the complete homogeneous symmetric function $h_n := \sum_{\lambda \vdash n} m_\lambda$ and the power-sum symmetric function $p_n := m_{(n)} = x_1^n + x_2^n + \dots$. Products are denoted respectively $h_{n_1 n_2 \dots n_\ell} := h_{n_1} h_{n_2} \dots h_{n_\ell}$ and $p_{n_1 n_2 \dots n_\ell} := p_{n_1} p_{n_2} \dots p_{n_\ell}$. The vector space of symmetric functions of order $n$ has numerous bases, including $\{m_\lambda | \lambda \vdash n\}$, $\{h_\lambda | \lambda \vdash n\}$ and $\{p_\lambda | \lambda \vdash n\}$. For any $\lambda \vdash n$, $z_\lambda$ denotes the number

$$ (2) \qquad z_\lambda := 1^{r_1} r_1! 2^{r_2} r_2! \dots n^{r_n} r_n! $$

provided $\lambda$ has $r_1$ ones, $r_2$ twos, etc. We set $\delta_{\lambda=\nu}$ to 1 if $\lambda = \nu$ is true and to 0 otherwise. The scalar product of symmetric functions is classically defined by

$$ (3) \qquad \langle p_{\lambda}, p_{\nu} \rangle := \delta_{\lambda=\nu} z_{\lambda}, \quad \text{from which we deduce} \quad \langle m_{\lambda}, h_{\nu} \rangle = \delta_{\lambda=\nu}. $$

The connection to the graph enumeration problem is as follows. We can extract the coefficient of a particular monomial in a symmetric function with a judiciously chosen scalar product. Write $\bar{F} := \prod_{i<j} (1+x_ix_j)$ and consider an example. This product is fundamental in the study of symmetric functions, particularly its expression in the various bases. Now, since $r_4^{(3)} = [x_1^3 x_2^3 x_3^3 x_4^3] \bar{F}$, to actually compute this write $\bar{F}$ as a sum of monomial symmetric functions, and determine the coefficient of $m_{3,3,3,3}$ (which is the only basis element to contain the term $x_1^3 x_2^3 x_3^3 x_4^3$). As the monomial and complete homogenous bases are orthogonal under the usual scalar product of symmetric functions, this coefficient is precisely $\langle \bar{F}, h_{3,3,3,3} \rangle = \langle \bar{F}, h_3^4 \rangle$.

From the formulas $\log(1+u) = \sum_{k \ge 1} (-1)^{k+1} u^k / k$ and $2 \sum_{i<j} x_i^k x_j^k = \sum_{i,j} x_i^k x_j^k - \sum_i x_i^{2k}$ it follows

$$ (4) \qquad \bar{F} = \exp \left( \sum_{i<j} \log(1+x_ix_j) \right) = \exp \left( \sum_{i<j} \sum_{k \ge 1} (-1)^{k+1} \frac{x_i^k x_j^k}{k} \right) = \exp \left( \sum_{k \ge 1} (-1)^{k+1} \frac{p_k^2 - p_{2k}}{2k} \right). $$

Henceforth we will only work with the power-sum basis, specifically, we work in a ring generated by $t$ and a finite number of the $p_i$ variables. To continue the example, to determine $R^{(3)}(t)$ we first write $h_3 = \frac{p_3}{3} + \frac{p_2p_1}{2} + \frac{p_1^3}{6}$, and thus obtain the following expression for the generating function:

$$ (5) \qquad R^{(3)}(t) = \left\langle \bar{F}, \sum_{n \ge 0} h_3^n \frac{t^n}{n!} \right\rangle = \left\langle \exp \left( \sum_{k \ge 1} (-1)^{k+1} \frac{p_k^2 - p_{2k}}{2k} \right), \exp \left( \left( \frac{p_3}{3} + \frac{p_2p_1}{2} + \frac{p_1^3}{6} \right) t \right) \right\rangle. $$

Since the second argument has only $p_1, p_2, p_3$, all terms with other $p_i$ contribute 0:

$$ (6) \qquad R^{(3)}(t) = \left\langle \exp \left( \frac{p_1^2}{2} - \frac{p_2}{2} - \frac{p_2^2}{4} + \frac{p_3^2}{6} \right), \exp \left( \left( \frac{p_3}{3} + \frac{p_2p_1}{2} + \frac{p_1^3}{6} \right) t \right) \right\rangle. $$

<footnote n="2">²We follow the usual terminology of a “scalar product” in combinatorics, although the presence of a formal indeterminate $t$ would require to speak more properly of a “pairing”.</footnote>
divide a given ideal element, resulting into a uniquely defined remainder that is zero if and only if the given polynomial is in the ideal.

Given a number $k$, we henceforth write $p = (p_1, \dots, p_k)$ and $\partial = (\partial_1, \dots, \partial_k)$. Given a series $F$ in $p$ and a series $G$ in $(t, p)$, we showed in [3] that differential equations with respect to $t$ satisfied by the scalar product $\langle F, G \rangle$ are to be found as those elements free of $(p, \partial)$ in the (vector space) sum of the left ideal $\text{ann } G$ and of the right ideal $(\text{ann } F)^{\dagger}$ obtained by taking the adjoints of all elements in $\text{ann } F$. A first algorithm in [3], based on linear algebra, consists: (i) in fixing an integer $d$; (ii) in determining representatives of $(\text{ann } F)^{\dagger}$ and $\text{ann } G$ for each possible leading monomial of total degree at most $d$ with respect to $(p, \partial, \partial_t)$; (iii) and in using a non-commutative variant of Gaussian elimination over $\mathbb{Q}(t)$ to eliminate $(p, \partial)$, repeating the whole process with a larger $d$ if elimination results in no non-trivial output. Because there are $\binom{d}{2k+1} = O(d^{2k+1})$ monomials of degree at most $d$, and almost as many representatives to determine for each ideal, this process is very inefficient in practice. A second algorithm in [3] is tailored to a certain form for the argument $G$ in the scalar product: if $G = \exp(h_k t)$, the theory of Hammond series, as developed in [6], provides the formula

$$ \langle F, \exp(h_k t_k) \rangle = \mathcal{H}(F)(0, \dots, 0, t_k), $$

where $\mathcal{H}(F)(t_1, \dots, t_k)$ is a transform of $F$ known as its Hammond series. A simple replacement of the $p_i$ and the $\partial_i$ in $\text{ann } F$ with suitable polynomials in $t_1, \dots, t_k$ and corresponding derivatives $\partial_{t_i}$ provides $\text{ann } \mathcal{H}(F)$. The specialization of $t_1, \dots, t_{k-1}$ to 0 is then obtained by restriction, an operation dual to integration. One way to implement it would have been to first eliminate the $k-1$ variables $\partial_{t_1}, \dots, \partial_{t_{k-1}}$, e.g., by a Gröbner basis calculation, before setting all of the $k-1$ variables $t_1, \dots, t_{k-1}$ to zero and taking a generator of the resulting principal ideal in $\mathbb{Q}(t_k)\langle \partial_{t_k} \rangle$. But a simultaneous elimination in this way leads to high degrees and is also inefficient in practice. More generally, in the 2000s, no good algorithm was known for integration with respect to several variables considered simultaneously, so one had to resort to iterated integrations, one variable after the other. Correspondingly, for multiple restriction one had to perform specializations one variable after the other, and this is what we proposed in [3], in a way that is reminiscent of elimination by successive resultants. This approach, too, fails for $k=5$: all steps are fast until the last elimination, which should eliminate $\partial_{t_1}$ from two degree-9 polynomials in the four variables $t_1, t_5, \partial_{t_1}, \partial_{t_5}$, and this fails in practice.

In both old approaches, the culprit is elimination in too many variables: eliminating $2k$ variables between polynomials in $2k+1$ variables over $\mathbb{Q}(t)$ in the first approach; eliminating $k-1$ variables between polynomials in $2k-1$ variables over $\mathbb{Q}(t_k)$ in the second approach. The second is an improvement in that it reduces the number of variables, and this is assisted by specializations to zero along the process.

A turning point in the theory of Creative Telescoping was the introduction of reduction-based algorithms, starting with the integration of bivariate rational functions [1] in 2010, and followed by many articles in the literature. Our inspiration for the present work came from a more recent reduction-based algorithm [2] for the integration with regard to one variable $p$ of general D-finite functions $f(t, p)$, leading to integrals parametrized by $t$. In a nutshell, reduction-based algorithms: (i) set up a reduction process that corresponds to simplifying a function to be integrated modulo derivatives with respect to $p$ of other functions, in such a way that the resulting remainder lies in a finite-dimensional vector space; (ii) find a linear relation between the remainders of successive higher-order derivatives with respect to the parameter $t$ of the function to be integrated. In situations where integrals of derivatives are zero, the output linear relation reflects a differential equation in $t$ of the parametrized integral. Although the symmetric scalar product cannot be represented as an integral of a D-finite function, the method of [2] can be adapted to the present situation, in a way that the reduction with respect to the $k$ variables $p_1, \dots, p_k$ is possible simultaneously and that most of the calculations involve polynomials in $k+1$ variables over $\mathbb{Q}(t)$.

### 1.4. Contributions.
Beside presenting a heuristic method that adapts reduction-based algorithms to a simultaneous reduction with respect to several integration variables, our main contribution in the present work is to obtain differential equations satisfied by various models of graphs with vertex degrees restricted to be in a fixed subset of $\{1, \dots, 6\}$, as well as a differential equation satisfied by 7-regular (simple loopless) graphs. In Table 3, we list for a few dozens of models the order of a differential equation satisfied by the counting generating function and the order of a recurrence equation satisfied by its sequence of coefficients, together with corresponding degrees of their coefficients. To the best of our knowledge, this is the first time
For future reference, we note the following formula, which leads to generalizations of Eqs. (5) and (6):

$$ (7) \qquad R^{(k)}(t) = \left\langle \bar{F}, \sum_{n \ge 0} h_k^n \frac{t^n}{n!} \right\rangle = \langle \bar{F}, \exp(h_k t) \rangle. $$

This formula will be proven and extended in Lemma 2.

### 1.3. Earlier computational approaches.
As we mentioned above, Gessel [5] proved the existence of linear differential equations for scalar products like Eq. (7), and earlier work [3] proposed algorithms to compute them. In there, for a given series S in the variables $p_1, \dots, p_k$ we consider the set, denoted $\text{ann}(S)$, of all linear differential operators that annihilate S. The elements of $\text{ann}(S)$ are non-commutative polynomials in the variables $p_1, \dots, p_k$ and in the corresponding derivatives $\partial_1, \dots, \partial_k$; they possess a well-defined total degree in the $2k$ variables. The set $\text{ann}(S)$ is closed under multiplication by any operator on the left and is thus a left ideal. As is customary in effective literature, such a left ideal is best represented by a non-commutative analogue of a Gröbner basis, that is, by a finite set of non-commutative polynomials that can algorithmically divide a given ideal element, resulting into a uniquely defined remainder that is zero if and only if the given polynomial is in the ideal.

Given a number $k$, we henceforth write $p = (p_1, \dots, p_k)$ and $\partial = (\partial_1, \dots, \partial_k)$. Given a series $F$ in $p$ and a series $G$ in $(t, p)$, the differential equations with respect to $t$ satisfied by the scalar product $\langle F, G \rangle$ are to be found as those elements free of $(p, \partial)$ in the (vector space) sum of the left ideal $\text{ann}(G)$ and of the right ideal $\text{ann}(F)^{\dagger}$ obtained by taking the adjoints of all elements in $\text{ann}(F)$ [3] (see the definitions in Section 4). A first algorithm in [3], based on linear algebra, consists: (i) in fixing an integer $d$; (ii) in determining representatives of $\text{ann}(F)^{\dagger}$ and $\text{ann}(G)$ for each possible leading monomial of total degree at most $d$ with respect to $(p, \partial, \partial_k)$; (iii) and in using a non-commutative variant of Gaussian elimination over $\mathbb{Q}(t)$ to eliminate $(p, \partial)$, repeating the whole process with a larger $d$ if elimination results in no non-trivial output. Because there are $\binom{d}{2k+1} = O(d^{2k+1})$ monomials of degree at most $d$, and almost as many representatives to determine for each ideal, this process is very inefficient in practice. A second algorithm in [3] is tailored to a certain form for the argument $G$ in the scalar product: if $G = \exp(h_k t)$, the theory of Hammond series, as developed in [6], provides the formula

$$ \langle F, \exp(h_k t_k) \rangle = \mathcal{H}(F)(0, \dots, 0, t_k), $$

where $\mathcal{H}(F)(t_1, \dots, t_k)$ is a transform of $F$ known as its Hammond series. A simple replacement of the $p_i$ and the $\partial_i$ in $\text{ann}(F)$ with suitable polynomials in $t_1, \dots, t_k$ and corresponding derivatives $\partial_{t_i}$ provides $\text{ann}(\mathcal{H}(F))$. The specialization of $t_1, \dots, t_{k-1}$ to 0 is then obtained by restriction, an operation dual to integration. One way to implement it would have been to first eliminate the $k-1$ variables $\partial_{t_1}, \dots, \partial_{t_{k-1}}$, e.g., by a Gröbner basis calculation, before setting all of the $k-1$ variables $t_1, \dots, t_{k-1}$ to zero and taking a generator of the resulting principal ideal in $\mathbb{Q}(t_k)\langle \partial_{t_k} \rangle$. But a simultaneous elimination in this way leads to high degrees and is also inefficient in practice. More generally, in the 2000s, no good algorithm was known for integration with respect to several variables considered simultaneously, so one had to resort to iterated integrations, one variable after the other. Correspondingly, for multiple restriction one had to perform specializations one variable after the other, and this is what is proposed in [3], in a way that is reminiscent of elimination by successive resultants. This approach, too, fails for $k=5$: all steps are fast until the last elimination, which should eliminate $\partial_{t_1}$ from two degree-9 polynomials in the four variables $t_1, t_5, \partial_{t_1}, \partial_{t_5}$, and this fails in practice.

In both old approaches, the culprit is elimination in too many variables: eliminating $2k$ variables between polynomials in $2k+1$ variables over $\mathbb{Q}(t)$ in the first approach; eliminating $k-1$ variables between polynomials in $2k-1$ variables over $\mathbb{Q}(t_k)$ in the second approach. The second is an improvement in that it reduces the number of variables, and this is assisted by specializations to zero along the process.

A turning point in the theory of Creative Telescoping was the introduction of reduction-based algorithms, starting with the integration of bivariate rational functions [1] in 2010, and followed by many articles in the literature. Inspiration for the present work came from a more recent reduction-based algorithm [2] for the integration with regard to one variable $p$ of general D-finite functions $f(t, p)$, leading to integrals parametrized by $t$. In a nutshell, reduction-based algorithms: (i) set up a reduction process that corresponds to simplifying a function to be integrated modulo derivatives with respect to $p$ of other functions, in such a way that the
differential equations are presented for $R^{(5)}(t)$, $R^{(6)}(t)$ and $R^{(7)}(t)$, or more generally graphs where degrees 5, 6, or 7 are considered.

The recurrences we find are linear, with polynomial coefficients and hence can be unravelled quickly to get data for graphs of high order. For example, it take about 15 minutes to determine the number of 7-regular graphs on 2000 vertices from the ODE of order 20 that we found:

$$r_{2000}^{(7)} = 80680697 \dots 04296875 \approx 8.068069734 \times 10^{18572}.$$

It is even faster when the machine allows parallel processes.

The generated enumerative data, recurrences, differential equations and Maple code implementing our strategy are all available at https://files.inria.fr/chyzak/kregs/.

## 2. WORKED EXAMPLE: 4-REGULAR GRAPHS

Before introducing our procedure in a systematic way in Section 4, we illustrate it with the class of 4-regular graphs, allowing single edges and no loops. (The case $k=3$ is too simple to demonstrate important points of our method.) Specializing Eq. (6) to $k=4$, we consider the scalar product $\langle F, G \rangle$, which represents $R^{(4)}(t)$ when the exponential functions $F = \exp(f)$ and $G = \exp(tg)$ are given by

$$f := \frac{p_1^2}{2} - \frac{p_2^2}{4} + \frac{p_3^2}{6} - \frac{p_4^2}{8} - \frac{p_2}{2} + \frac{p_4}{4}, \quad g := \frac{p_1^4}{24} + \frac{p_1^2 p_2}{4} + \frac{p_2^2}{8} + \frac{p_1 p_3}{3} + \frac{p_4}{4}.$$

2.1. **A reduction procedure.** We begin by explaining a procedure to normalize expressions of the form $\langle F, sG \rangle$ for a polynomial $s \in \mathbb{Q}(t)[p]:$ without changing the value of the scalar product, the polynomial $s$ will be replaced with an element in $\mathbb{Q}(t) + \mathbb{Q}(t)p_1 + \mathbb{Q}(t)p_2$.

From the definition of $F$, we get that annihilating operators for $F$ are

$$(7) \qquad P_1 := \partial_1 - p_1, \quad P_2 := 2\partial_2 + p_2 + 1, \quad P_3 := 3\partial_3 - p_3, \quad P_4 := 4\partial_4 + p_4 - 1.$$

In Section 4, we will define two transformations on differential operators, namely adjoints ($\dagger$) and twists ($\ddagger$). Applying them to Eq. (7), we obtain

$$P_1^\dagger := p_1 - \partial_1, \quad P_2^\dagger := p_2 + 2\partial_2 + 1, \quad P_3^\dagger := p_3 - 3\partial_3, \quad P_4^\dagger := p_4 + 4\partial_4 - 1,$$

and

$$P_1^\sharp := p_1 - \partial_1 - \frac{t}{6}(p_1^3 + 3p_1p_2 + 2p_3), \quad P_2^\sharp := p_2 + 2\partial_2 + \frac{t}{2}(p_1^2 + p_2) + 1,$$

$$P_3^\sharp := p_3 - 3\partial_3 - tp_1, \quad P_4^\sharp := p_4 + 4\partial_4 + t - 1.$$

We will prove in Section 4 that $\langle F, (P_j^\sharp \cdot \bar{s}) G \rangle$ is zero for any $\bar{s} \in \mathbb{Q}(t)[p]$ and any $j$, motivating that we will try to adjust $s$ by a linear combination of polynomials of the form $P_j^\sharp \cdot \bar{s}$.

In order to determine how to do so more precisely, observe first that for any monomial $p^\alpha$,

$$P_1^\sharp \cdot p^\alpha = -\frac{t}{6} p_1^{\alpha_1+3} p_2^{\alpha_2} p_3^{\alpha_3} p_4^{\alpha_4} + \dots, \quad P_2^\sharp \cdot p^\alpha = \frac{t}{2} p_1^{\alpha_1+2} p_2^{\alpha_2} p_3^{\alpha_3} p_4^{\alpha_4} + \dots,$$

$$P_3^\sharp \cdot p^\alpha = -tp_1^{\alpha_1+1} p_2^{\alpha_2} p_3^{\alpha_3} p_4^{\alpha_4} + p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3+1} p_4^{\alpha_4} + \dots, \quad P_4^\sharp \cdot p^\alpha = p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} p_4^{\alpha_4+1} + \dots,$$

where in each case, the dots represent a polynomial with lower total degree. We will base our calculation on these forms. Consider for example any monomial ordering for which $p_4$ is lexicographically higher than all other variables. Given a polynomial $s \in \mathbb{Q}(t)[p]$ with leading term $cp^\beta$ for $\beta_4 \ge 1$, the choice $\alpha = \beta - (0, 0, 0, 1)$ ensures that $s - P_4^\sharp \cdot \bar{s}$ has a leading monomial less than $p^\beta$. As a consequence, $s$ can be reduced by a series of like transformations to a polynomial $s - P_4^\sharp \cdot \bar{s}$ that does not involve $p_4$: here $\bar{s}$ is a polynomial that adds up all the $cp^\alpha$ observed during the reduction process. In other words, one can eliminate $p_4$ from $s$. One can similarly use $P_3^\sharp$ to reduce the degree with respect to $p_3$: this essentially introduces $p_1$ as a replacement of $p_3$, but one can eliminate $p_3$ as well. By continuing with transformations based on $P_2^\sharp$, which do not reintroduce either $p_3$ or $p_4$, one could hope to eliminate $p_1$ as well (after $p_3$ and $p_4$) from $s$. It turns out that one cannot fully eliminate $p_1$, but that degrees with respect to $p_1$ can be reduced down to at most 1. On the other hand, it is not immediately evident that degrees with respect to $p_2$ can be kept under control.
resulting remainder lies in a finite-dimensional vector space; (ii) find a linear relation between the remainders of successive higher-order derivatives with respect to the parameter $t$ of the function to be integrated. In situations where integrals of derivatives are zero, the output linear relation reflects a differential equation in $t$ of the parametrized integral. Although the symmetric scalar product cannot be represented as an integral of a D-finite function, the method of [2] can be adapted to the present situation, in a way that the reduction with respect to the $k$ variables $p_1, \dots, p_k$ is possible simultaneously and that most of the calculations involve polynomials in $k+1$ variables over $\mathbb{Q}(t)$.

**1.4. Contributions.** Besides presenting in Algorithm 1 a method that adapts reduction-based algorithms to a simultaneous reduction with respect to several integration variables, our main contribution in the present work is to obtain differential equations satisfied by various models of graphs with vertex degrees restricted to be in a fixed subset of $\{1, \dots, 7\}$ (see Theorem 1 and Corollary 12). We cannot guarantee the termination of our method, but any differential equation it outputs is correct, as proven by Theorem 11. In Table 2, we list for a few dozens of models the order of a differential equation satisfied by the counting generating function and the order of a recurrence equation satisfied by its sequence of coefficients, together with corresponding degrees of their coefficients. All those equations are proven correct by the computer calculations (see Corollary 12). To the best of our knowledge, this is the first time differential equations are presented for $R^{(5)}(t)$, $R^{(6)}(t)$ and $R^{(7)}(t)$, or more generally graphs where degrees 5, 6, or 7 are considered.

The recurrences we find are linear, with polynomial coefficients and hence can be unravelled quickly to get data for graphs of high order. For example, it take about 15 minutes to determine the number of 7-regular graphs on 2000 vertices from the ODE of order 20 that we found:

$$r_{2000}^{(7)} = 80680697 \dots 04296875 \approx 8.068069734 \times 10^{18572}.$$

It is even faster when the machine allows parallel processes. More generally, we are able to significantly increase the number of known terms compared to the state of the art in the On-line Encyclopedia of Integer Sequences (OEIS) [12] for sequences A338978 and A339847, and we have contributed a new sequence, A374842 counting 7-regular graphs.

The generated enumerative data, recurrences, differential equations and Maple code implementing our strategy are all available at https://files.inria.fr/chyzak/kregs/.

## 2. WORKED EXAMPLE: 4-REGULAR GRAPHS

Before introducing our procedure in a systematic way in Section 4, we illustrate it with the class of 4-regular graphs, allowing single edges and no loops. (The case $k=3$ is too simple to demonstrate important points of our method.) Specializing Eq. (7) to $k=4$, we consider the scalar product $\langle F, G \rangle$, which represents $R^{(4)}(t)$ when the exponential functions $F = \exp(f)$ and $G = \exp(tg)$ are given by

$$f := \frac{p_1^2}{2} - \frac{p_2^2}{4} + \frac{p_3^2}{6} - \frac{p_4^2}{8} - \frac{p_2}{2} + \frac{p_4}{4}, \quad g := \frac{p_1^4}{24} + \frac{p_1^2 p_2}{4} + \frac{p_2^2}{8} + \frac{p_1 p_3}{3} + \frac{p_4}{4}.$$

**2.1. A reduction procedure.** We begin by explaining a procedure to normalize expressions of the form $\langle F, sG \rangle$ for a polynomial $s \in \mathbb{Q}(t)[p]$: without changing the value of the scalar product, the polynomial $s$ will be replaced with an element in $\mathbb{Q}(t) + \mathbb{Q}(t)p_1 + \mathbb{Q}(t)p_2$.

From the definition of $F$, we get that annihilating operators for $F$ are

$$(8) \qquad P_1 := \partial_1 - p_1, \quad P_2 := 2\partial_2 + p_2 + 1, \quad P_3 := 3\partial_3 - p_3, \quad P_4 := 4\partial_4 + p_4 - 1.$$

In Section 4, we will define two transformations on differential operators, namely adjoints ($\dagger$) and twists ($\ddagger$). Applying them to Eq. (8), we obtain

$$P_1^\dagger := p_1 - \partial_1, \quad P_2^\dagger := p_2 + 2\partial_2 + 1, \quad P_3^\dagger := p_3 - 3\partial_3, \quad P_4^\dagger := p_4 + 4\partial_4 - 1,$$

and

$$P_1^\sharp := p_1 - \partial_1 - \frac{t}{6}(p_1^3 + 3p_1p_2 + 2p_3), \quad P_2^\sharp := p_2 + 2\partial_2 + \frac{t}{2}(p_1^2 + p_2) + 1,$$

$$P_3^\sharp := p_3 - 3\partial_3 - tp_1, \quad P_4^\sharp := p_4 + 4\partial_4 + t - 1.$$
To explain how controlling $p_2$ can be done, we continue our informal presentation by recombining the $P_i^\sharp$ in the following way into elements of the right ideal they generate:

$$P_1^\sharp + P_3^\sharp \frac{t}{3} = -\frac{t}{6}p_1^3 - \frac{t}{2}p_1p_2 + \left(1 - \frac{t^2}{3}\right)p_1 - \partial_1 - t\partial_3,$$

$$P_2^\sharp = \frac{t}{2}p_1^2 + \left(1 + \frac{t}{2}\right)p_2 + 1 + 2\partial_2,$$

$$\tilde{P}_5 := P_1^\sharp + P_3^\sharp \frac{t}{3} + P_2^\sharp \frac{p_1}{3} = \frac{1-t}{3}p_1p_2 + \frac{4-t^2}{3}p_1 + \frac{2}{3}p_1\partial_2 - \partial_1 - t\partial_3,$$

$$\tilde{P}_6 := \tilde{P}_5 \frac{t}{2}p_1 + P_2^\sharp \frac{t-1}{3}p_1 = \frac{(4-t^2)t}{6}p_1^2 + \frac{t^2+t-2}{6}p_2^2 + \frac{t-1}{3}p_2 + \frac{t}{3}p_1^2\partial_2 \\ + \frac{t-4}{6} - \frac{t}{2}p_1\partial_1 + \frac{2(t-1)}{3}p_2\partial_2 - \frac{t^2}{2}p_1\partial_3,$$

$$\tilde{P}_7 := \tilde{P}_6 + P_2^\sharp \frac{t^2-4}{3} = \frac{t^2+t-2}{6}p_2^2 + \frac{t^3+2t^2-2t-10}{6}p_2 + \frac{t}{3}p_1^2\partial_2 \\ + \frac{2t^2+t-4}{6} - \frac{t}{2}p_1\partial_1 + \frac{2(t-1)}{3}p_2\partial_2 - \frac{t^2}{2}p_1\partial_3 + \frac{2(t^2-4)}{3}\partial_2.$$

Observe how at each line, one can determine precisely the action of the operator on a monomial $p_1^{\alpha_1} p_2^{\alpha_2}$ and thus predict the leading monomial of the result for the monomial ordering refining total degree by $p_1 > p_2$:

$$\tilde{P}_5 \cdot p_1^{\alpha_1} p_2^{\alpha_2} = \frac{1-t}{3} p_1^{\alpha_1+1} p_2^{\alpha_2+1} + \dots,$$

$$\tilde{P}_6 \cdot p_1^{\alpha_1} p_2^{\alpha_2} = \frac{(4-t^2)t}{6} p_1^{\alpha_1+2} p_2^{\alpha_2} + \dots,$$

$$\tilde{P}_7 \cdot p_1^{\alpha_1} p_2^{\alpha_2} = \frac{t^2+t-2}{6} p_1^{\alpha_1} p_2^{\alpha_2+2} + \dots.$$

Considering in particular $\tilde{P}_7$, one obtains that degrees with respect to $p_2$ can be reduced down to at most 1. Note that the $\tilde{P}_7 \cdot p_1^{\alpha_1} p_2^{\alpha_2}$ luckily do not reintroduce the variables $p_3$ and $p_4$. So at this point, any polynomial $s \in \mathbb{Q}(t)[p]$ in an expression $\langle F, sG \rangle$ can be replaced with a linear combination of 1, $p_1$, $p_2$, and $p_1p_2$ over $\mathbb{Q}(t)$, that is, with some polynomial confined to a 4-dimensional vector space. Finally, because $\tilde{P}_5 \cdot 1 = \frac{1-t}{3}p_1p_2 + \frac{4-t^2}{3}p_1$, the monomial $p_1p_2$ can be replaced with $p_1$ in such linear combinations, bringing the finite dimension down to 3. In the end, for any $s \in \mathbb{Q}(t)[p]$, a sequence of transformations results: first in an element $\tilde{s} \in \mathbb{Q}(t) + \mathbb{Q}(t)p_1 + \mathbb{Q}(t)p_2$ and elements $\tilde{s}_j \in \mathbb{Q}(t)[p]$ for $j = 0, \dots, 4$ such that $\langle F, sG \rangle = \langle F, \tilde{s}G \rangle$ and

$$s - \tilde{s} = \sum_{i=0}^{4} G_i \cdot \tilde{s}_i \quad \text{for} \quad (G_0, \dots, G_4) = (P_4^\sharp, P_3^\sharp, P_2^\sharp, \tilde{P}_7, \tilde{P}_5);$$

next, because $\tilde{P}_5$ and $\tilde{P}_7$ are in the right ideal, in elements $\tilde{s}_j \in \mathbb{Q}(t)[p]$ for $j = 1, \dots, 4$ such that $s - \tilde{s} = P_1^\sharp \cdot \tilde{s}_1 + P_2^\sharp \cdot \tilde{s}_2 + P_3^\sharp \cdot \tilde{s}_3 + P_4^\sharp \cdot \tilde{s}_4$.

Eliminating variables one after the other in this presentation was chosen for the sake of the informal explanation. In the next section and in our implementation, we use an optimized elimination strategy that bases more strongly on total degree.

## 2.2. Recombining normal forms for a differential equation.
We now explain how the reduction step of the previous section can be used to derive a differential equation with respect to $t$ for $\langle F, G \rangle$.

For any $i \in \mathbb{N}$, the identity $\partial_t^i \cdot \langle F, G \rangle = \langle F, g^i G \rangle$ follows from the definition $G = \exp(tg)$. By the reduction of previous section, the polynomial $g^i$ can be replaced with some element $\tilde{g}_i$ from the 3-dimensional vector space $\mathbb{Q}(t) + \mathbb{Q}(t)p_1 + \mathbb{Q}(t)p_2$. So, the family $\{\tilde{g}_0, \tilde{g}_1, \tilde{g}_2, \tilde{g}_3\}$ is obviously linearly dependent over $\mathbb{Q}(t)$, and a linear relation $q_0\tilde{g}_0 + \dots + q_3\tilde{g}_3 = 0$ with $q_i \in \mathbb{Q}(t)$ provides a linear differential relation $(q_0 + q_1\partial_t + q_2\partial_t^2 + q_3\partial_t^3) \cdot \langle F, G \rangle = 0$.
We will prove in Section 4 that $\langle F, (P_j^\sharp \cdot \bar{s}) G \rangle$ is zero for any $\bar{s} \in \mathbb{Q}(t)[p]$ and any $j$, motivating that we will try to adjust $s$ by a linear combination of polynomials of the form $P_j^\sharp \cdot \bar{s}$.

In order to determine how to do so more precisely, observe first that for any monomial $p^\alpha$,

$$P_1^\sharp \cdot p^\alpha = -\frac{t}{6} p_1^{\alpha_1+3} p_2^{\alpha_2} p_3^{\alpha_3} p_4^{\alpha_4} + \dots,$$

$$P_2^\sharp \cdot p^\alpha = \frac{t}{2} p_1^{\alpha_1+2} p_2^{\alpha_2} p_3^{\alpha_3} p_4^{\alpha_4} + \dots,$$

$$P_3^\sharp \cdot p^\alpha = -t p_1^{\alpha_1+1} p_2^{\alpha_2} p_3^{\alpha_3} p_4^{\alpha_4} + p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3+1} p_4^{\alpha_4} + \dots,$$

$$P_4^\sharp \cdot p^\alpha = p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} p_4^{\alpha_4+1} + \dots,$$

where in each case, the dots represent a polynomial with lower total degree. We will base our calculation on these forms. Consider for example any monomial ordering for which $p_4$ is lexicographically higher than all other variables. Given a polynomial $s \in \mathbb{Q}(t)[p]$ with leading term $cp^\beta$ for $\beta_4 \ge 1$, the choice $\alpha = \beta - (0, 0, 0, 1)$ ensures that $s - P_4^\sharp \cdot (cp^\alpha)$ has a leading monomial less than $p^\beta$. As a consequence, $s$ can be reduced by a series of like transformations to a polynomial $s - P_4^\sharp \cdot \bar{s}$ that does not involve $p_4$: here $\bar{s}$ is a polynomial that adds up all the $cp^\alpha$ observed during the reduction process. In other words, one can eliminate $p_4$ from $s$. One can similarly use $P_3^\sharp$ to reduce the degree with respect to $p_3$: this essentially introduces $p_1$ as a replacement of $p_3$, but one can eliminate $p_3$ as well. By continuing with transformations based on $P_2^\sharp$, which do not reintroduce either $p_3$ or $p_4$, one could hope to eliminate $p_1$ as well (after $p_3$ and $p_4$) from $s$. It turns out that one cannot fully eliminate $p_1$, but that degrees with respect to $p_1$ can be reduced down to at most 1. On the other hand, it is not immediately evident that degrees with respect to $p_2$ can be kept under control.

To explain how controlling $p_2$ can be done, we continue our informal presentation by recombining the $P_i^\sharp$ in the following way into elements of the right ideal they generate:

$$P_1^\sharp + P_3^\sharp \frac{t}{3} = -\frac{t}{6} p_1^3 - \frac{t}{2} p_1 p_2 + \left(1 - \frac{t^2}{3}\right) p_1 - \partial_1 - t \partial_3,$$

$$P_2^\sharp = \frac{t}{2} p_1^2 + \left(1 + \frac{t}{2}\right) p_2 + 1 + 2 \partial_2,$$

$$\tilde{P}_5 := P_1^\sharp + P_3^\sharp \frac{t}{3} + P_2^\sharp \frac{p_1}{3} = \frac{1-t}{3} p_1 p_2 + \frac{4-t^2}{3} p_1 + \frac{2}{3} p_1 \partial_2 - \partial_1 - t \partial_3,$$

$$\tilde{P}_6 := \tilde{P}_5 \frac{t}{2} p_1 + P_2^\sharp \frac{t-1}{3} p_1 = \frac{(4-t^2)t}{6} p_1^2 + \frac{t^2+t-2}{6} p_2^2 + \frac{t-1}{3} p_2 + \frac{t}{3} p_1^2 \partial_2$$

$$+ \frac{t-4}{6} - \frac{t}{2} p_1 \partial_1 + \frac{2(t-1)}{3} p_2 \partial_2 - \frac{t^2}{2} p_1 \partial_3,$$

$$\tilde{P}_7 := \tilde{P}_6 + P_2^\sharp \frac{t^2-4}{3} = \frac{t^2+t-2}{6} p_2^2 + \frac{t^3+2t^2-2t-10}{6} p_2 + \frac{t}{3} p_1^2 \partial_2$$

$$+ \frac{2t^2+t-4}{6} - \frac{t}{2} p_1 \partial_1 + \frac{2(t-1)}{3} p_2 \partial_2 - \frac{t^2}{2} p_1 \partial_3 + \frac{2(t^2-4)}{3} \partial_2.$$

Observe how at each line, one can determine precisely the action of the operator on a monomial $p_1^{\alpha_1} p_2^{\alpha_2}$ and thus predict the leading monomial of the result for the monomial ordering refining total degree by $p_1 > p_2$:

$$\tilde{P}_5 \cdot p_1^{\alpha_1} p_2^{\alpha_2} = \frac{1-t}{3} p_1^{\alpha_1+1} p_2^{\alpha_2+1} + \dots,$$

$$\tilde{P}_6 \cdot p_1^{\alpha_1} p_2^{\alpha_2} = \frac{(4-t^2)t}{6} p_1^{\alpha_1+2} p_2^{\alpha_2} + \dots,$$

$$\tilde{P}_7 \cdot p_1^{\alpha_1} p_2^{\alpha_2} = \frac{t^2+t-2}{6} p_1^{\alpha_1} p_2^{\alpha_2+2} + \dots.$$

Considering in particular $\tilde{P}_7$, one obtains that degrees with respect to $p_2$ can be reduced down to at most 1. Note that the $\tilde{P}_7 \cdot p_1^{\alpha_1} p_2^{\alpha_2}$ luckily do not reintroduce the variables $p_3$ and $p_4$. So at this point, any polynomial $s \in \mathbb{Q}(t)[p]$ in an expression $\langle F, sG \rangle$ can be replaced with a linear combination of 1, $p_1$, $p_2$, and $p_1 p_2$ over $\mathbb{Q}(t)$, that is, with some polynomial confined to a 4-dimensional vector space. Finally, because $\tilde{P}_5 \cdot 1 = \frac{1-t}{3} p_1 p_2 + \frac{4-t^2}{3} p_1$, the monomial $p_1 p_2$ can be replaced with $p_1$ in such linear combinations, bringing the finite dimension down to 3. In the end, for any $s \in \mathbb{Q}(t)[p]$, a sequence of transformations results: first in an element $\tilde{s} \in \mathbb{Q}(t) + \mathbb{Q}(t)p_1 + \mathbb{Q}(t)p_2$ and elements $\tilde{s}_j \in \mathbb{Q}(t)[p]$ for $j = 0, \dots, 4$ such that $\langle F, sG \rangle = \langle F, \tilde{s}G \rangle$
Performing these calculations on our worked example, we start with $g^0 = 1$, so that $\check{g}_0 = 1$ as 1 is already reduced. Next, reducing $g$ yields $g = \check{g}_1 + \sum_{i=0}^4 G_i \cdot \tilde{s}_i$ with

$$ \check{g}_1 = - \frac{(t^5 + 2t^4 + 2t^2 + 8t - 4)}{4(t^2 + t - 2)t^2} (p_2 + 1) $$

$$ \text{and } (\check{s}_0, \dots, \check{s}_4) = \left( \frac{1}{4}, \frac{p_1}{3}, \frac{p_1^2}{12t} + \frac{(5t-2)p_2}{12t^2} + \frac{4t^2-1}{6t^2}, -\frac{t^2+4t-2}{2t^2(t^2+t-2)}, 0 \right). $$

At this point, a more heavy calculation yields $g^2 = \check{g}_2 + \sum_{i=0}^4 G_i \cdot \tilde{s}_i$ with

$$ \check{g}_2 = - \frac{t^{12} - 14t^{10} - 20t^9 - 36t^8 - 200t^7 - 356t^6 - 48t^5 + 200t^4 - 336t^3 - 240t^2 + 416t - 96}{16(t^2 + t - 2)^2(t - 1)t^4(t + 2)} \\ - \frac{(t^{13} + 4t^{12} - 16t^{10} - 10t^9 - 36t^8 - 220t^7 - 348t^6 - 48t^5 + 200t^4 - 336t^3 - 240t^2 + 416t - 96)}{16(t^2 + t - 2)^2(t - 1)t^4(t + 2)} p_2 $$

and quotients $\tilde{s}_i$ that we refrain from displaying. After finding a linear dependency between the $\check{g}_i$ over $\mathbb{Q}(t)$, we obtain the annihilating operator

$$ 16t^2(t+2)^2(t-1)^2(t^5+2t^4+2t^2+8t-4)\partial_t^2 \\ + (-4t^{13}-16t^{12}+64t^{10}+40t^9+144t^8+880t^7+1392t^6 \\ + 192t^5-800t^4+1344t^3+960t^2-1664t+384)\partial_t \\ - t^4(t^5+2t^4+2t^2+8t-4)^2. $$

Getting an order 2 less than the dimension 3 could not be predicted.

For efficiency, the remainders $\check{g}_i$ can be obtained in a more incremental way: the formula

$$ \partial_t^{i+1} \cdot \langle F, G \rangle = \partial_t \cdot \langle F, \check{g}_i G \rangle = \langle F, \partial_t \cdot (\check{g}_i G) \rangle = \langle F, (\check{g}_i \times g + \partial_t \cdot \check{g}_i) G \rangle $$

suggests one can obtain $\check{g}_{i+1}$ by reducing $\check{g}_i \times g + \partial_t \cdot \check{g}_i$, which is much smaller than $g^{i+1}$. This makes calculations generally faster, although in the present example $\check{g}_1 \times g + \partial_t \cdot \check{g}_1$ is messier than $g^2$.

### 3. APPLICABILITY TO VARIOUS MODELS OF GRAPHS

As we remarked in the introduction, there are many enumeration problems that can be expressed using the scalar product, and have the potential to be solved with our strategy. The computational limits are directly related to the maximal $i$ of all $p_i$ that appear in the expressions, and this leaves substantial flexibility. Although in the work above (namely Section 1.2 and Section 2) we have focused on the case of simple, loopless graphs, with only minor modifications of $G$ in Eq. (6) we can consider graphs with multiple edges, or loops, or both. The form is still an exponential of a polynomial in the $p_i$. Similarly, it is straightforward to consider graph classes where the possible vertex degrees come from a finite set $K$. To this end, it suffices to replace $\exp(th_k)$ with $\exp(t(\sum_{j \in K} h_j))$ and to express the $h_j$ in the power sum basis.

Most of our calculations are for sets $K$ included in $\{1, 2, 3, 4, 5, 6\}$, allowing several edge and loop variations. For example, we have computed the differential equation satisfied by the set of labelled graphs with degree bounded by $k = 6$, that is, for $K = \{1, 2, 3, 4, 5, 6\}$. In addition, we have computed one model with $K = \{7\}$.

Table 3 presents the results of applying our method as summarized in Table 1. We label generalized regular graph models according to three parameters:

* $e$ encodes the model of allowed edges: ‘se’ is used for graphs with single edges; ‘me’ is used for generalized structures with multiple edges allowed (usually called “multigraphs”).

* $l$ encodes how loops are allowed and counted: ‘ll’ is used for loopless structures, like “graphs” in the usual terminology; ‘la’ is used for structures with loops allowed and contributing 2 each to the degree of a vertex, in other words, those models enumerate structures according to the number of adjacent half-edges. ‘lh’ is used for structures with loops allowed and contributing 1 each to the degree of a vertex, in other words, those models enumerate structures according to the number of adjacent edges.
and

$$s - \check{s} = \sum_{i=0}^{4} G_i \cdot \bar{s}_i \quad \text{for} \quad (G_0, \dots, G_4) = (P_4^{\sharp}, P_3^{\sharp}, P_2^{\sharp}, \tilde{P}_7, \tilde{P}_5);$$

next, because $\tilde{P}_5$ and $\tilde{P}_7$ are in the right ideal, in elements $\bar{s}_j \in \mathbb{Q}(t)[p]$ for $j = 1, \dots, 4$ such that $s - \check{s} = P_1^{\sharp} \cdot \bar{s}_1 + P_2^{\sharp} \cdot \bar{s}_2 + P_3^{\sharp} \cdot \bar{s}_3 + P_4^{\sharp} \cdot \bar{s}_4$.

Eliminating variables one after the other in this presentation was chosen for the sake of the informal explanation. In the next section and in our implementation, we use an optimized elimination strategy that bases more strongly on total degree.

## 2.2. Recombining normal forms for a differential equation.
We now explain how the reduction step of the previous section can be used to derive a differential equation with respect to $t$ for $\langle F, G \rangle$.

For any $i \in \mathbb{N}$, the identity $\partial_t^i \cdot \langle F, G \rangle = \langle F, g^i G \rangle$ follows from the definition $G = \exp(tg)$. By the reduction of previous section, the polynomial $g^i$ can be replaced with some element $\check{g}_i$ from the 3-dimensional vector space $\mathbb{Q}(t) + \mathbb{Q}(t)p_1 + \mathbb{Q}(t)p_2$. So, the family $\{\check{g}_0, \check{g}_1, \check{g}_2, \check{g}_3\}$ is obviously linearly dependent over $\mathbb{Q}(t)$, and a linear relation $q_0\check{g}_0 + \dots + q_3\check{g}_3 = 0$ with $q_i \in \mathbb{Q}(t)$ provides a linear differential relation $(q_0 + q_1\partial_t + q_2\partial_t^2 + q_3\partial_t^3) \cdot \langle F, G \rangle = 0$.

Performing these calculations on our worked example, we start with $g^0 = 1$, so that $\check{g}_0 = 1$ as $1$ is already reduced. Next, reducing $g$ yields $g = \check{g}_1 + \sum_{i=0}^4 G_i \cdot \bar{s}_i$ with

$$\check{g}_1 = - \frac{(t^5 + 2t^4 + 2t^2 + 8t - 4)}{4(t^2 + t - 2)t^2} (p_2 + 1)$$

$$\text{and } (\bar{s}_0, \dots, \bar{s}_4) = \left( \frac{1}{4}, \frac{p_1}{3}, \frac{p_1^2}{12t} + \frac{(5t-2)p_2}{12t^2} + \frac{4t^2-1}{6t^2}, -\frac{t^2+4t-2}{2t^2(t^2+t-2)}, 0 \right).$$

At this point, a more heavy calculation yields $g^2 = \check{g}_2 + \sum_{i=0}^4 G_i \cdot \bar{s}_i$ with

$$\check{g}_2 = - \frac{t^{12} - 14t^{10} - 20t^9 - 36t^8 - 200t^7 - 356t^6 - 48t^5 + 200t^4 - 336t^3 - 240t^2 + 416t - 96}{16(t^2 + t - 2)^2(t - 1)t^4(t + 2)} \\ - \frac{(t^{13} + 4t^{12} - 16t^{10} - 10t^9 - 36t^8 - 220t^7 - 348t^6 - 48t^5 + 200t^4 - 336t^3 - 240t^2 + 416t - 96)}{16(t^2 + t - 2)^2(t - 1)t^4(t + 2)} p_2$$

and quotients $\bar{s}_i$ that we refrain from displaying. After finding a linear dependency between the $\check{g}_i$ over $\mathbb{Q}(t)$, we obtain the annihilating operator

$$16t^2(t+2)^2(t-1)^2(t^5+2t^4+2t^2+8t-4)\partial_t^2 \\ + (-4t^{13}-16t^{12}+64t^{10}+40t^9+144t^8+880t^7+1392t^6 \\ + 192t^5-800t^4+1344t^3+960t^2-1664t+384)\partial_t \\ - t^4(t^5+2t^4+2t^2+8t-4)^2.$$

Getting an order 2 less than the dimension 3 could not be predicted.

For efficiency, the remainders $\check{g}_i$ can be obtained in a more incremental way: the formula

$$\partial_t^{i+1} \cdot \langle F, G \rangle = \partial_t \cdot \langle F, \check{g}_i G \rangle = \langle F, \partial_t \cdot (\check{g}_i G) \rangle = \langle F, (\check{g}_i \times g + \partial_t \cdot \check{g}_i) G \rangle$$

suggests one can obtain $\check{g}_{i+1}$ by reducing $\check{g}_i \times g + \partial_t \cdot \check{g}_i$, which is much smaller than $g^{i+1}$. This makes calculations generally faster, although in the present example $\check{g}_1 \times g + \partial_t \cdot \check{g}_1$ is messier than $g^2$.

# 3. APPLICABILITY TO VARIOUS MODELS OF GRAPHS

As we remarked in the introduction, there are many enumeration problems that can be expressed using the scalar product, and have the potential to be solved with our strategy. The computational limits are directly related to the maximal index $i$ of all $p_i$ that appear in the expressions, and this leaves substantial flexibility. Although in the work above (namely Section 1.2 and Section 2) we have focused on the case of simple, loopless graphs, with only minor modifications of $\tilde{F}$ in Eq. (7) we can consider graphs with multiple edges, or loops, or both, as we will prove in Lemma 2. The form is still an exponential of a polynomial in the $p_i$. Similarly, it is straightforward to consider graph classes where the possible vertex degrees come from
• K denotes the set of allowed degrees of vertices, whether it be counting adjacent edges with 'lh' models or counting adjacent half-edges with 'la' models; usual k-regular graphs are obtained by setting K to the singleton {k}; models with K of larger cardinality allow different vertices of a graph to have different degrees as long as they are in K; for example, K = {1, 2, ..., k} can be used to describe a class of graphs with vertex degree bounded by k; unless otherwise clear by the context, we make k = max K.

Finally, it is worth it to recall that given two combinatorial classes, and differential equations satisfied by the generating function of each class, we can determine the differential equations satisfied by both the sum and the product of the two generating functions. This sum and product are respectively the generating functions of the union and the cartesian product of the two classes. For example, from our existing results, we could easily determine the differential equations satisfied by the set of graphs that are either 5- or 6-regular. (In contrast to the set of graphs whose vertices are of degree either 5 or 6, which we can determine directly).

## 4. DESCRIPTION OF THE APPROACH

Fix a number $k$ and, again, write $p = (p_1, \dots, p_k)$ and $\partial = (\partial_1, \dots, \partial_k)$ as a shorthand. The number $k$ is the level of regularity of graphs, that is, with the $k$ variables in $p$ we will be able to express the enumerative series of $k$-regular graphs and variants with regularity bounded by $k$.

Introduce the Weyl algebra

$$W_p := \mathbb{Q}\langle p_1, \dots, p_k, \partial_1, \dots, \partial_k; \partial_i p_j = p_j \partial_i + \delta_{i,j}, 1 \le i, j \le k \rangle,$$

where $\delta_{i,j}$ is one if and only if $i = j$, zero otherwise. Each $\partial_i$ acts on $\mathbb{Q}[t][[p]]$ as the usual derivation operator with respect to $p_i$. The following relations are easily derived for any two series $U$ and $V$ in $\mathbb{Q}[t][[p]]$ and any $i \in \{1, \dots, k\}$:

$$\langle p_i U, V \rangle = \langle U, i \partial_i \cdot V \rangle, \quad \langle i \partial_i \cdot U, V \rangle = \langle U, p_i V \rangle.$$

By bilinearity and symmetry, proving these relations reduces indeed to proving the identity

$$(9) \qquad \langle p_i p_\lambda, p_\nu \rangle = \langle p_\lambda, i \partial_i \cdot p_\nu \rangle$$

for any $i$, $\lambda$, and $\nu$. We prove it for completeness. First, the identity holds if $\nu$ does not involve $i$, both sides being zero. So we continue assuming $i$ appears in $\nu$. Define $\lambda^+$ as the partition obtained by adjoining $i$ to $\lambda$ and consider the integers $r_i$ as in Eq. (2), so that the analog of Eq. (2) for $\lambda^+$ is obtained by incrementing $r_i$. Therefore, $z_{\lambda^+} = z_{\lambda}r_i(i+1)$ holds. Define as well $\nu^-$ as the partition obtained by removing $i$ from $\nu$, so that $\partial_i \cdot p_\nu = s_i p_{\nu^-}$ where $s_i$ denotes the number of occurrences of $i$ in $\nu$. In particular, $s_i = r_i + 1$ if $\nu = \lambda^+$. Next,

$$\langle p_i p_\lambda, p_\nu \rangle = \langle p_{\lambda^+}, p_\nu \rangle = \delta_{\lambda^+, \nu} z_\lambda i (r_i + 1) = i(r_i + 1) \delta_{\lambda, \nu^-} z_\lambda = i(r_i + 1) \langle p_\lambda, p_{\nu^-} \rangle = i \langle p_\lambda, \partial_i \cdot p_\nu \rangle$$

and Eq. (9) is proved. More generally, for any linear differential operator $L$, $\langle L \cdot U, V \rangle = \langle U, L^\dagger \cdot V \rangle$, where the adjoint $L^\dagger$ of $L$ is the result of applying the algebra anti-automorphism of $W_p$ defined by $p_i^\dagger = i \partial_i$ and $\partial_i^\dagger = i^{-1} p_i$. This adjoint operation is an involution. Note that $W_p[t]$ acts on $\mathbb{Q}[t][[p]]$ as well, but we will restrict the use of this action to right-hand arguments of scalar products.

Given two polynomials $f$ and $g$ in $\mathbb{Q}[p] \setminus \mathbb{Q}$, introduce:

• $F := \exp(f) \in \mathbb{Q}[[p]]$,

• $G := \exp(tg) \in \mathbb{Q}[p][[t]] \cap \mathbb{Q}[t][[p]]$,

• $S := \langle F, G \rangle \in \mathbb{Q}[[t]]$.

We will write $f_i$ for $\partial_i \cdot f$ and $g_i$ for $\partial_i \cdot g$.

If $P \in W_p$ annihilates $F$, then for any $s \in \mathbb{Q}[p]$,

$$(10) \qquad 0 = \langle P \cdot F, sG \rangle = \langle F, P^\dagger \cdot (sG) \rangle = \langle F, (P^\sharp \cdot s)G \rangle,$$

where

$$P^\sharp(p_1, \dots, p_k, \partial_1, \dots, \partial_k) = P^\dagger(p_1, \dots, p_k, \partial_1 + tg_1, \dots, \partial_k + tg_k) \in W_p[t].$$

Note that when $P$ runs over the left ideal of annihilating operators of $F$, denoted $\text{ann } F$, the transform $P^\dagger$ runs over the right ideal $(\text{ann } F)^\dagger$, and likewise $P^\sharp$ runs over the right ideal $(\text{ann } F)^\sharp$. In particular, Eq. (10) holds for $P = P_i := i(\partial_i - f_i)$, in which case $P^\sharp$ is given as $P_i^\sharp$ in Eq. (8).
a finite set $K$. To this end, it suffices to replace $\exp(th_k)$ with $\exp(t(\sum_{j \in K} h_j))$ (as per the lemma again) and to express the $h_j$ in the power-sum basis. For the lemma and future discussions, we label generalized regular graph models according to three parameters:

* $e$ encodes the model of allowed edges: 'se' is used for graphs with single edges; 'me' is used for generalized structures with multiple edges allowed (usually called "multigraphs").

* $l$ encodes how loops are allowed and counted:

- 'll' is used for loopless structures, like "graphs" in the usual terminology;

- 'la' is used for structures with loops allowed and contributing 2 each to the degree of a vertex, in other words, those models enumerate structures according to the number of adjacent half-edges;

- 'lh' is used for structures with loops allowed and contributing 1 each to the degree of a vertex, in other words, those models enumerate structures according to the number of adjacent edges.

* $K$ denotes the set of allowed degrees of vertices, whether it be counting adjacent edges with 'lh' models or counting adjacent half-edges with 'la' models; usual $k$-regular graphs are obtained by setting $K$ to the singleton $\{k\}$; models with $K$ of larger cardinality allow different vertices of a graph to have different degrees as long as they are in $K$; for example, $K = \{1, 2, \dots, k\}$ can be used to describe a class of graphs with vertex degree bounded by $k$; unless otherwise clear by the context, we make $k = \max K$.

### 3.1. Theoretical flexibility.

**Lemma 2.** The exponential generating function of a graph model given by some tuple $(e, l, K)$ is the scalar product $\langle \exp(f), \exp(tg) \rangle$ for the polynomials $f$ and $g$ in $p_1, \dots, p_k$ ($k = \max K$) defined by Eqs. (17) and (18).

The following proof generalizes Eq. (7) to handle more graph classes, and degree restrictions. For each graph class we define a symmetric function encoding of graphs without degree restrictions, which we shall denote by $\bar{F}$, expressed in the power sum basis (see Table 1). In all cases $\bar{F}$ can be written as an exponential of an infinite sum $\bar{f}$ of terms in the $p_i$, and the wanted generating function takes the form of a scalar product $\langle \bar{F}, G \rangle$. We show that the coefficient extractor $G$ has the form $G = \exp(tg)$ for a symmetric polynomial $g$. Writing $g$ in the power sum basis involves only a finite number of $p_i$, and hence $\langle \bar{F}, G \rangle = \langle F, G \rangle$, where $F$ is obtained from $\bar{F}$ by setting all but a finite number of the $p_i$ to 0, and hence is of the form $F = \exp(f)$ where $f$ is obtained from $\bar{f}$ in the same way.

*Proof.* First we consider the extraction operators and the corresponding series $G$. For any symmetric function $S$, the coefficient of the monomial $m_\lambda$ in $S$ is $\langle S, h_\lambda \rangle$. To get the desired form of $G$ we use the decomposition $h_\lambda = h_{\lambda_1} h_{\lambda_2} \dots$, and the linearity of the scalar product.

Thus, in order to count $k$-regular objects, that is, for the case $K = \{k\}$, as above with Eq. (7) we have to use $\lambda = (k, \dots, k)$, with $n$ equal parts, for each size $n$. This yields the extraction formula

$$ \sum_{n \ge 0} \langle S, h_{k^n} \rangle \frac{t^n}{n!} = \sum_{n \ge 0} \langle S, h_k^n \frac{t^n}{n!} \rangle = \langle S, \exp(h_k t) \rangle, $$

and so $G = \exp(th_k)$.

In the case where the degree can be from a finite set $K$ of integers, we need to extract the coefficients $\langle S, m_\lambda \rangle$ for partitions $\lambda$ with all parts in $K$. We note that, by the classic correspondence between the exponential function and labelled set constructions, $G = \exp(t \sum_{k \in K} h_k)$ gives the correct set of monomials with the correct weighting. Using the change of basis formula $h_n = \sum_{\lambda \vdash n} \frac{p_\lambda}{z_\lambda}$, we see that written in the power sum basis, $G$ uses a finite number of $p_i$, the maximum index of which is at most the maximum element of $K$.

Next, let us consider the symmetric functions $\bar{F}$ encoding the different unconstrained graph classes corresponding to each choice for $(e, l)$. We can build up the generating function for all six combinations, and use some basic symmetric-function identities to express them using power sums. The results are derived from [17, Proposition 7.7.4], which is proved in a manner similar to Eq. 4 and states

$$ (9) \quad \prod_{i,j} \frac{1}{1 - x_i y_j} = \exp \left( \sum_{n \ge 1} \frac{1}{n} p_n(x) p_n(y) \right) \quad \text{and} \quad \prod_{i,j} (1 + x_i y_j) = \exp \left( \sum_{n \ge 1} \frac{(-1)^{n-1}}{n} p_n(x) p_n(y) \right), $$
**Input:** a graph model $(e, l, k, K)$,
where $e \in \{\text{'se'}, \text{'me'}\}, l \in \{\text{'ll'}, \text{'lh'}, \text{'la'}\}, k \in \mathbb{N}_{>0}, K \subset \{1, \dots, k\}$.

**Output:** an operator of minimal order in $\partial_t$
that cancels the counting generating function of the model.

a. Compute $g = \sum_{\lambda \vdash n} p_{\lambda}/z_{\lambda}$ and $f$ by the formula

$$f = \sum_{j \in K} \left( \sum_{i=1}^{j} \{e = \text{'se'} ? (-1)^{i+1} : 1\} \frac{p_i^2}{2i} + \{e = \text{'lh'} ? 1 : 0\} \frac{p_i}{i} - \{l = \text{'la'} ? -1 : 1\} \sum_{i=1}^{\lfloor j/2 \rfloor} \{e = \text{'se'} ? (-1)^{i+1} : 1\} \frac{p_{2i}}{2i} \right),$$

where for a logical formula $\mathcal{P}$, the expression $\{\mathcal{P} ? t : f\}$ is equal to $t$ if $\mathcal{P}$ holds and to $f$ otherwise.

b. Get generators of the right $W_p(t)$-ideal $(\text{ann } f)^{\sharp}$ by computing $P_i^{\sharp}$ for $1 \le i \le k$ by the formula

$$P_i^{\sharp} = (i\partial_i - if_i)^{\sharp} = p_i - if_i(\partial_1 + tg_1, 2(\partial_2 + tg_2), \dots, k(\partial_k + tg_k)). \quad (8)$$

Here, the right-hand side is obtained by the non-commutative substitution of $p_1$ with $\partial_1 + tg_1$, of $p_2$ with $2(\partial_2 + tg_2)$, ..., of $p_k$ with $k(\partial_k + tg_k)$, in the polynomial $f_i = f_i(p_1, \dots, p_k)$.

c. Transform each $P_i^{\sharp}$ by the map

$$\sum_{\alpha} c_{\alpha} \partial^{\alpha} \mapsto c_0 \eta + \sum_{\alpha \neq 0} c_{\alpha} \partial^{\alpha}$$

to get a system of generators of a right $\mathbb{Q}(t)[p]$-module. Here, $\alpha$ ranges in the finite set of exponents involved in the $P_i^{\sharp}$.

d. Compute a Gröbner basis of this module for an ordering $\prec$ that makes $\eta$ lexicographically higher than $p$ and $p$ lexicographically higher than $\partial$.

e. Obtain elements $G_1, \dots, G_\rho$ of $W_p(t)$ by setting $\eta = 1$ in those elements of the Gröbner basis that involve $\eta$ with a non-zero coefficient, then write each $G_i$ in the form $Q_i(p) + R_i(p, \partial)$ where each monomial of $R_i$ involves at least one $\partial_j$.

f. If the polynomial ideal $I = (Q_1, \dots, Q_\rho)$ has positive dimension, then return 'FAIL', else determine the monomials $p^{\beta_1}, \dots, p^{\beta_\delta}$ under the stair of $I$.

g. Set $\check{g}_0 = 1$, then for $i$ from 2 to $\delta$, set $\check{g}_i = \text{red}(g\check{g}_{i-1} + \partial_t \cdot \check{g}_{i-1}, (G_i)_{i=1}^\rho, \prec)$.

h. Compute the matrix $M$ with rows indexed by $0 \le i \le \delta$ and columns indexed by $1 \le j \le \delta$, whose entry at position $(i, j)$ is the coefficient of $p^{\beta_j}$ in $G_i$.

i. Compute a basis of the left kernel of $M$, then combine its elements to obtain a non-zero row vector $(q_0, \dots, q_\delta) \in \mathbb{Q}(t)^{\delta+1}$ with maximal number of zeros to the right.

j. Return $q_0 + q_1 \partial_t + \dots + q_\delta \partial_\delta$.

<caption>TABLE 1. Outline of the method. Uses the reduction of TABLE 2.</caption>

Introduce the derivation operator $\partial_t$ with respect to $t$ as well as the Weyl algebra

$$W_t := \mathbb{Q}\langle t, \partial_t; \partial_t t = t \partial_t + 1 \rangle.$$

Observe

$$\partial_t^j \cdot S = \langle F, \partial_t^j \cdot G \rangle = \langle F, g^j G \rangle, \quad (11)$$
<table><caption>TABLE 1. Product expressions to encode labelled graphs of the six types considered in Eqs. (17). The product expression $\bar{F}$ is equal to the exponential $\exp(f)$ where $\bar{f}$ is the summation in the final column. The polynomial $f$ in the hypotheses is equal to $\bar{f}$ where all $p_n$ are set to zero, for $n > k$.</caption><thead><tr><th>Graph type</th><th>x-expression F&#773;</th><th>f&#773; in power-sum basis</th></tr></thead><tbody><tr><td>('se', 'll')</td><td>&Pi;<sub>i&lt;j</sub>(1 + x<sub>i</sub>x<sub>j</sub>)</td><td>&Sigma;<sub>n&ge;1</sub>(-1)<sup>n-1</sup> <sup>p<sub>n</sub><sup>2</sup> - p<sub>2n</sub></sup>&frasl;<sub>2n</sub></td></tr><tr><td>('se', 'la')</td><td>&Pi;<sub>i&le;j</sub>(1 + x<sub>i</sub>x<sub>j</sub>)</td><td>&Sigma;<sub>n&ge;1</sub>(-1)<sup>n-1</sup> <sup>p<sub>n</sub><sup>2</sup> + p<sub>2n</sub></sup>&frasl;<sub>2n</sub></td></tr><tr><td>('se', 'lh')</td><td>&Pi;<sub>i&lt;j</sub>(1 + x<sub>i</sub>x<sub>j</sub>) &times; &Pi;<sub>i</sub>(1 + x<sub>i</sub>)</td><td>&Sigma;<sub>n&ge;1</sub>(-1)<sup>n-1</sup> (<sup>p<sub>n</sub><sup>2</sup></sup>&frasl;<sub>2n</sub> - <sup>p<sub>2n</sub></sup>&frasl;<sub>2n</sub> + <sup>p<sub>n</sub></sup>&frasl;<sub>n</sub>)</td></tr><tr><td>('me', 'll')</td><td>&Pi;<sub>i&lt;j</sub>(1 - x<sub>i</sub>x<sub>j</sub>)<sup>-1</sup></td><td>&Sigma;<sub>n&ge;1</sub> <sup>p<sub>n</sub><sup>2</sup> - p<sub>2n</sub></sup>&frasl;<sub>2n</sub></td></tr><tr><td>('me', 'la')</td><td>&Pi;<sub>i&le;j</sub>(1 - x<sub>i</sub>x<sub>j</sub>)<sup>-1</sup></td><td>&Sigma;<sub>n&ge;1</sub> <sup>p<sub>n</sub><sup>2</sup> + p<sub>2n</sub></sup>&frasl;<sub>2n</sub></td></tr><tr><td>('me', 'lh')</td><td>&Pi;<sub>i&lt;j</sub>(1 - x<sub>i</sub>x<sub>j</sub>)<sup>-1</sup> &times; &Pi;<sub>i</sub>(1 - x<sub>i</sub>)<sup>-1</sup></td><td>&Sigma;<sub>n&ge;1</sub> (<sup>p<sub>n</sub><sup>2</sup></sup>&frasl;<sub>2n</sub> - <sup>p<sub>2n</sub></sup>&frasl;<sub>2n</sub> + <sup>p<sub>n</sub></sup>&frasl;<sub>n</sub>)</td></tr></tbody></table>

where $p_n(x)$ is the same series $p_n = \sum_i x_i^n$ as before and $p_n(y)$ is its analogue $\sum_i y_i^n$. We exploit these equations using two key evaluations. Setting $y_i = x_i$ in Eq. (9) (and hence writing $p_n$ for $p_n(x)$) we get

$$ (10) \qquad \prod_{i,j} \frac{1}{1-x_i x_j} = \exp\left(\sum_{n \ge 1} \frac{p_n^2}{n}\right) \quad \text{and} \quad \prod_{i,j} (1+x_i x_j) = \exp\left(\sum_{n \ge 1} (-1)^{n-1} \frac{p_n^2}{n}\right). $$

Next, setting $y_1 = 1$ and $y_k = 0$, for $k > 1$, into Eq. (9), thus forcing $p_n(y) = 1$, for $n \ge 1$, we have

$$ \prod_i \frac{1}{1-x_i} = \exp\left(\sum_{n \ge 1} \frac{p_n}{n}\right) \quad \text{and} \quad \prod_i (1+x_i) = \exp\left(\sum_{n \ge 1} (-1)^{n-1} \frac{p_n}{n}\right). $$

Remark that for $p_n = p_n(x_1, x_2, \dots)$, we have $p_n(x_1^2, x_2^2, \dots) = p_{2n}(x_1, x_2, \dots) = p_{2n}$, hence

$$ (11) \qquad \prod_i \frac{1}{1-x_i^2} = \exp\left(\sum_{n \ge 1} \frac{p_{2n}}{n}\right) \quad \text{and} \quad \prod_i (1+x_i^2) = \exp\left(\sum_{n \ge 1} (-1)^{n-1} \frac{p_{2n}}{n}\right). $$

All six cases can be derived using these in various products, and the results are summarized in Table 1. For example, multiplying Eqs. (10) and (11) yields the squares of the x-expressions for ('se', 'la') and ('me', 'la'), and correspondingly the doubles of the power-sum expressions $\bar{f}$. These calculations give the values in Eq. (17) once we recall that the maximum index of a power-sum symmetric function in $g$ is bounded, thus the scalar product will be unchanged if the power sums with indices higher than that bound are set to 0. Each truncated expression comes in two sums to accommodate the parts in $p_n$ and $p_{2n}$ separately. □

It is worth it to recall that given two combinatorial classes, and differential equations satisfied by the generating function of each class, we can determine the differential equations satisfied by both the sum and the product of the two generating functions. This sum and product are respectively the generating functions of the union and the cartesian product of the two classes.

## 3.2. Practical calculations.
We implemented our method as summarized in Algorithm 1 and ran it successfully in Maple. Table 2 presents the results. All of our calculations are for sets $K$ included in $\{1, 2, 3, 4, 5, 6, 7\}$, allowing several edge and loop variations. For example, we have computed the differential equation satisfied by the set of labelled graphs with degree bounded by $k = 7$, that is, for $K = \{1, 2, 3, 4, 5, 6, 7\}$, and the differential equation satisfied by the set of labelled graphs with degree exactly $k = 7$, that is, for $K = \{7\}$.

Following up the remark at the end of the previous section, from our existing results we could for example easily determine the differential equations satisfied by the set of graphs that are either 5- or 6-regular. (In contrast to the set of graphs whose vertices are of degree either 5 or 6, which we can determine directly).
**Input:** a polynomial $s \in \mathbb{Q}(t)[p]$ to be reduced; differential operators $G_1, \dots, G_\rho$ from $W_p(t)$; a monomial ordering $<$ for which the leading monomials $m_i$ of the $G_i$ do not involve $\partial$.

**Output:** a polynomial $\check{s} \in \mathbb{Q}(t)[p]$ such that $s - \check{s} \in \sum_{i=1}^\rho G_i \cdot \mathbb{Q}(t)[p]$.

a. If no monomial of $s$ is divisible by any $m_i$, return $s$.

b. Set $m$ to the maximal monomial in $s$ that is divisible by some $m_i$ and choose $j$ such that $m_j$ divides $m$.

c. Set $c$ to the coefficient of $m$ in $s$ and $c_j$ to the leading coefficient of $G_j$.

d. Set $t$ to the term $\frac{c}{c_j \cdot m_j}$ and return $\text{red}(s - G_j \cdot t, (G_i)_{i=1}^\rho, <)$.

<caption>TABLE 2. Reduction used by the method in TABLE 1.</caption>

so that an annihilator $Q = \sum_{j=0}^r q_j(t) \partial_t^j \in W_t$ of $S$ satisfies

$$0 = Q \cdot S = \langle F, Q \cdot G \rangle = \langle F, \sum_{j=0}^{r} q_j g^j G \rangle = \langle F, \sum_{j=0}^{r} q_j (g^j + \ell_j) G \rangle$$

for any polynomials $\ell_j$ that are linear combinations over $\mathbb{Q}[t]$ of polynomials of the form $P^\sharp \cdot s$, that is, elements of the vector space

$$H := \sum_{P \in \text{ann} F} P^\sharp \cdot \mathbb{Q}(t)[p] = \sum_{P \in (\text{ann} F)^\sharp} P \cdot \mathbb{Q}(t)[p].$$

In what follows, for each $g^j$ we (implicitly) obtain $\ell_j$ in such a way that the computed $g^j + \ell_j$ is “reduced” and confined in a finite-dimensional $\mathbb{Q}(t)$-vector space. This makes it possible to derive the $q_j$.

The procedure is to deal with 11 for each $j$ separately, by reducing the coefficient $g^j$ modulo $H$. This space $H$ is first expressed as a finite sum of spaces as follows. Fix any finite family $\{L_i\}_{i=1}^\ell$ of generators of $(\text{ann} F)^\sharp$. Then, the finite sum $\tilde{H} := \sum_{i=1}^\ell L_i \cdot \mathbb{Q}(t)[p]$ is a subspace of $H$. Writing any $P$ of $(\text{ann} F)^\sharp$ in the form $P = \sum_{i=1}^\ell L_i U_i$ yields the inclusion of the space $H$ into $\tilde{H}$, and thus the equality $\tilde{H} = H$. To define the reduction, we proceed by exchanging the generating family $\{P_i^\sharp\}$ of $(\text{ann} F)^\sharp$ for a family $\{G_i\}_{i=1}^\ell$ satisfying the property that any term $cm$ to be reduced ($c$ a coefficient, $m$ a monomial) will be obtained for some $(j, s) \in \{1, \dots, \ell\} \times \mathbb{Q}(t)[p]$ as the leading monomial of $G_j \cdot s$, where leading monomials are decided by some monomial ordering of $\mathbb{Q}(t)[p]$ that is compatible with the choice of the family $\{G_i\}_{i=1}^\ell$. To make this possible, we ensure that $G_j = m_j + \dots \in W_p(t)$ for a monomial $m_j$ in $p$, with the property that, for any $\tilde{s} \in \mathbb{Q}(t)[p]$, the leading monomial of $m_j \tilde{s}$ is larger than the leading monomial of $(G_j - m_j) \cdot \tilde{s}$. In practice, the polynomial $s$ used to reduce $cm$ will be set to the term $cm/m_j$, so that $m$ is reduced into $m - G_j \cdot (cm/m_j)$. Observing that only finitely many monomials are divisible by none of the $m_j$ will then ensure the wanted confinement in finite dimension.

There remains to explain how to choose the $G_i$. To this end, consider the action of $W_p(t)$ on polynomials of $\mathbb{Q}(t)[p]$, and compare monomials $m_1 = p^{\alpha_1} \partial^{\beta_1}$ and $m_2 = p^{\alpha_2} \partial^{\beta_2}$ in $W_p(t)$ by declaring $m_1 > m_2$ if and only if $p^{\alpha_1 + \beta_2} > p^{\alpha_2 + \beta_1}$ for the ordering on polynomials. Under the assumption that the monomial order is graded by the total degree in $(p, \partial)$, it is sufficient to force the leading monomial of each $G_i$ to be a monomial in $p$ to have the wanted property on the $G_j \cdot s$.

We do not know how to ensure the existence of a family $\{G_j\}_{j=1}^\ell$ whose leading monomials are monomials in $p$, but a module Gröbner basis calculation will in practice be sufficient to exhibit such a situation for $k$-regular graphs with $k \le 7$.

For each $i$, write $P_i^\sharp = Q_i(p) + R_i(p, \partial)$, where $Q_i$ does not involve any $\partial_j$ and each monomial of $R_i$ involves at least one $\partial_j$. Then, consider $M_i := \eta_1 Q_i + \eta_0 R_i$, where $\eta_0$ and $\eta_1$ are new names denoting elements of a
## 4. DESCRIPTION OF THE APPROACH

We now provide more formal details on our method, which will lead to Algorithm 1. Fix a number $k$ and, again, write $p = (p_1, \dots, p_k)$ and $\partial = (\partial_1, \dots, \partial_k)$ as a shorthand. The number $k$ is the level of regularity of graphs, that is, with the $k$ variables in $p$ we will be able to express the enumerative series of $k$-regular graphs and variants with regularity bounded by $k$.

Introduce the Weyl algebra

$$W_p := \mathbb{Q}\langle p_1, \dots, p_k, \partial_1, \dots, \partial_k; \partial_i p_j = p_j \partial_i + \delta_{i,j}, 1 \le i, j \le k \rangle,$$

where $\delta_{i,j}$ is one if and only if $i = j$, zero otherwise. Each $\partial_i$ acts on $\mathbb{Q}[t][p]$ as the usual derivation operator with respect to $p_i$. The following relations are easily derived for any two series $U$ and $V$ in $\mathbb{Q}[t][p]$ and any $i \in \{1, \dots, k\}$:

$$\langle p_i U, V \rangle = \langle U, i \partial_i \cdot V \rangle, \quad \langle i \partial_i \cdot U, V \rangle = \langle U, p_i V \rangle.$$

By bilinearity and symmetry, proving these relations reduces indeed to proving the identity

$$(12) \qquad \langle p_i p_\lambda, p_\nu \rangle = \langle p_\lambda, i \partial_i \cdot p_\nu \rangle$$

for any $i, \lambda$, and $\nu$. We prove it for completeness. First, the identity holds if $\nu$ does not involve $i$, both sides being zero. So we continue assuming $i$ appears in $\nu$. Define $\lambda^+$ as the partition obtained by adjoining $i$ to $\lambda$ and consider the integers $r_i$ as in Eq. (2), so that the analog of Eq. (2) for $\lambda^+$ is obtained by incrementing $r_i$. Therefore, $z_{\lambda^+}$ is equal to $z_{\lambda}r_i(i+1)$. Define as well $\nu^-$ as the partition obtained by removing $i$ from $\nu$, so that $\partial_i \cdot p_\nu = s_i p_{\nu^-}$ where $s_i$ denotes the number of occurrences of $i$ in $\nu$. In particular, $s_i = r_i + 1$ if $\nu = \lambda^+$. Next,

$$\langle p_i p_\lambda, p_\nu \rangle = \langle p_{\lambda^+}, p_\nu \rangle = \delta_{\lambda^+, \nu} z_\lambda i (r_i + 1) = i(r_i + 1) \delta_{\lambda, \nu^-} z_\lambda = i(r_i + 1) \langle p_\lambda, p_{\nu^-} \rangle = i \langle p_\lambda, \partial_i \cdot p_\nu \rangle$$

and Eq. (12) is proved. More generally, for any linear differential operator $L$, $\langle L \cdot U, V \rangle = \langle U, L^\dagger \cdot V \rangle$, where the adjoint $L^\dagger$ of $L$ is the result of applying the algebra anti-automorphism of $W_p$ defined by $p_i^\dagger = i \partial_i$ and $\partial_i^\dagger = i^{-1} p_i$. This adjoint operation is an involution. Note that $W_p[t]$ acts on $\mathbb{Q}[t][p]$ as well, but we will restrict the use of this action to right-hand arguments of scalar products.

With Theorem 11, we will only able to prove the correctness of Algorithm 1, but not its completeness. This is why, we now proceed to progressively develop sufficient properties satisfied by intermediate Gröbner bases in calculations for Algorithm 1 to be successful and return correct outputs.

Let $f$ and $g$ be two polynomials in $\mathbb{Q}[p] \setminus \mathbb{Q}$, which we do not want to fix at this point to the polynomial needed for the $k$-regular models provided in Lemma 2. Introduce

$$F := \exp(f) \in \mathbb{Q}[[p]], \quad G := \exp(tg) \in \mathbb{Q}[p][[t]] \cap \mathbb{Q}[t][[p]], \quad S := \langle F, G \rangle \in \mathbb{Q}[[t]].$$

We will write $f_i$ for $\partial_i \cdot f$ and $g_i$ for $\partial_i \cdot g$. Given an element $P \in W_p$, we define its twist $P^\sharp \in W_p[t]$ by

$$(13) \qquad P^\sharp(p_1, \dots, p_k, \partial_1, \dots, \partial_k) = P^\dagger(p_1, \dots, p_k, \partial_1 + tg_1, \dots, \partial_k + tg_k).$$

Finally, let $H \subset \mathbb{Q}(t)[p]$ denote the vector space

$$(14) \qquad H := \sum_{P \in \mathrm{ann}(F)} P^\sharp \cdot \mathbb{Q}(t)[p] = \sum_{P \in \mathrm{ann}(F)^\sharp} P \cdot \mathbb{Q}(t)[p].$$

**Lemma 3.** For any polynomial $h \in H \subset \mathbb{Q}(t)[p]$, the scalar product $\langle F, hG \rangle$ is zero.

*Proof.* If $P \in W_p$ annihilates $F$, then for any $s \in \mathbb{Q}[p]$,

$$(15) \qquad 0 = \langle P \cdot F, sG \rangle = \langle F, P^\dagger \cdot (sG) \rangle = \langle F, (P^\sharp \cdot s)G \rangle,$$

where $P^\sharp(p_1, \dots, p_k, \partial_1, \dots, \partial_k) \in W_p[t]$ is defined by Eq. (13). Note that when $P$ runs over the left ideal of annihilating operators of $F$, denoted $\mathrm{ann}(F)$, the transform $P^\dagger$ runs over the right ideal $\mathrm{ann}(F)^\dagger$, and likewise $P^\sharp$ runs over the right ideal $\mathrm{ann}(F)^\sharp$. The result follows by linearity over $\mathbb{Q}(t)$. $\square$

Introduce the derivation operator $\partial_t$ with respect to $t$ as well as the Weyl algebra

$$W_t := \mathbb{Q}\langle t, \partial_t; \partial_t t = t \partial_t + 1 \rangle.$$

Observe

$$(16) \qquad \partial_t^j \cdot S = \langle F, \partial_t^j \cdot G \rangle = \langle F, g^j G \rangle,$$
basis of the free right module $\eta_0 W_p(t) \oplus \eta_1 W_p(t)$. Consider a Gröbner basis for the right$^3$ module over $W_p(t)$ generated by the $M_i$ with respect to an ordering satisfying:

(1) $\eta_1 > \eta_0$,

(2) $p_i > \partial_j$ for all $i$ and $j$,

(3) $p_k > \cdots > p_1$.

Those elements $\eta_1 Q + \eta_0 R$ of the Gröbner basis satisfying $Q \neq 0$ need not possess the property that $Q$ has a leading monomial larger than the leading monomial of $R$, but as we start from elements $P_i^\dagger$ that make the $M_i$ have the property, the Gröbner basis elements are likely to have it, and the $Q+R$ are the $G_i$ we are looking for. Indeed, this nice situation occurs when $k \le 6$ for all variant models described in Section 3. Because the goal of the calculation is to reveal a zero-dimensional ideal in $\mathbb{Q}(t)[p]$, the module structure over $W_p(t)$ can be replaced with a module structure over $\mathbb{Q}(t)[p]$, that is, one would like to consider only polynomial recombinations of the coefficients of $\eta_1$, without continuing with non-commutative recombinations of the coefficients of $\eta_0$ between generators with zero coefficient with respect to $\eta_1$. In practice, this is achieved by viewing the $M_i$ as elements of a free $\mathbb{Q}(t)[p]$-module with a finite basis consisting of $\eta_1$ and some $\partial^\alpha \eta_1$. For all models considered when $2 \le k \le 6$, this has the nice consequence of speeding up the calculation.

### 5. NO COMPUTATION OF INITIAL CONDITIONS IS NEEDED

For $3 \le k \le 7$, after computing the ODE one readily proves by observation that it possesses the only exponent $n=0$ at $t=0$. Consequently, the series solutions form a 1-dimensional vector space, for which a basis is the singleton family $(R^{(k)}(t))$. Note that the empty graph is $k$-regular for any $k$, implying the identity $R^{(k)}(t) = 1+O(t)$. Converting the ODE to a recurrence relation satisfied by the coefficient sequence $(c_n)_{n \in \mathbb{Z}}$ of any of its series solution $\sum_{n \in \mathbb{Z}} c_n t^n$ and forcing $c_0 = 1$ and $c_n = 0$ for all $n < 0$ therefore uniquely determines all $c_n$ for $n > 0$. This observation generalizes to any of the models of edges and loops presented in Section 3.

So, a complete proof of correctness of the method for computing an ODE satisfied by the scalar product, together with the observation above, makes it unnecessary to apply a resource-consuming calculation of first terms of the series. Nonetheless, we did verify our series solution by direct computation of scalar product, specifically we directly determined $r_n^{(k)}$ for $n \le 1284$ when $k=3$, $n \le 216$ when $k=4$, $n \le 90$ when $k=5$, $n \le 46$ when $k=6$, and $n \le 31$ when $k=7$. Furthermore, McKay provided values for $k=5$ and $n \le 600$, all consistent with our computations.

### 6. CONCLUSION

For each graph class we considered with degrees bounded by 6, it did not require more than 15 minutes to determine the differential equation satisfied the generating function. In contrast, the very same implementation requires weeks to terminate for $k=7$, at least for loopless, simple $k$-regular graphs. The time breaks down as follows: a Gröbner basis can be obtained in 5 seconds (steps a. to f. in Table 1), from which one can predict that reduced forms of scalar products will be confined in dimension 20. Twenty reductions are then performed, for a total duration of almost 172.5 days, which is over 24 weeks (step g.). Successive reductions take longer and longer, the twentieth requiring 2.18e+6 seconds (23.2 days), after which the linear algebra (steps h. and i.) requires only 1.26e+6 seconds (14.6 days). The resulting ODE satisfied by the generating series $R^{(7)}(t)$ for 7-regular graphs has order 20.

Of course the natural question to ask is *What about $k > 7$?* In that respect, ongoing discussions with Hadrien Brochet have led to promising observations that could speed up calculations and hopefully get $k=8$.

Finally, the generating function for all regular graphs is not D-finite. Are there properties of the presented ODEs that can help us understand if the generating function of all regular graphs is differentially algebraic or not, and if so how to find the differential equation?

<footnote>$^3$As Maple only computes Gröbner bases for left structures, the actual computer calculation computes a Gröbner basis for the left module generated by the $Q_i^\dagger \eta_1 + R_i^\dagger \eta_0$, then returns the adjoints $(Q+R)^\dagger$ obtained from the elements $Q\eta_1 + R\eta_0$ of the Gröbner basis satisfying $Q \neq 0$.</footnote>
so that, as a consequence of Lemma 3, any annihilator $Q = \sum_{j=0}^{r} q_j(t) \partial_t^j \in W_t$ of $S$ satisfies

$$0 = Q \cdot S = \langle F, Q \cdot G \rangle = \left\langle F, \sum_{j=0}^{r} q_j g^j G \right\rangle = \left\langle F, \sum_{j=0}^{r} q_j (g^j + \ell_j) G \right\rangle$$

for any polynomials $\ell_j$ that are elements of the vector space $H$ defined by Eq. (14). In what follows, for each $g^j$ we (implicitly) obtain $\ell_j$ in such a way that the computed $g^j + \ell_j$ is “reduced” and confined in a finite-dimensional $\mathbb{Q}(t)$-vector space. This makes it possible to derive the $q_j$. The procedure is therefore to deal with Eq. (16) for each $j$ separately, by reducing the coefficient $g^j$ modulo $H$.

Although, as we will see, we will only be able to reduce by a subspace of $H$, we continue our analysis by expressing the space $H$ as a finite sum of spaces.

**Lemma 4.** The vector space $H$ is the sum $\sum_{i=1}^{\ell} L_i \cdot \mathbb{Q}(t)[p]$ for any finite family $\{L_i\}_{i=1}^{\ell}$ generating $\mathrm{ann}(F)^{\sharp}$.

*Proof.* The finite sum $\tilde{H} := \sum_{i=1}^{\ell} L_i \cdot \mathbb{Q}(t)[p]$ is a subspace of $H$. Writing any $P$ of $\mathrm{ann}(F)^{\sharp}$ in the form $P = \sum_{i=1}^{\ell} L_i U_i$ yields the inclusion of the space $H$ into $\tilde{H}$, and thus the equality $\tilde{H} = H$. $\square$

Eq. (15) holds in particular for $P = P_i := i(\partial_i - f_i)$, in which case $P^{\sharp}$ is given as $P_i^{\sharp}$ in Eq. (19).

To define the reduction that was announced, we proceed by exchanging the generating family $\{P_i^{\sharp}\}$ of $\mathrm{ann}(F)^{\sharp}$ for a family $\{G_i\}_{i=1}^{\ell}$ satisfying the property that any term $cm$ to be reduced ($c$ a coefficient, $m$ a monomial) will be obtained for some $(j, s) \in \{1, \dots, \ell\} \times \mathbb{Q}(t)[p]$ as the leading monomial of $G_j \cdot s$, where leading monomials are decided by some monomial ordering of $\mathbb{Q}(t)[p]$ that is compatible with the choice of the family $\{G_i\}_{i=1}^{\ell}$. To make this possible, we ensure that $G_j = m_j + \dots \in W_p(t)$ for a monomial $m_j$ in $p$, with the property that, for any $\tilde{s} \in \mathbb{Q}(t)[p]$, the leading monomial of $m_j \tilde{s}$ is larger than the leading monomial of $(G_j - m_j) \cdot \tilde{s}$. In practice, the polynomial $s$ used to reduce $cm$ will be set to the term $cm/m_j$, so that $m$ is reduced into $m - G_j \cdot (cm/m_j)$. Observing that only finitely many monomials are divisible by none of the $m_j$ will then ensure the wanted confinement in finite dimension.

The following lemma describes a situation in which a skew polynomial $G$ has the property we require from the $G_j$. For future reference, we give a name to this property.

**Definition 5.** A skew polynomial $G \in W_p(t)$ is said to be dominant if it is of the form $G = m + R$ for a non-zero monomial $m \in \mathbb{Q}[p]$ and some rest $R$ involving only monomials $p^\alpha \partial_p^\beta$ for which $\sum_{i=1}^k (\alpha_i - \beta_i)$ is less than the total degree of $m$.

**Lemma 6.** Let $G \in W_p(t)$ be dominant. Fix a monomial ordering on $\mathbb{Q}(t)[p]$ that is graded by total degree. Then, for any non-zero polynomial $s$, the leading monomial of $G \cdot s$ is the product of $m$ with the leading monomial of $s$.

*Proof.* The quantity $\sum_{i=1}^k (\alpha_i - \beta_i)$ is what is added to the degree of any monomial $q$ when applying $p^\alpha \partial_p^\beta$ to it. So because $G$ is dominant and the ordering is graded by total degree, the leading monomial of $G \cdot s$ is the product of $mq$. The result then follows from the general properties of monomial orderings. $\square$

In general, we do not know how to ensure the existence of a family $\{G_j\}_{j=1}^{\ell}$ consisting of dominant $G_j$, but for $k$-regular graphs, a module Gröbner basis calculation will in practice compute such a family for $k$ up to 7, as we will show in Proposition 9. To describe how to engineer the construction of such a family, we now introduce a few compatible monomial orderings for the structures that we will use.

**Definition 7.** (1) Let $\prec$ denote a monomial ordering on $W_p(t)$ that compares the $p_i$ by a total degree order and that eliminates $p$ by making $p_i$ lexicographically higher than $\partial_j$ for all $i$ and $j$, Here, lexicographically higher means $p_i \succ \partial_j^n$ for all $i, j$, and $n$.

(2) Let $\prec_h$ denote the monomial ordering on the free right module $\eta_0 W_p(t) \oplus \eta_1 W_p(t)$ that eliminates $\eta_1$ by making $\eta_1$ lexicographically higher than $\eta_0$ and by sorting monomials in the same $\eta_i$ by means of $\prec$. Here, $\eta_0$ and $\eta_1$ are new names denoting elements of a basis and lexicographically higher means $p^\alpha \partial^\beta \eta_1 \succ_h p^\gamma \partial^\delta \eta_0$ for all $\alpha, \beta, \gamma$, and $\delta$.

(3) Let $\prec_p$ denote the monomials ordering on $\mathbb{Q}(t)[p]$ that is induced by $\prec$. This is just notation to stress the polynomial situation, as we could use the symbol $\prec$ as well.
# 7. AUTHOR CONTRIBUTIONS STATEMENT

Frédéric Chyzak: Conceptualization, methodology, software, writing. Marni Mishna: Conceptualization, writing.

# 8. ACKNOWLEDGEMENTS

FC's work was supported in part by the French ANR grant De rerum natura (ANR-19-CE40-0018) and by the French-Austrian ANR-FWF grant EAGLES (ANR-22-CE91-0007 & FWF-I-6130-N). MM's work was supported by Discovery Grant RGPIN-2017-04157 from the National Science and Engineering Research Council of Canada. The authors are grateful to Brendan McKay for continued interest in the problem, and for providing some counting sequence data for comparison purposes.

# REFERENCES

[1] Alin Bostan, Shaoshi Chen, Frédéric Chyzak, and Ziming Li. Complexity of creative telescoping for bivariate rational functions. In *ISSAC'10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation*, pages 203–210, New York, NY, USA, 2010. ACM.

[2] Alin Bostan, Frédéric Chyzak, Pierre Lairez, and Bruno Salvy. Generalized Hermite reduction, creative telescoping and definite integration of D-finite functions. In Éric Schost, editor, *ISSAC'18*, pages 95–102. ACM Press, 2018.

[3] Frédéric Chyzak, Marni Mishna, and Bruno Salvy. Effective scalar products of D-finite symmetric functions. *Journal of Combinatorial Theory. Series A*, 112(1):1–43, 2005.

[4] Ira Gessel. Enumerative applications of symmetric functions. *Séminaire Lotharingien de Combinatoire* [electronic only], 17:B17a–17, 1987. Publisher: Universität Wien, Fakultät für Mathematik.

[5] Ira M. Gessel. Symmetric functions and P-recursiveness. *Journal of Combinatorial Theory. Series A*, 53(2):257–285, 1990.

[6] I. P. Goulden, D. M. Jackson, and J. W. Reilly. The Hammond series of a symmetric function and its application to P-recursiveness. *Society for Industrial and Applied Mathematics. Journal on Algebraic and Discrete Methods*, 4(2):179–193, 1983.

[7] Harald Gröpp. Enumeration of regular graphs 100 years ago. In *Discrete Mathematics*, volume 101, pages 73–85. 1992. ISSN: 0012-365X, 1872-681X Journal Abbreviation: Discrete Math.

[8] L. Lipshitz. D-finite power series. *Journal of Algebra*, 122(2):353–373, 1989.

[9] Marni Mishna. Automatic enumeration of regular objects. *Journal of Integer Sequences*, 10(5):Article 07.5.5, 18, 2007.

[10] Marni Mishna. Regularity in weighted graphs a symmetric function approach. *Contributions to Discrete Mathematics*, 13(2):32–44, 2018.

[11] R. C. Read. The enumeration of locally restricted graphs. I. *The Journal of the London Mathematical Society*, 34:417–436, 1959.

[12] Bruce E. Sagan. *The symmetric group*, volume 203 of *Graduate Texts in Mathematics*. Springer-Verlag, New York, second edition, 2001. Representations, combinatorial algorithms, and symmetric functions.

[13] R. P. Stanley. Differentiably finite power series. *European Journal of Combinatorics*, 1(2):175–188, 1980.

[14] Nicholas Wormald. Asymptotic enumeration of graphs with given degree sequence. In *Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018*, pages 3245–3264. World Scientific, 2018.

# APPENDIX A. DIFFERENTIAL EQUATIONS AND RECURRENCES RELATIONS

The following table gathers information related to computations we performed for a list of models:

* parameters “edges”, “loops”, and *k*’s are as described in Section 3;

* the obtained ODE has order provided in column $\partial_t$ and its polynomial coefficients have degrees bounded by the number in column *t*;

* a recurrence on the number of graphs of size *n* has order provided in column $\partial_n$ and its polynomial coefficients have degrees bounded by the number in column *n*;

* the corresponding calculation is done in the time of column “time”, measured in seconds.
For each $i$, write $P_i^\sharp = Q_i(p) + R_i(p, \partial)$, where $Q_i$ does not involve any $\partial_j$ and each monomial of $R_i$ involves at least one $\partial_j$. Then, consider $M_i := \eta_1 Q_i + \eta_0 R_i$. Consider a Gröbner basis for the right$^3$ module over $W_p(t)$ generated by the $M_i$ with respect to $\prec_\eta$. Those elements $\eta_1 Q + \eta_0 R$ of the Gröbner basis satisfying $Q \neq 0$ need not make $Q + R$ dominant by general properties of Gröbner bases, but as we start from the dominant elements $P_i^\sharp$, the Gröbner basis elements can be hoped to make the $Q + R$ dominant, at least if the Gröbner basis calculation does not modify too much the higher monomials of the input polynomials. Indeed, we are in the nice situation that the $Q + R$ are the $G_i$ we are looking for when $k \le 6$ for all variant models described in Section 3 as well as for the case of regular simple graphs when $k = 7$. Because the goal of the calculation is to reveal a zero-dimensional ideal in $\mathbb{Q}(t)[p]$, the module structure over $W_p(t)$ can be replaced with a module structure over $\mathbb{Q}(t)[p]$, that is, one would like to consider only polynomial recombinations guided by the coefficients of $\eta_1$, without continuing with non-commutative recombinations of the coefficients of $\eta_0$ between generators with zero coefficient with respect to $\eta_1$. This is achieved by viewing the $M_i$ as elements of a free $\mathbb{Q}(t)[p]$-module with a finite basis consisting of $\eta_1$ and some $\partial^\alpha \eta_0$, for the same ordering $\prec_h$. For all models considered when $2 \le k \le 6$, this has the nice consequence of speeding up the calculation. For the single model we considered with $k = 7$ we therefore directly used this improvement.

**Proposition 8.** The operators $G_i$ obtained at Step e. of Algorithm 1 are such that $\sum_{i=1}^\rho G_i W_p(t)$ is a subideal of $\mathrm{ann}(F)^\sharp$, including the possible degenerate case $0$ obtained if $\rho = 0$.

*Proof.* Given a graph model $(e, l, K)$, Step a. implements the formula announced by Lemma 2, so that $\langle \exp(f), \exp(tg) \rangle$ is the exponential generating function of the model and $F$ is fixed to $\exp(f)$. Next, Step b. computes generators of the right $W_p(t)$-ideal $\mathrm{ann}(F)^\sharp$ because the map $\sharp$ is a linear anti-homomorphism from $W_p$ to $W_p(t)$ and the $P_i$ generate the left $W_p$-ideal $\mathrm{ann}(F)$. Steps c. to e. produce operators $G_i$ that are elements of $\mathrm{ann}(F)^\sharp$. This proves the result. $\square$

**Proposition 9.** For each model in Table 2:

(1) the elements $Q_i(p) + R_i(p, \partial)$ of the Gröbner basis obtained at Step e. of Algorithm 1 are all dominant and so satisfy the property of $G$ in Lemma 6, for $m = Q_i(p)$.

(2) the ideal $I$ generated by the $Q_i(p)$ at Step f. has dimension zero.

*Proof.* For each model, the proof is by inspection after computing the Gröbner basis at Step d.: testing Point (1) consists in comparing each monomial of $Q_i + R_i$ with the leading monomial $m_i$ of $Q_i$; testing Point (2) is done by computing the dimension of the commutative polynomial ideal by a classical algorithm, after observing that the commutative polynomials $Q_i$ obtained as parts of the $Q_i + R_i$ are already a Gröbner basis for the ordering induced on $\mathbb{Q}(t)[p]$ by the ordering $\prec_\eta$ used at Step d. $\square$

The polynomials $G_i = Q_i + R_i$ obtained at Step e. of Algorithm 1 will be used to reduce polynomials to a finite-dimensional vector space at Step g. So we first analyse this reduction separately. To this end, we stress a possibly confusing fact: although $\mathrm{ann}(F)^\sharp$ is a right-module, we make it act to the left of polynomials during reductions.

**Proposition 10.** The reduction algorithm, Algorithm 2, terminates if the ideal $I$ generated by the leading monomials with respect to $\prec$ of the dominant inputs $G_i$ is zero-dimensional. It returns a polynomial $\tilde{s} \in \mathbb{Q}(t)[p]$ whose monomials are under the stairs of $I$ with respect to $\prec_p$. The difference $s - \tilde{s}$ is in $\sum_{i=1}^\rho G_i \cdot \mathbb{Q}(t)[p]$, and therefore it is an element of the vector space $H$ defined by Eq. (14).

*Proof.* The term $t$ at Step e. is chosen so that leading terms satisfy:

$$ \mathrm{lt}(G_j \cdot t) = \mathrm{lt}(\mathrm{lt}(G_j) \cdot t) = \mathrm{lt}(c_j m_j \cdot t) = \mathrm{lt}(c_j m_j t) = \mathrm{lt}(cm) = cm, $$

where the first equality is by the assumed dominant character of $G_j$ and by Lemma 6, and where the third equality is because $m_j$ does not involve $\partial$. So all monomials appearing in the difference $s - G_j \cdot t$ and susceptible of reduction by the $m_i$ are less than $m$. Because of the 0-dimensionality of $I$, the recursive calls to $\mathrm{red}(\cdot)$ terminate. The output has no monomial reducible by any $m_i$, hence all its monomials are under the stairs of $I$. Finally, each $G_j \cdot t$ considered by some recursive call is in $H$, hence so is $\tilde{s} - s$. $\square$

<footnote>$^3$As Maple only computes Gröbner bases for left structures, the actual computer calculation computes a Gröbner basis for the left module generated by the $Q_i^\dagger \eta_1 + R_i^\dagger \eta_0$, then returns the adjoints $(Q + R)^\dagger$ obtained from the elements $Q\eta_1 + R\eta_0$ of the Gröbner basis satisfying $Q \neq 0$.</footnote>
<table><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂</th><th>n</th><th>∂<sub>n</sub></th><th>time</th></tr></thead><tbody><tr><td>se</td><td>ll</td><td>[2]</td><td>2</td><td>1</td><td>1</td><td>3</td><td>0.36</td></tr><tr><td>me</td><td>ll</td><td>[2]</td><td>2</td><td>1</td><td>1</td><td>3</td><td>0.36</td></tr><tr><td>se</td><td>lh</td><td>[2]</td><td>3</td><td>1</td><td>1</td><td>4</td><td>0.38</td></tr><tr><td>me</td><td>lh</td><td>[2]</td><td>3</td><td>1</td><td>1</td><td>4</td><td>0.39</td></tr><tr><td>se</td><td>la</td><td>[2]</td><td>2</td><td>1</td><td>1</td><td>3</td><td>0.34</td></tr><tr><td>me</td><td>la</td><td>[2]</td><td>2</td><td>1</td><td>1</td><td>3</td><td>0.33</td></tr><tr><td>se</td><td>ll</td><td>[3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.38</td></tr><tr><td>me</td><td>ll</td><td>[3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.46</td></tr><tr><td>se</td><td>lh</td><td>[3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.38</td></tr><tr><td>me</td><td>lh</td><td>[3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.45</td></tr><tr><td>se</td><td>la</td><td>[3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.47</td></tr><tr><td>me</td><td>la</td><td>[3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.5</td></tr><tr><td>se</td><td>ll</td><td>[2, 3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.48</td></tr><tr><td>me</td><td>ll</td><td>[2, 3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.48</td></tr><tr><td>se</td><td>lh</td><td>[2, 3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.48</td></tr><tr><td>me</td><td>lh</td><td>[2, 3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.51</td></tr><tr><td>se</td><td>la</td><td>[2, 3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.47</td></tr><tr><td>me</td><td>la</td><td>[2, 3]</td><td>11</td><td>2</td><td>2</td><td>12</td><td>0.46</td></tr><tr><td>se</td><td>ll</td><td>[4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.55</td></tr><tr><td>me</td><td>ll</td><td>[4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.57</td></tr><tr><td>se</td><td>lh</td><td>[4]</td><td>30</td><td>3</td><td>3</td><td>31</td><td>0.81</td></tr><tr><td>me</td><td>lh</td><td>[4]</td><td>29</td><td>3</td><td>3</td><td>30</td><td>0.73</td></tr><tr><td>se</td><td>la</td><td>[4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.67</td></tr><tr><td>me</td><td>la</td><td>[4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.57</td></tr><tr><td>se</td><td>ll</td><td>[2, 4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.57</td></tr><tr><td>me</td><td>ll</td><td>[2, 4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.57</td></tr><tr><td>se</td><td>lh</td><td>[2, 4]</td><td>30</td><td>3</td><td>3</td><td>31</td><td>0.79</td></tr><tr><td>me</td><td>lh</td><td>[2, 4]</td><td>29</td><td>3</td><td>3</td><td>30</td><td>0.76</td></tr><tr><td>se</td><td>la</td><td>[2, 4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.67</td></tr><tr><td>me</td><td>la</td><td>[2, 4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.68</td></tr><tr><td>se</td><td>ll</td><td>[3, 4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.7</td></tr><tr><td>me</td><td>ll</td><td>[3, 4]</td><td>13</td><td>2</td><td>2</td><td>14</td><td>0.57</td></tr><tr><td>se</td><td>lh</td><td>[3, 4]</td><td>30</td><td>3</td><td>3</td><td>31</td><td>0.8</td></tr><tr><td>me</td><td>lh</td><td>[3, 4]</td><td>29</td><td>3</td><td>3</td><td>30</td><td>0.77</td></tr><tr><td>se</td><td>la</td><td>[3, 4]</td><td>13</td><td>2</td><td>2</td><td>14</td><td>0.7</td></tr><tr><td>me</td><td>la</td><td>[3, 4]</td><td>14</td><td>2</td><td>2</td><td>15</td><td>0.73</td></tr><tr><td>se</td><td>ll</td><td>[5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.29</td></tr><tr><td>me</td><td>ll</td><td>[5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>3.84</td></tr><tr><td>se</td><td>lh</td><td>[5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>5.39</td></tr><tr><td>me</td><td>lh</td><td>[5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.53</td></tr><tr><td>se</td><td>la</td><td>[5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.27</td></tr><tr><td>me</td><td>la</td><td>[5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>3.4</td></tr><tr><td>se</td><td>ll</td><td>[2, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.9</td></tr><tr><td>me</td><td>ll</td><td>[2, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.64</td></tr><tr><td>se</td><td>lh</td><td>[2, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>7.03</td></tr><tr><td>me</td><td>lh</td><td>[2, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>6.31</td></tr><tr><td>se</td><td>la</td><td>[2, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.37</td></tr><tr><td>me</td><td>la</td><td>[2, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.74</td></tr><tr><td>se</td><td>ll</td><td>[3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.87</td></tr><tr><td>me</td><td>ll</td><td>[3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.76</td></tr><tr><td>se</td><td>lh</td><td>[3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>6.96</td></tr><tr><td>me</td><td>lh</td><td>[3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>6.63</td></tr><tr><td>se</td><td>la</td><td>[3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.89</td></tr><tr><td>me</td><td>la</td><td>[3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.89</td></tr></tbody></table>

<table><caption>TABLE 3. Results of calculations on the models described in Section 3. All timings obtained on the same computer (Dell, Precision Mobile 7550, with i9 processor and 64 GB of RAM).</caption><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂<sub>t</sub></th><th>n</th><th>∂<sub>n</sub></th><th>time</th></tr></thead><tbody><tr><td>se</td><td>ll</td><td>[4, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.69</td></tr><tr><td>me</td><td>ll</td><td>[4, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.61</td></tr><tr><td>se</td><td>lh</td><td>[4, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>7.31</td></tr><tr><td>me</td><td>lh</td><td>[4, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>6.6</td></tr><tr><td>se</td><td>la</td><td>[4, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.7</td></tr><tr><td>me</td><td>la</td><td>[4, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>4.67</td></tr><tr><td>se</td><td>ll</td><td>[1, 3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>2.62</td></tr><tr><td>me</td><td>ll</td><td>[1, 3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>2.56</td></tr><tr><td>se</td><td>lh</td><td>[1, 3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>3.8</td></tr><tr><td>me</td><td>lh</td><td>[1, 3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>3.64</td></tr><tr><td>se</td><td>la</td><td>[1, 3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>2.87</td></tr><tr><td>me</td><td>la</td><td>[1, 3, 5]</td><td>125</td><td>6</td><td>6</td><td>126</td><td>2.68</td></tr><tr><td>se</td><td>ll</td><td>[6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>99.23</td></tr><tr><td>me</td><td>ll</td><td>[6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>87.31</td></tr><tr><td>se</td><td>lh</td><td>[6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>485.57</td></tr><tr><td>me</td><td>lh</td><td>[6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>497.67</td></tr><tr><td>se</td><td>la</td><td>[6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>97.83</td></tr><tr><td>me</td><td>la</td><td>[6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>87.62</td></tr><tr><td>se</td><td>ll</td><td>[2, 6]</td><td>142</td><td>6</td><td>6</td><td>143</td><td>91.72</td></tr><tr><td>me</td><td>ll</td><td>[2, 6]</td><td>142</td><td>6</td><td>6</td><td>143</td><td>88.8</td></tr><tr><td>se</td><td>lh</td><td>[2, 6]</td><td>416</td><td>10</td><td>10</td><td>417</td><td>604.93</td></tr><tr><td>me</td><td>lh</td><td>[2, 6]</td><td>416</td><td>10</td><td>10</td><td>417</td><td>584.91</td></tr><tr><td>se</td><td>la</td><td>[2, 6]</td><td>142</td><td>6</td><td>6</td><td>143</td><td>87.82</td></tr><tr><td>me</td><td>la</td><td>[2, 6]</td><td>142</td><td>6</td><td>6</td><td>143</td><td>85.04</td></tr><tr><td>se</td><td>lh</td><td>[3, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>145.43</td></tr><tr><td>me</td><td>lh</td><td>[3, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>145.26</td></tr><tr><td>se</td><td>la</td><td>[3, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>814.86</td></tr><tr><td>me</td><td>la</td><td>[3, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>860.93</td></tr><tr><td>se</td><td>lh</td><td>[3, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>137.03</td></tr><tr><td>me</td><td>la</td><td>[3, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>146.39</td></tr><tr><td>se</td><td>ll</td><td>[4, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>143.17</td></tr><tr><td>me</td><td>ll</td><td>[4, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>143.94</td></tr><tr><td>se</td><td>lh</td><td>[4, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>792.33</td></tr><tr><td>me</td><td>lh</td><td>[4, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>817.3</td></tr><tr><td>se</td><td>la</td><td>[4, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>155.22</td></tr><tr><td>me</td><td>la</td><td>[4, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>145.1</td></tr><tr><td>se</td><td>ll</td><td>[5, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>145.46</td></tr><tr><td>me</td><td>ll</td><td>[5, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>140.28</td></tr><tr><td>se</td><td>lh</td><td>[5, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>788.6</td></tr><tr><td>me</td><td>lh</td><td>[5, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>806.88</td></tr><tr><td>se</td><td>la</td><td>[5, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>140.4</td></tr><tr><td>me</td><td>la</td><td>[5, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>144.45</td></tr><tr><td>se</td><td>ll</td><td>[2, 4, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>159.43</td></tr><tr><td>me</td><td>ll</td><td>[2, 4, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>160.11</td></tr><tr><td>se</td><td>lh</td><td>[2, 4, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>673.59</td></tr><tr><td>me</td><td>lh</td><td>[2, 4, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>692.73</td></tr><tr><td>se</td><td>la</td><td>[2, 4, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>172.37</td></tr><tr><td>me</td><td>la</td><td>[2, 4, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>157.62</td></tr><tr><td>se</td><td>ll</td><td>[1, 2, 3, 4, 5, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>117.07</td></tr><tr><td>me</td><td>ll</td><td>[1, 2, 3, 4, 5, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>113.62</td></tr><tr><td>se</td><td>lh</td><td>[1, 2, 3, 4, 5, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>495.58</td></tr><tr><td>me</td><td>lh</td><td>[1, 2, 3, 4, 5, 6]</td><td>425</td><td>10</td><td>10</td><td>426</td><td>508.73</td></tr><tr><td>se</td><td>la</td><td>[1, 2, 3, 4, 5, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>118.23</td></tr><tr><td>me</td><td>la</td><td>[1, 2, 3, 4, 5, 6]</td><td>145</td><td>6</td><td>6</td><td>146</td><td>113.11</td></tr><tr><td>se</td><td>ll</td><td>[7]</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>1.49000e+07</td></tr></tbody></table>
**Input:** a graph model $(e, l, K)$,
where $e \in \{\text{'se'}, \text{'me'}\}$, $l \in \{\text{'ll'}, \text{'la'}, \text{'lh'}\}$, $K \subset \mathbb{N}_{>0}$.

**Output:** an operator of minimal order in $\partial_t$
that cancels the exponential generating function of the model.

a. Set $k = \max K$, then compute $f$ and $g$ by the formulas

$$ (17) \qquad f = \sum_{i=1}^{k} ((-1)^{i+1} \delta_{e,\text{'se'}} + \delta_{e,\text{'me'}}) \left( \frac{p_i^2}{2i} + \delta_{l,\text{'lh'}} \frac{p_i}{i} \right) - (-1)^{\delta_{l,\text{'la'}}} \sum_{i=1}^{\lfloor k/2 \rfloor} ((-1)^{i+1} \delta_{e,\text{'se'}} + \delta_{e,\text{'me'}}) \frac{p_{2i}}{2i}, $$

$$ (18) \qquad g = \sum_{j \in K} \sum_{\lambda \vdash j} \frac{p_\lambda}{z_\lambda}, $$

where the expression $\delta_{x,y}$ is equal to 1 if $x = y$ and to 0 otherwise.

b. Get generators of the right $W_p(t)$-ideal $\text{ann}(F)^\sharp$ by computing $P_i^\sharp$ for $1 \le i \le k$ by the formula

$$ (19) \qquad P_i^\sharp = (i\partial_i - if_i)^\sharp = p_i - if_i(\partial_1 + tg_1, 2(\partial_2 + tg_2), \dots, k(\partial_k + tg_k)). $$

Here, the right-hand side is obtained by the non-commutative substitution of $p_1$ with $\partial_1 + tg_1$, of $p_2$ with $2(\partial_2 + tg_2)$, ..., of $p_k$ with $k(\partial_k + tg_k)$, in the polynomial $f_i = f_i(p_1, \dots, p_k)$.

c. Transform each $P_i^\sharp$ by the map

$$ \sum_{\alpha} c_{\alpha} \partial^{\alpha} \mapsto c_0 \eta_1 + \sum_{\alpha \neq 0} c_{\alpha} \partial^{\alpha} \eta_0 $$

to get a system of generators of a right $\mathbb{Q}(t)[p]$-module with basis $\{\eta_1\} \cup \{\partial^\alpha \eta_0\}_\alpha$. Here, $\alpha$ ranges in the finite set of non-zero exponents involved in the $P_i^\sharp$.

d. Compute a Gröbner basis of this right module for an ordering $\prec_\eta$ that makes $\eta$ lexico-graphically higher than $p$ and $p$ lexicographically higher than $\partial$, using Definition 7.

e. Obtain elements $G_1, \dots, G_\rho$ of $W_p(t)$ by setting $\eta_1 = \eta_0 = 1$ in those elements of the Gröbner basis that involve $\eta_1$ with a non-zero coefficient, then write each $G_i$ in the form $Q_i(p) + R_i(p, \partial)$ where each monomial of $R_i$ involves at least one $\partial_j$.

f. If the polynomial ideal $I = (Q_1, \dots, Q_\rho)$ of $\mathbb{Q}(t)[p]$ has positive dimension, then return 'FAIL', else determine the monomials $p^{\beta_1}, \dots, p^{\beta_\delta}$ under the stair of $I$ with respect to $\prec_p$.

g. Set $\check{g}_0 = 1$, then for $i$ from 2 to $\delta$, set $\check{g}_i = \text{red}(g\check{g}_{i-1} + \partial_t \cdot \check{g}_{i-1}, (G_i)_{i=1}^\rho, \prec)$.

h. Compute the matrix $M$ with rows indexed by $0 \le i \le \delta$ and columns indexed by $1 \le j \le \delta$, whose entry at position $(i, j)$ is the coefficient of $p^{\beta_j}$ in $G_i$.

i. Compute a basis of the left kernel of $M$, then combine its elements to obtain a non-zero row vector $(q_0, \dots, q_\delta) \in \mathbb{Q}(t)^{\delta+1}$ with maximal number of zeros to the right.

j. Return $q_0 + q_1 \partial_t + \dots + q_\delta \partial_\delta$.

**ALGORITHM 1.** Outline of the method. Uses the reduction $\text{red}(\cdot)$ of **ALGORITHM 2**.

We note that the choice of $\prec_p$ to be induced by $\prec_h$ and that $\prec_h$ reduces to a graded order on monomials in $p$ is not for termination, but for efficiency.

**Theorem 11.** *Algorithm 1 is correct, that is, if it terminates, then either this is by giving up, returning 'FAIL' at Step f., or this is by outputting at Step j. a differential equation that annihilates the scalar product S.*
**Input:** a polynomial $s \in \mathbb{Q}(t)[p]$ to be reduced and dominant operators $G_1, \dots, G_\rho$ of $W_p(t)$.

**Output:** a polynomial $\check{s} \in \mathbb{Q}(t)[p]$.

a. For each $i$, set $m_i$ to the leading monomial of $G_i$.

b. If no monomial of $s$ is divisible by any of the $m_i$, return $s$.

c. Set $m$ to the maximal monomial in $s$ that is divisible by some $m_i$ and choose $j$ such that $m_j$ divides $m$.

d. Set $c$ to the coefficient of $m$ in $s$ and $c_j$ to the leading coefficient of $G_j$.

e. Set $t$ to the term $\frac{c}{c_j} \frac{m}{m_j}$ and return $\text{red}(s - G_j \cdot t, (G_i)_{i=1}^\rho)$.

<caption>ALGORITHM 2. Reduction $\text{red}(\cdot)$ used by ALGORITHM 1.</caption>

*Proof.* By Proposition 8, we obtain that, after Step e., $\sum_{i=1}^\rho G_i W_p(t)$-is a subideal of $\text{ann}(F)^\sharp$. So, if the algorithm terminates without returning 'FAIL' at Step f., then the ideal $I$, which is generated by the $Q_i = G_i - R_i$, must have dimension 0. Proposition 10 shows that $\text{red}(\cdot)$ modifies its input $s$ by adding to it an element $\check{s} - s$ of the vector space $H$ defined by Eq. (14). So, Step g. is an incremental calculation of the $\partial_t^i \cdot S$ defined by Eq. (16), as justified by Lemma 3. The final steps compute a non-trivial $\mathbb{Q}(t)$-linear relation between the $\partial_t^i \cdot S$. The corresponding differential equation is finally returned. $\square$

We emphasize that we do not claim that the case of 0-dimensionality of the ideal $I$ at Step f. implies that termination of the subsequent steps. In fact, this is just a necessary condition for those steps to be well defined. A sufficient condition for termination, knowing that the dimension of $I$ is 0, is that for each $i$ in $\{1, \dots, \rho\}$ the (total) degree of $Q_i$ in $p$ is larger than the (partial) degree of $R_i$ in $p$ (cf. Lemma 6). This is a condition that we have observed in all of our experiments.

Because we observe that our implementation of Algorithm 1 terminates and outputs a differential equation on the models listed in Table 2, we get the following corollary.

**Corollary 12.** For each model in Table 2, there exist:

(1) a linear differential equation annihilating the generating function of the model, with order given in column '∂t';

(2) a linear recurrence equation annihilating the enumerative sequence of the model, with order given in column '∂n minimized', the latter being the minimal order of a recurrence if it is not starred.

*Proof.* Only the minimality of recurrence order requires a proof: this is by the correctness of van Hoeij's LREtools[MinimalRecurrence] implementation, whose proven method is described in his student Zhou's PhD thesis [19, Chapter 6]. $\square$

## 5. NO COMPUTATION OF INITIAL CONDITIONS IS NEEDED

For all classes, after computing the ODE one readily proves by observation that it possesses the only exponent $n = 0$ at $t = 0$. Consequently, the series solutions form a 1-dimensional vector space, for which a possible basis is the family with only entry our combinatorial series, e.g., the singleton family $(R^{(k)}(t))$ in the $k$-regular case. Note that the empty graph is $k$-regular for any $k$, implying the identity $R^{(k)}(t) = 1 + O(t)$, and an analogue result holds for all degree sets $K$. Converting the ODE to a recurrence relation satisfied by the coefficient sequence $(c_n)_{n \in \mathbb{Z}}$ of any of its series solution $\sum_{n \in \mathbb{Z}} c_n t^n$ and forcing $c_0 = 1$ and $c_n = 0$ for all $n < 0$ therefore uniquely determines all $c_n$ for $n > 0$. This observation generalizes to any of the models of edges and loops presented in Section 3.

So, a complete proof of correctness of the method for computing an ODE satisfied by the scalar product, together with the observation above, makes it unnecessary to apply a resource-consuming calculation of first terms of the series. Nonetheless, for all the classes we did verify our series solution by direct computation of scalar product. For example for simple $k$-regular graphs, we directly determined $r_n^{(k)}$ for $n \le 1284$ when $k = 3$, $n \le 216$ when $k = 4$, $n \le 90$ when $k = 5$, $n \le 46$ when $k = 6$, and $n \le 31$ when $k = 7$. Furthermore, McKay provided values for $k = 5$ and $n \le 600$, all consistent with our computations.
## 6. MINIMAL RECURRENCES

Table 2 shows that in many instances the obtained ODE has low order and high degree, leading to a recurrence of high order and low degree. This is one possible motivation for searching for recurrences of lower orders. To this end, we have used Mark van Hoeij’s Maple implementation of his algorithm to reduce the order of recurrences satisfied by a specific solution to a given initial recurrence$^4$, which is available in Maple as `LREtools[MinimalRecurrence]`.

For roughly half of the models, we could reduce the order. For a small quarter of the list, minimizing was too much calculation. Fortunately in those cases, the generating series is even, the initial recurrence relates every second term of the sequence, and a change of indexes to consider the sub-sequence of even terms led to a recurrence that Maple could reduce. These are marked with a star in the table.

However, all models with $k = \max K = 6$ and loops described by $l = ‘lh’, no recurrence of lower order could be found.

In all relevant cases, the recurrence of reduced order is larger than the initial recurrence, as the degree increase outbalances the order decrease. This is amplified by an increase in the size of integers that occur in the reduced recurrence. For example, for the model defined by $e = ‘se’, l = ‘ll$, $K = \{6\}$, the product “degree × order” is multiplied by 4.8, raising from 876 to 4176, while the length of the longest integer raises from 50 to 236. As a consequence, computing first terms as with Maple’s command `gfun[rectoproc]` results in slower calculations with the reduced recurrence: for the same example, computing up to the 1000th term takes more than five times as much with the reduced recurrence, with times raising from below 30 seconds to above 150 seconds.

## 7. CONCLUSION

7.1. **Computational considerations.** For each graph class we considered with degrees bounded by 6, it did not require more than 10 minutes to determine the differential equation satisfied the generating function. In contrast, for models with $k = \max K = 7$, the very same implementation requires hours to terminate (between 4.5 and ≃ 30). For example, for the model defined by $e = ‘se’, l = ‘ll$, $K = \{7\}$, the time breaks down as follows: a Gröbner basis that supports the reduction by the vector space $H$ of Eq. (14). can be obtained in less than 1 hour (Steps a. to f. in Algorithm 1). From this, one can predict that reduced forms of scalar products will be confined in dimension 20. Twenty successive reductions are then performed, taking longer and longer, for a total duration of about 9 hours (Step g.). After this, the linear algebra (Steps h. and i.) is comparatively fast. The resulting ODE satisfied by the generating series $R^{(7)}(t)$ for 7-regular graphs has order 20.

Of course the natural question to ask is *What about $k > 7$?* In that respect, ongoing discussions with Hadrien Brochet have led to promising observations that could speed up calculations and hopefully get $k = 8$.

Finally, the generating function for all regular graphs is not D-finite. Are there properties of the presented ODEs that can help us understand if the generating function of all regular graphs is differentially algebraic or not, and if so how to find the differential equation?

7.2. **Combinatorial considerations.** We have used symmetric function identities to get an expression in the power-sum basis for the graph generating functions. In fact, there is a well developed combinatorial theory to get these expressions directly using cycle index series, and other machinery from Species theory. The underlying combinatorial framework is developed and rigourous in [9] and is interpreted for this context in [11]. Roughly, this means that we can express the generating functions of a wide family of combinatorial objects such as hypergraphs, and weighted graphs under restrictions of graph degree in a form similar to those expressed in Lemma 2. Furthermore, the $f$ are very simply deduced using the plethysm operator of symmetric functions.

The symmetric function $\prod_{i \ge 1} \frac{1}{1-x_i} \prod_{1 \le i < j} \frac{1}{1-x_i x_j}$ encodes graphs models with $e = ‘me’, l = ‘ll’. This is a very well studied symmetric function, as it also encodes semi-standard Young Tableaux by their content [17, Corollary 7.13.8]. Thus, the method presented in this work determines generating functions of semi-standard Young tableaux with restrictions on the number of times each number appears as an entry. For example,

<footnote n="4">⁴The documentation of the procedure promises to achieve the minimal order, but to the best of our knowledge no formal publication is available yet.</footnote>
$\langle \prod_{i \ge 1} \frac{1}{1-x_i} \prod_{1 \le i < j} \frac{1}{1-x_i x_j}, h_1^n \rangle$ is the number of standard Young tableaux on $n$ boxes with entries $1, 2, \dots, n$, each appearing exactly once. Some of our results then double as recurrences for the number of semi-standard Young tableaux on $n$ boxes where the number of times an entry appears comes from a finite set $K$.

## 8. ACKNOWLEDGEMENTS

The first author's work was supported in part by the French ANR grant De rerum natura (ANR-19-CE40-0018) and by the French-Austrian ANR-FWF grant EAGLES (ANR-22-CE91-0007 & FWF-I-6130-N). The second author's work was supported by Discovery Grant RGPIN-2017-04157 from the National Science and Engineering Research Council of Canada. The authors are grateful to Nick Wormald for comments on this work, and also to Brendan McKay for motivating our interest in the problem; for providing some counting sequence data for comparison purposes; and for keen observations that arose in the study of the output recurrences.

## REFERENCES

[1] Alin Bostan, Shaoshi Chen, Frédéric Chyzak, and Ziming Li. Complexity of creative telescoping for bivariate rational functions. In *ISSAC'10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation*, pages 203–210, New York, NY, USA, 2010. ACM.

[2] Alin Bostan, Frédéric Chyzak, Pierre Lairez, and Bruno Salvy. Generalized Hermite reduction, creative telescoping and definite integration of D-finite functions. In *Éric Schost, editor, ISSAC'18*, pages 95–102. ACM Press, 2018.

[3] Frédéric Chyzak, Marni Mishna, and Bruno Salvy. Effective scalar products of D-finite symmetric functions. *Journal of Combinatorial Theory. Series A*, 112(1):1–43, 2005.

[4] Ira Gessel. Enumerative applications of symmetric functions. *Séminaire Lotharingien de Combinatoire [electronic only]*, 17:B17a–17, 1987. Publisher: Universität Wien, Fakultät für Mathematik.

[5] Ira M. Gessel. Symmetric functions and P-recursiveness. *Journal of Combinatorial Theory. Series A*, 53(2):257–285, 1990.

[6] I. P. Goulden, D. M. Jackson, and J. W. Reilly. The Hammond series of a symmetric function and its application to P-recursiveness. *Society for Industrial and Applied Mathematics. Journal on Algebraic and Discrete Methods*, 4(2):179–193, 1983.

[7] Harald Gropp. Enumeration of regular graphs 100 years ago. In *Discrete Mathematics*, volume 101, pages 73–85. 1992. ISSN: 0012-365X,1872-681X Journal Abbreviation: Discrete Math.

[8] L. Lipshitz. D-finite power series. *Journal of Algebra*, 122(2):353–373, 1989.

[9] Miguel Méndez. Multisets and the combinatorics of symmetric functions. *Adv. Math.*, 102(1):95–125, 1993.

[10] Marni Mishna. Automatic enumeration of regular objects. *Journal of Integer Sequences*, 10(5):Article 07.5.5, 18, 2007.

[11] Marni Mishna. Regularity in weighted graphs a symmetric function approach. *Contributions to Discrete Mathematics*, 13(2):32–44, 2018.

[12] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org. Accessed on July 23, 2024.

[13] R. C. Read. The enumeration of locally restricted graphs. I. *The Journal of the London Mathematical Society*, 34:417–436, 1959.

[14] R. C. Read and N. C. Wormald. Number of labeled 4-regular graphs. *Journal of Graph Theory*, 4(2):203–212, 1980.

[15] Ronald C Read. *Some enumeration problems in graph theory*. PhD thesis, University of London (University College of the West Indies), 1959.

[16] R. P. Stanley. Differentiably finite power series. *European Journal of Combinatorics*, 1(2):175–188, 1980.

[17] Richard P. Stanley. *Enumerative combinatorics. Vol. 2*, volume 62 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[18] Nicholas Wormald. Asymptotic enumeration of graphs with given degree sequence. In *Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018*, pages 3245–3264. World Scientific, 2018.

[19] Yi Zhou. *Algorithms for factoring linear recurrence operators*. PhD thesis, Florida State University, 2022.

## APPENDIX A. DIFFERENTIAL EQUATIONS AND RECURRENCES RELATIONS

Table 2 gathers information related to computations we performed for a list of models:

* parameters “edges”, “loops”, and $k$’s are as described in Section 3;

* the obtained ODE has order provided in column $\partial_t$ and its polynomial coefficients have degrees bounded by the number in column $t$;

* a first recurrence on the number of graphs of size $n$ is directly obtained by translating the ODE by Maple's `gfun[diffeqtorec]`; it has order provided in column $\partial_n$ and its polynomial coefficients have degrees bounded by the number in column $n$;
* in the majority of models, the first recurrence could be minimized by LREtools[MinimalRecurrence], leading to a new pair of columns *n* and *∂*<sub>*n*</sub>; the minimal order is proved unless it is starred, meaning that the minimized recurrence is only of minimal order among recurrences on even terms;

* the corresponding calculation is done in the time of column "time", measured in seconds.

<table><caption>Table 2: Models up to *k* = 7. See description in Section 3. All timings obtained on the same computer (with AMD EPYC 9754 processor).</caption><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂<sub>t</sub></th><th>n<br>from ODE</th><th>∂<sub>n</sub></th><th>n<br>minimized</th><th>time</th></tr></thead><tbody><tr><td>se</td><td>ll</td><td>2</td><td>2</td><td>1</td><td>1</td><td>3</td><td>1</td><td>3</td><td>0.04</td></tr><tr><td>me</td><td>ll</td><td>2</td><td>2</td><td>1</td><td>1</td><td>3</td><td>1</td><td>3</td><td>0.05</td></tr><tr><td>se</td><td>la</td><td>2</td><td>2</td><td>1</td><td>1</td><td>3</td><td>1</td><td>3</td><td>0.05</td></tr><tr><td>me</td><td>la</td><td>2</td><td>2</td><td>1</td><td>1</td><td>3</td><td>1</td><td>3</td><td>0.05</td></tr><tr><td>se</td><td>lh</td><td>2</td><td>3</td><td>1</td><td>1</td><td>4</td><td>1</td><td>4</td><td>0.05</td></tr><tr><td>me</td><td>lh</td><td>2</td><td>3</td><td>1</td><td>1</td><td>4</td><td>1</td><td>4</td><td>0.05</td></tr><tr><td>se</td><td>ll</td><td>1,2</td><td>3</td><td>1</td><td>1</td><td>4</td><td>1</td><td>4</td><td>0.05</td></tr><tr><td>me</td><td>ll</td><td>1,2</td><td>3</td><td>1</td><td>1</td><td>4</td><td>1</td><td>4</td><td>0.05</td></tr><tr><td>se</td><td>la</td><td>1,2</td><td>3</td><td>1</td><td>1</td><td>4</td><td>1</td><td>4</td><td>0.07</td></tr><tr><td>me</td><td>la</td><td>1,2</td><td>3</td><td>1</td><td>1</td><td>4</td><td>1</td><td>4</td><td>0.05</td></tr><tr><td>se</td><td>lh</td><td>1,2</td><td>3</td><td>1</td><td>1</td><td>4</td><td>1</td><td>4</td><td>0.06</td></tr><tr><td>me</td><td>lh</td><td>1,2</td><td>3</td><td>1</td><td>1</td><td>4</td><td>1</td><td>4</td><td>0.06</td></tr><tr><td>se</td><td>ll</td><td>3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>4</td><td>8*</td><td>0.08</td></tr><tr><td>me</td><td>ll</td><td>3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>4</td><td>8*</td><td>0.08</td></tr><tr><td>se</td><td>la</td><td>3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>4</td><td>8*</td><td>0.09</td></tr><tr><td>me</td><td>la</td><td>3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>4</td><td>8*</td><td>0.07</td></tr><tr><td>se</td><td>lh</td><td>3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.09</td></tr><tr><td>me</td><td>lh</td><td>3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.1</td></tr><tr><td>se</td><td>ll</td><td>1,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>4</td><td>8*</td><td>0.09</td></tr><tr><td>me</td><td>ll</td><td>1,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>4</td><td>8*</td><td>0.07</td></tr><tr><td>se</td><td>la</td><td>1,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>4</td><td>8*</td><td>0.09</td></tr><tr><td>me</td><td>la</td><td>1,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>3</td><td>8*</td><td>0.07</td></tr><tr><td>se</td><td>lh</td><td>1,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.07</td></tr><tr><td>me</td><td>lh</td><td>1,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.09</td></tr><tr><td>se</td><td>ll</td><td>2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.08</td></tr><tr><td>me</td><td>ll</td><td>2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.1</td></tr><tr><td>se</td><td>la</td><td>2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.08</td></tr><tr><td>me</td><td>la</td><td>2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.08</td></tr><tr><td>se</td><td>lh</td><td>2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.08</td></tr><tr><td>me</td><td>lh</td><td>2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.08</td></tr><tr><td>se</td><td>ll</td><td>1,2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.07</td></tr><tr><td>me</td><td>ll</td><td>1,2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.1</td></tr><tr><td>se</td><td>la</td><td>1,2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.08</td></tr><tr><td>me</td><td>la</td><td>1,2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.07</td></tr><tr><td>se</td><td>lh</td><td>1,2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.08</td></tr><tr><td>me</td><td>lh</td><td>1,2,3</td><td>11</td><td>2</td><td>2</td><td>12</td><td>6</td><td>8</td><td>0.08</td></tr><tr><td>se</td><td>ll</td><td>4</td><td>14</td><td>2</td><td>2</td><td>15</td><td>7</td><td>10</td><td>0.2</td></tr><tr><td>me</td><td>ll</td><td>4</td><td>14</td><td>2</td><td>2</td><td>15</td><td>7</td><td>10</td><td>0.2</td></tr><tr><td>se</td><td>la</td><td>4</td><td>14</td><td>2</td><td>2</td><td>15</td><td>7</td><td>10</td><td>0.19</td></tr><tr><td>me</td><td>la</td><td>4</td><td>14</td><td>2</td><td>2</td><td>15</td><td>6</td><td>10</td><td>0.17</td></tr></tbody></table><table><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂<sub>t</sub></th><th>from ODE<br>n</th><th>∂<sub>n</sub></th><th>minimized<br>n</th><th>time</th></tr></thead><tbody></tbody></table>
<table><caption>Table 2: Models up to k = 7 (continued)</caption><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂<sub>t</sub></th><th>n<br>from ODE</th><th>∂<sub>n</sub></th><th>n<br>minimized</th><th>time</th></tr></thead><tbody><tr><td>se</td><td>lh</td><td>4</td><td>30</td><td>3</td><td>3</td><td>31</td><td>18</td><td>16</td><td>0.19</td></tr><tr><td>me</td><td>lh</td><td>4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.19</td></tr><tr><td>se</td><td>ll</td><td>1,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.29</td></tr><tr><td>me</td><td>ll</td><td>1,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.28</td></tr><tr><td>se</td><td>la</td><td>1,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.2</td></tr><tr><td>me</td><td>la</td><td>1,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.18</td></tr><tr><td>se</td><td>lh</td><td>1,4</td><td>30</td><td>3</td><td>3</td><td>31</td><td>18</td><td>16</td><td>0.29</td></tr><tr><td>me</td><td>lh</td><td>1,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.27</td></tr><tr><td>se</td><td>ll</td><td>2,4</td><td>14</td><td>2</td><td>2</td><td>15</td><td>7</td><td>10</td><td>0.2</td></tr><tr><td>me</td><td>ll</td><td>2,4</td><td>14</td><td>2</td><td>2</td><td>15</td><td>7</td><td>10</td><td>0.2</td></tr><tr><td>se</td><td>la</td><td>2,4</td><td>14</td><td>2</td><td>2</td><td>15</td><td>7</td><td>10</td><td>0.2</td></tr><tr><td>me</td><td>la</td><td>2,4</td><td>14</td><td>2</td><td>2</td><td>15</td><td>7</td><td>10</td><td>0.21</td></tr><tr><td>se</td><td>lh</td><td>2,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.29</td></tr><tr><td>me</td><td>lh</td><td>2,4</td><td>30</td><td>3</td><td>3</td><td>31</td><td>18</td><td>16</td><td>0.27</td></tr><tr><td>se</td><td>ll</td><td>3,4</td><td>30</td><td>3</td><td>3</td><td>31</td><td>18</td><td>16</td><td>0.3</td></tr><tr><td>me</td><td>ll</td><td>3,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.33</td></tr><tr><td>se</td><td>la</td><td>3,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.3</td></tr><tr><td>me</td><td>la</td><td>3,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.31</td></tr><tr><td>se</td><td>lh</td><td>3,4</td><td>30</td><td>3</td><td>3</td><td>31</td><td>18</td><td>16</td><td>0.33</td></tr><tr><td>me</td><td>lh</td><td>3,4</td><td>30</td><td>3</td><td>3</td><td>31</td><td>18</td><td>16</td><td>0.32</td></tr><tr><td>se</td><td>ll</td><td>1,2,3,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.32</td></tr><tr><td>me</td><td>ll</td><td>1,2,3,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.24</td></tr><tr><td>se</td><td>la</td><td>1,2,3,4</td><td>29</td><td>3</td><td>3</td><td>30</td><td>17</td><td>16</td><td>0.34</td></tr><tr><td>me</td><td>la</td><td>1,2,3,4</td><td>30</td><td>3</td><td>3</td><td>31</td><td>18</td><td>16</td><td>0.24</td></tr><tr><td>se</td><td>lh</td><td>1,2,3,4</td><td>30</td><td>3</td><td>3</td><td>31</td><td>18</td><td>16</td><td>0.28</td></tr><tr><td>me</td><td>lh</td><td>1,2,3,4</td><td>30</td><td>3</td><td>3</td><td>31</td><td>18</td><td>16</td><td>0.3</td></tr><tr><td>se</td><td>ll</td><td>5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.96</td></tr><tr><td>me</td><td>ll</td><td>5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.7</td></tr><tr><td>se</td><td>la</td><td>5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.92</td></tr><tr><td>me</td><td>la</td><td>5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.8</td></tr><tr><td>se</td><td>lh</td><td>5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.42</td></tr><tr><td>me</td><td>lh</td><td>5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.09</td></tr><tr><td>se</td><td>ll</td><td>1,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.78</td></tr><tr><td>me</td><td>ll</td><td>1,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.52</td></tr><tr><td>se</td><td>la</td><td>1,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.5</td></tr><tr><td>me</td><td>la</td><td>1,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.8</td></tr><tr><td>se</td><td>lh</td><td>1,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.55</td></tr><tr><td>me</td><td>lh</td><td>1,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.44</td></tr><tr><td>se</td><td>ll</td><td>2,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.27</td></tr><tr><td>me</td><td>ll</td><td>2,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.76</td></tr><tr><td>se</td><td>la</td><td>2,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.49</td></tr><tr><td>me</td><td>la</td><td>2,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.37</td></tr><tr><td>se</td><td>lh</td><td>2,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.62</td></tr><tr><td>me</td><td>lh</td><td>2,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>—</td><td>—</td><td>2.48</td></tr><tr><td>se</td><td>ll</td><td>3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.94</td></tr><tr><td>me</td><td>ll</td><td>3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.97</td></tr><tr><td>se</td><td>la</td><td>3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.82</td></tr></tbody><tfoot><tr><td>edges</td><td>loops</td><td>k's</td><td>t</td><td>∂<sub>t</sub></td><td>from ODE<br>n</td><td>∂<sub>n</sub></td><td>n<br>minimized</td><td>time</td></tr></tfoot></table>
<table><caption>Table 2: Models up to k = 7 (continued)</caption><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂<sub>t</sub></th><th>n<br>from ODE</th><th>∂<sub>n</sub></th><th>n<br>minimized</th><th>∂<sub>n</sub></th><th>time</th></tr></thead><tbody><tr><td>me</td><td>la</td><td>3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>2.18</td></tr><tr><td>se</td><td>lh</td><td>3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.46</td></tr><tr><td>me</td><td>lh</td><td>3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.52</td></tr><tr><td>se</td><td>ll</td><td>4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.87</td></tr><tr><td>me</td><td>ll</td><td>4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.8</td></tr><tr><td>se</td><td>la</td><td>4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.71</td></tr><tr><td>me</td><td>la</td><td>4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.72</td></tr><tr><td>se</td><td>lh</td><td>4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.95</td></tr><tr><td>me</td><td>lh</td><td>4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.8</td></tr><tr><td>se</td><td>ll</td><td>1,3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.83</td></tr><tr><td>me</td><td>ll</td><td>1,3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.8</td></tr><tr><td>se</td><td>la</td><td>1,3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.85</td></tr><tr><td>me</td><td>la</td><td>1,3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>53</td><td>32*</td><td>1.78</td></tr><tr><td>se</td><td>lh</td><td>1,3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.55</td></tr><tr><td>me</td><td>lh</td><td>1,3,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.73</td></tr><tr><td>se</td><td>ll</td><td>1,2,3,4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>3.17</td></tr><tr><td>me</td><td>ll</td><td>1,2,3,4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.98</td></tr><tr><td>se</td><td>la</td><td>1,2,3,4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.96</td></tr><tr><td>me</td><td>la</td><td>1,2,3,4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.83</td></tr><tr><td>se</td><td>lh</td><td>1,2,3,4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>3.03</td></tr><tr><td>me</td><td>lh</td><td>1,2,3,4,5</td><td>125</td><td>6</td><td>6</td><td>126</td><td>-</td><td>-</td><td>2.88</td></tr><tr><td>se</td><td>ll</td><td>6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>52.3</td></tr><tr><td>me</td><td>ll</td><td>6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>49.4</td></tr><tr><td>se</td><td>la</td><td>6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>52.6</td></tr><tr><td>me</td><td>la</td><td>6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>49.5</td></tr><tr><td>se</td><td>lh</td><td>6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>250</td></tr><tr><td>me</td><td>lh</td><td>6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>265</td></tr><tr><td>se</td><td>ll</td><td>1,6</td><td>417</td><td>10</td><td>10</td><td>418</td><td>-</td><td>-</td><td>182</td></tr><tr><td>me</td><td>ll</td><td>1,6</td><td>417</td><td>10</td><td>10</td><td>418</td><td>-</td><td>-</td><td>170</td></tr><tr><td>se</td><td>la</td><td>1,6</td><td>417</td><td>10</td><td>10</td><td>418</td><td>-</td><td>-</td><td>186</td></tr><tr><td>me</td><td>la</td><td>1,6</td><td>417</td><td>10</td><td>10</td><td>418</td><td>-</td><td>-</td><td>186</td></tr><tr><td>se</td><td>lh</td><td>1,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>265</td></tr><tr><td>me</td><td>lh</td><td>1,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>233</td></tr><tr><td>se</td><td>ll</td><td>2,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>55</td></tr><tr><td>me</td><td>ll</td><td>2,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>58</td></tr><tr><td>se</td><td>la</td><td>2,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>55.4</td></tr><tr><td>me</td><td>la</td><td>2,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>51.6</td></tr><tr><td>se</td><td>lh</td><td>2,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>264</td></tr><tr><td>me</td><td>lh</td><td>2,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>261</td></tr><tr><td>se</td><td>ll</td><td>3,6</td><td>423</td><td>10</td><td>10</td><td>424</td><td>-</td><td>-</td><td>262</td></tr><tr><td>me</td><td>ll</td><td>3,6</td><td>423</td><td>10</td><td>10</td><td>424</td><td>-</td><td>-</td><td>277</td></tr><tr><td>se</td><td>la</td><td>3,6</td><td>423</td><td>10</td><td>10</td><td>424</td><td>-</td><td>-</td><td>259</td></tr><tr><td>me</td><td>la</td><td>3,6</td><td>423</td><td>10</td><td>10</td><td>424</td><td>-</td><td>-</td><td>298</td></tr><tr><td>se</td><td>lh</td><td>3,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>276</td></tr><tr><td>me</td><td>lh</td><td>3,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>268</td></tr><tr><td>se</td><td>ll</td><td>4,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>63.5</td></tr><tr><td>me</td><td>ll</td><td>4,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>67.7</td></tr></tbody></table><table><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂<sub>t</sub></th><th>n<br>from ODE</th><th>∂<sub>n</sub></th><th>n<br>minimized</th><th>∂<sub>n</sub></th><th>time</th></tr></thead><tbody></tbody></table>
<table><caption>Table 2: Models up to k = 7 (continued)</caption><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂<sub>t</sub></th><th>n</th><th>∂<sub>n</sub></th><th>n</th><th>∂<sub>n</sub></th><th>time</th></tr></thead><tbody><tr><td>se</td><td>la</td><td>4,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>60.6</td></tr><tr><td>me</td><td>la</td><td>4,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>65.4</td></tr><tr><td>se</td><td>lh</td><td>4,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>308</td></tr><tr><td>me</td><td>lh</td><td>4,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>311</td></tr><tr><td>se</td><td>ll</td><td>5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>378</td></tr><tr><td>me</td><td>ll</td><td>5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>315</td></tr><tr><td>se</td><td>la</td><td>5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>361</td></tr><tr><td>me</td><td>la</td><td>5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>326</td></tr><tr><td>se</td><td>lh</td><td>5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>344</td></tr><tr><td>me</td><td>lh</td><td>5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>302</td></tr><tr><td>se</td><td>ll</td><td>2,4,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>73.9</td></tr><tr><td>me</td><td>ll</td><td>2,4,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>68.9</td></tr><tr><td>se</td><td>la</td><td>2,4,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>59.2</td></tr><tr><td>me</td><td>la</td><td>2,4,6</td><td>145</td><td>6</td><td>6</td><td>146</td><td>116</td><td>36</td><td>69.3</td></tr><tr><td>se</td><td>lh</td><td>2,4,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>293</td></tr><tr><td>me</td><td>lh</td><td>2,4,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>300</td></tr><tr><td>se</td><td>ll</td><td>1,2,3,4,5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>447</td></tr><tr><td>me</td><td>ll</td><td>1,2,3,4,5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>402</td></tr><tr><td>se</td><td>la</td><td>1,2,3,4,5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>387</td></tr><tr><td>me</td><td>la</td><td>1,2,3,4,5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>509</td></tr><tr><td>se</td><td>lh</td><td>1,2,3,4,5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>397</td></tr><tr><td>me</td><td>lh</td><td>1,2,3,4,5,6</td><td>425</td><td>10</td><td>10</td><td>426</td><td>-</td><td>-</td><td>547</td></tr><tr><td>se</td><td>ll</td><td>7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>3.22e+04</td></tr><tr><td>me</td><td>ll</td><td>7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>2.66e+04</td></tr><tr><td>se</td><td>la</td><td>7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>5.16e+04</td></tr><tr><td>me</td><td>la</td><td>7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>2.02e+04</td></tr><tr><td>se</td><td>lh</td><td>7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>3.46e+04</td></tr><tr><td>me</td><td>lh</td><td>7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>3.06e+04</td></tr><tr><td>se</td><td>ll</td><td>1,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>3.11e+04</td></tr><tr><td>me</td><td>ll</td><td>1,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>1.65e+04</td></tr><tr><td>se</td><td>la</td><td>1,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>1.82e+04</td></tr><tr><td>me</td><td>la</td><td>1,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>5.93e+04</td></tr><tr><td>se</td><td>lh</td><td>1,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>5.15e+04</td></tr><tr><td>me</td><td>lh</td><td>1,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>4.11e+04</td></tr><tr><td>se</td><td>ll</td><td>2,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>7.68e+04</td></tr><tr><td>me</td><td>ll</td><td>2,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>4.39e+04</td></tr><tr><td>se</td><td>la</td><td>2,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>4.43e+04</td></tr><tr><td>me</td><td>la</td><td>2,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>3.22e+04</td></tr><tr><td>se</td><td>lh</td><td>2,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>4.17e+04</td></tr><tr><td>me</td><td>lh</td><td>2,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>5.04e+04</td></tr><tr><td>se</td><td>ll</td><td>3,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>9.72e+04</td></tr><tr><td>me</td><td>ll</td><td>3,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>5.89e+04</td></tr><tr><td>se</td><td>la</td><td>3,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>1.46e+04</td></tr><tr><td>me</td><td>la</td><td>3,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>1.38e+05</td></tr><tr><td>se</td><td>lh</td><td>3,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>3.73e+04</td></tr><tr><td>me</td><td>lh</td><td>3,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>3.80e+04</td></tr><tr><td>se</td><td>ll</td><td>4,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>-</td><td>3.65e+04</td></tr></tbody></table><table><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂<sub>t</sub></th><th>from ODE</th><th>n</th><th>∂<sub>n</sub></th><th>n</th><th>∂<sub>n</sub></th><th>time</th></tr></thead></table>
<table><caption>Table 2: Models up to k = 7 (continued)</caption><thead><tr><th>edges</th><th>loops</th><th>k's</th><th>t</th><th>∂<sub>t</sub></th><th>n<br>from ODE</th><th>∂<sub>n</sub></th><th>n<br>minimized</th><th>time</th></tr></thead><tbody><tr><td>me</td><td>ll</td><td>4,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>3.50e+04</td></tr><tr><td>se</td><td>la</td><td>4,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>6.28e+04</td></tr><tr><td>me</td><td>la</td><td>4,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>3.75e+04</td></tr><tr><td>se</td><td>lh</td><td>4,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>3.69e+04</td></tr><tr><td>me</td><td>lh</td><td>4,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>3.61e+04</td></tr><tr><td>se</td><td>ll</td><td>5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>3.48e+04</td></tr><tr><td>me</td><td>ll</td><td>5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>1.09e+05</td></tr><tr><td>se</td><td>la</td><td>5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.17e+04</td></tr><tr><td>me</td><td>la</td><td>5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.87e+04</td></tr><tr><td>se</td><td>lh</td><td>5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.39e+04</td></tr><tr><td>me</td><td>lh</td><td>5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.61e+04</td></tr><tr><td>se</td><td>ll</td><td>6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.67e+04</td></tr><tr><td>me</td><td>ll</td><td>6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.60e+04</td></tr><tr><td>se</td><td>la</td><td>6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.97e+04</td></tr><tr><td>me</td><td>la</td><td>6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.76e+04</td></tr><tr><td>se</td><td>lh</td><td>6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.10e+04</td></tr><tr><td>me</td><td>lh</td><td>6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>5.31e+04</td></tr><tr><td>se</td><td>ll</td><td>1,3,5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>2.63e+04</td></tr><tr><td>me</td><td>ll</td><td>1,3,5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>8.89e+04</td></tr><tr><td>se</td><td>la</td><td>1,3,5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>1.96e+04</td></tr><tr><td>me</td><td>la</td><td>1,3,5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>2.44e+04</td></tr><tr><td>se</td><td>lh</td><td>1,3,5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>3.90e+04</td></tr><tr><td>me</td><td>lh</td><td>1,3,5,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>3.89e+04</td></tr><tr><td>se</td><td>ll</td><td>1,2,3,4,5,6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.67e+04</td></tr><tr><td>me</td><td>ll</td><td>1,2,3,4,5,6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.99e+04</td></tr><tr><td>se</td><td>la</td><td>1,2,3,4,5,6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>3.86e+04</td></tr><tr><td>me</td><td>la</td><td>1,2,3,4,5,6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>4.95e+04</td></tr><tr><td>se</td><td>lh</td><td>1,2,3,4,5,6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>5.53e+04</td></tr><tr><td>me</td><td>lh</td><td>1,2,3,4,5,6,7</td><td>1683</td><td>20</td><td>20</td><td>1684</td><td>-</td><td>6.12e+04</td></tr></tbody></table>