# Counting Reduced Ordered Binary Decision Diagrams
With Respect to Size

Julien Clément, Antoine Genitrini

► To cite this version:

Julien Clément, Antoine Genitrini. Counting Reduced Ordered Binary Decision Diagrams With Respect to Size. 2025. hal-05183438

HAL Id: hal-05183438

https://hal.sorbonne-universite.fr/hal-05183438v1

Preprint submitted on 24 Jul 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
# Counting Reduced Ordered Binary Decision Diagrams With Respect to Size

Julien Clément

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

Normandie Université, UNICAEN, ENSICAEN, CNRS, GREYC - UMR 6072

Antoine Genitrini

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

Sorbonne Université, CNRS, LIP6 - UMR 7606

## Abstract

The set of *binary decision diagrams*, an efficient data structure representing Boolean functions, is extensively used in many distinct contexts like model verification, machine learning, cryptography or also resolution of combinatorial problems. The most famous variant, called reduced ordered binary decision diagram (ROBDD for short), can be viewed as the result of a specific compaction of a complete decision tree. A great property is that, once an order over the Boolean variables is fixed, each Boolean function is represented by exactly one ROBDD. In this paper we aim at computing the *exact distribution of the Boolean functions in k variables according to the ROBDD size*. Recall the number of Boolean functions with *k* variables is equal to $2^{2^k}$, which is of double exponential growth with respect to the number of variables. The maximal size of an ROBDD with *k* variables is $M_k \approx 2^k/k$. In this paper, we develop the first polynomial algorithm to derive the distribution of Boolean functions over *k* variables with respect to ROBDD size denoted by *n*. It performs $O(k n^3 \log n)$ arithmetical operations on integers and necessitates to store $O(n^2)$ integers in memory storage. Our new approach relies on a decomposition of ROBDDs layer by layer and on an enumerative inclusion-exclusion argument.

**2012 ACM Subject Classification** Mathematics of computing → Combinatorial algorithms; Mathematics of computing → Generating functions; Mathematics of computing → Combinatoric problems; Theory of computation → Generating random combinatorial structures; Information systems → Data compression; Theory of computation → Data compression

**Keywords and phrases** Boolean Function, Reduced Ordered Binary Decision Diagram (ROBDD), Enumerative Combinatorics, Directed Acyclic Graph

**Digital Object Identifier** 10.4230/LIPIcs...

**Funding** ANR-FWF project PANDAG ANR-23-CE48-0014-01

# 1 Introduction

Reduced Ordered Binary Decision Diagrams (ROBDDs) have served as a cornerstone of computer science for decades, providing a canonical and memory-efficient representation of Boolean functions. Their formalization is credited to Bryant in 1986 [1]. The algorithmic paradigm underpinning them offers clear advantages: it relies on a *divide-and-conquer* strategy, reinforced by a compaction mechanism.

The advantages of ROBDDs over alternative Boolean representations are so significant that dozens of diagram variants have emerged in recent years. They have become indispensable in areas such as formal verification [18], cryptography [12], and knowledge compilation [7]. Their prevalence in tools like model checkers and SAT solvers further underscores their lasting importance. Moreover, various decision diagrams also play a key role in strategies for solving combinatorial problems—for instance, the classic problem of counting satisfying assignments [11, vol. 4].

From a combinatorial standpoint, ROBDDs are typically represented as directed acyclic graphs (or DAGs). ROBDDs form a specialized subclass of DAGs, where node reduction imposes

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

© Julien Clément and Antoine Genitrini;
licensed under Creative Commons License CC-BY 4.0

Leibniz International Proceedings in Informatics

LIPICS Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
XX:2 Counting ROBDDs With Respect to Size

strict constraints—specifically, no two substructures within the graph may be isomorphic. A
central challenge is that, unlike binary trees (which admit well-known recursive decompositions
fundamental to their combinatorial analysis, such as for profile, width, or depth), no recursive
characterization of ROBDDs is known.

In other combinatorial structures, global non-isomorphism constraints are sometimes
addressed through the inclusion-exclusion principle, facilitating counts. However, such
approaches generally hinder effective random generation. Beyond the intriguing problem
of understanding the distribution of Boolean functions according to ROBDD size, uniform
random generation of ROBDDs is crucial. The Shannon effect [9] implies that almost all
ROBDDs for a fixed number of variables have near-maximum size. Therefore, methods for
generating structures of a given size are central—for example, within property-based testing
frameworks [3].

Prior research on counting (e.g. [11, 14]) and sampling (e.g. [10]) has offered partial
progress, but gaps persist with respect to uniform generation under size or profile con-
straints. This paper fills those gaps by integrating combinatorial techniques with algorithmic
innovations.

**Organization of the paper.** This article is a long version of [5]. The paper is organized as follows. In Section 2, we present the combinatorics necessary for the description of our counting approach. We provide in Section 4 our main results and relate them with the state of the art about the combinatorics of *Reduced Ordered Binary Decision Diagrams*. Section 5 can be seen as an interlude since it analyses the classical worst case size and profile of an ROBDD (the profile describes the number of decision nodes labelled with each variable). While the results are essentially already known, we present there new proof strategies. This section serves to the worst case analyses of our algorithmic tools that will follow. Section 6 presents our new iterative process for computing the number of ROBDDs having a given profile. It also states the most fundamental result of this paper which is an algebraic iterative formula for computing the number of ROBDDs involving linear maps over a polynomial ring. Finally, Section 7 presents the algorithmic tools derived for computing the complete distribution for Boolean functions according to their ROBDD sizes.

2 Preliminaries: Boolean functions representation

A Boolean function in $k$ variables is a function from the set $\{0, 1\}^k$ into the set $\{0, 1\}$. The set of functions is denoted by $B_k$ and its cardinality is $2^{2^k}$. Furthermore, for the rest of this paper, we choose an ordering of the sequence of variables that corresponds to $x_0, x_1, \dots, x_{k-1}$. Any other ordering could be chosen, but one must be fixed.

**2.1 Decision trees and binary decision diagrams**

Fig. 1 shows a decision tree representing a 4-variable Boolean function and its associated
ROBDD. In both structures, traversing a path from the root to a leaf allows to evaluate the
function for a given assignment. Being in a node labelled by $x_i$ and going to its low child
(taking the dotted edge) corresponds with evaluating $x_i$ to 0; going to its high child (with
the solid edge) corresponds with evaluating $x_i$ to 1.

► **Definition 1 (DAG representation).** Let $f \in B_k$ a Boolean function in $k$ variables $x_0, \dots, x_{k-1}$. The function $f$ can be represented as a rooted directed acyclic graph (DAG for short) composed of internal decision nodes, labelled by variables and two terminal nodes labelled by $\{\bot, \top\}$
<figure><img src="image_5.png" /><figcaption>■ **Figure 1** (left) A decision tree and (right) its associated ROBDD.</figcaption></figure>

representing respectively the constants 0 and 1. Each decision node labelled by $x_i$ ($0 \le i \le k$) has two children, the low child (resp. high child) such that traversing the edge to the low child (resp. high child) corresponds to assign $x_i$ to 0 (resp. to 1). In the DAG representation these edges are labeled 0 (resp. 1). The size of a DAG is its number of decision nodes.

By convention, in figures, nodes will be depicted in figures as having dotted left half-edges (for 0), and solid half-edges (for 1) departing them.

**Definition 2 (OBDD).** Let $f \in \mathcal{B}_k$ and one of its DAG representation. The DAG is called an Ordered Binary Decision Diagram for $f$ (OBDD for short) when all paths from the root to a terminal node traverse decision nodes with index in increasing order.

Taking an OBDD for a function $f \in \mathcal{B}_k$, and extracting the sub-DAG rooted in $\nu$ (labeled by $x_i$ for some $0 \le i < k$), we obtained an OBDD representing a Boolean function in the variables $x_i, x_{i+1}, \dots, x_{k-1}$.

**Definition 3 (ROBDD).** Let $f \in \mathcal{B}_k$ and $B$ one of its OBDD. If all sub-DAGs of $B$ are representing distinct Boolean functions and no decision node has the same low and high children, then $B$ is called Reduced Ordered Binary Decision Diagram (ROBDD).

Fig. 2 shows the forbidden configurations in ROBDD and the operations used to compress the structure.

<figure><img src="image_6.png" /><figcaption>■ **Figure 2** The two forbidden configurations in ROBDDs and the resulting operations when compressing: (left) $\nu$ and $\nu'$ are merged; (right) $\nu$ is deleted (from [9]).</figcaption></figure>

**Fact.** Let $f \in \mathcal{B}_k$ and an order on the variables, then there exists a single ROBDD representing $f$.

The data structure of ROBDDs is especially famous due to this property of canonicity<fnref n="1" />. The reader may refer to Knuth [11] for the proof of uniqueness and several other properties satisfied by ROBDDs.

<footnote n="1">¹ Uniqueness of the ROBDD for $f$ is ensured once a variable ordering is fixed.</footnote>
## XX:4 Counting ROBDDs With Respect to Size

For the rest of the paper, we are only dealing with ROBDDs. Furthermore, we take the point of view of layered ROBDD by studying and representing ROBDDs layer by layer: each layer contains all decision nodes labelled by the same variable. This layer-by-layer decomposition is natural since the variables are ordered. Thus, an ROBDD for a function in $k$ variables is composed of $k$ layers (plus a layer for the two terminal nodes). Note that any layer except the last one (constants) could be empty. An empty layer at level $\ell$ means the Boolean function does not depend on the particular variable $x_\ell$.

We can thus define the profile of an ROBDD with respect to layers.

**Definition 4 (Profile and size of an ROBDD).** Let $f \in \mathcal{B}_k$ and $B$ be its ROBDD. The profile of an ROBDD $B$ with $k$ variables is the non-negative integer sequence $\mathbf{p} = (p_0, p_1, \dots, p_{k-1})$, such that $p_i$ is the number of nodes labelled by $x_i$ in $B$, i.e. the size of the layer corresponding with $x_i$, for all $i \in \{0, \dots, k-1\}$. The size of an ROBDD is the number of decision nodes in its layers, i.e., $\sum_{i=0}^{k-1} p_i$.

As an example, the ROBDD depicted in Fig. 1 has profile $\mathbf{p} = (1, 2, 3, 2)$ and size 8. Sink nodes $\top$ (true) and $\bot$ (false) do not contribute to the size (by our definition).

In our previous paper [4], we proposed a recursive-like decomposition of an ROBDD based on the low and high children of the root. Here, we present a new framework, much simpler, which is based on a layer-by-layer description. This perspective proves to be significantly more efficient for both the counting and generation problems. Its efficiency stems from the ability to share common top layers among different ROBDDs, thereby facilitating factorization in computations.

## 2.2 Multi-rooted diagrams

In the following, we will rely on a classical generalization of an ROBDD, termed *multi-rooted ROBDDs* in [13] and [2, Chapter 26], sometimes also called *shared ROBDDs* (see [11]). Usually it is used in order to describe a set of distinct ROBDDs sharing some common substructures and thus this representation improves the global size compared with the representation of each ROBDD independently from the others. Our point of view is slightly different: a multi-rooted ROBDD is the structure obtained by removing some upper layers in a standard ROBDD (see Fig. 4 for an example).

By removing a specific number of top layers from an ROBDD, the resultant structure maintains its status as a directed acyclic graph (DAG), albeit with multiple entry points (called *sources*, i.e. the roots of each ROBDD in the classical definition). We retain information regarding the destination of half-edges originating from the removed top layers (these are called the incoming half-edges). Fig. 4 illustrates a comparison between an ROBDD and a multi-rooted ROBDD formed by eliminating the top three layers.

**Definition 5.** Let $\mathcal{N}$ be a set of nodes distributed in $k$ layers. An incoming half-edge pointing at a node of layer $\ell$ is said to be of level $\ell$. The profile of a set of incoming half-edges is the sequence $\mathbf{u} = (u_0, \dots, u_{k-1}, u_k)$ where there are $u_\ell$ incoming half-edges of level $\ell$. By extension $u_k$ denotes the number of half-edges going to the extra layer containing the constants.

**Definition 6 (Multi-rooted ROBDD).** A multi-rooted ROBDD with at most $k \ge 0$ variables and size $n \ge 0$ is represented as a pair $(M, \mathcal{U})$, where

■ The structure $M$ constitutes a layered binary directed acyclic graph with a set $\mathcal{N}$ of $n$ decision nodes distributed across $k$ layers, and two sink nodes $\top, \bot$;
- From each decision node, there are two edges departing labeled 0 and 1 connecting this node to another in a strictly deeper level;

- Any two subgraphs are non-isomorphic (akin to ROBDDs);

- The set $\mathcal{U}$ is the set of incoming half-edges, where each incoming half-edge can be identified by its destination in $\mathcal{N} \cup \{\top, \bot\}$;

- All sources of the DAG (nodes of in-degree 0) must be the destination of at least one incoming half-edge in $\mathcal{U}$;

- There is a path from any decision node to both sink nodes.

As a special case, an ROBDD can be seen as a multi-rooted ROBDD having one source (the root) and a set $\mathcal{U}$ reduced to one incoming half-edge pointing to the root. Furthermore, as a small generalization of the classical multi-rooted ROBDDs, we allow several incoming half-edges pointing to the same node (that is not relevant when we want to deal with a set of ROBDDs where each source must correspond with a distinct function).

<figure><img src="image_7.png" /><figcaption>■ **Figure 3** an ROBDD of size 13 (not counting the constant nodes $\bot$ and $\top$), with 6 variables and profile $\boldsymbol{p} = (1, 2, 3, 3, 3, 1)$. (left) A DAG representation of the ROBDD; (right) Cutting off top three layers, we obtain a multi-rooted ROBDD with a set of incoming half-edges represented in red: the set of nodes has profile $\boldsymbol{p} = (0, 0, 0, 3, 3, 1)$ and the set of incoming half-edges has profile $\boldsymbol{u} = (0, 0, 0, 4, 3, 0, 0)$.</figcaption></figure>

Looking at Fig. 4, let us number nodes (below the dotted line) from top to bottom and left to right in the multi-rooted ROBDD shown in Fig. 4. Then, the leftmost $x_3$ is labeled as 1, the second $x_3$ as 2, the rightmost $x_3$ as 3. The leftmost $x_4$ is labeled as 4, until $x_5$ as 7. The constant nodes $\bot$ and $\top$ are respectively assigned labels 8 and 9. This numbering scheme results in the set $\mathcal{U}$ of incoming half-edges which we can identify with their destination nodes 1, 2, 2, 3, 4, 4, 5 (pointed by red half-edges in Fig. 4).

Additionally, we remark that the same multi-rooted ROBDD $M$ may be obtained from different ROBDDs by removing top layers, even varying in number. Again this property allows sharing computations for the counting or the sampling methods we will develop in the next sections.

### 3 Combinatorics and layer description

In our previous paper [4], we proposed a recursive-like decomposition of an ROBDD based on the low and high children of the root. Here, we present a new perspective, much simpler,
XX:6 Counting ROBDDs With Respect to Size

which is based on a layer-by-layer description. This layer-by-layer perspective proves to be
significantly more efficient for both the counting and generation problems. Its efficiency stems
from the ability to share common top layers among different ROBDDs, thereby facilitating
factorization in computations.

**3.1 Multi-rooted diagrams**

In the following, we will rely on a classical generalization of an ROBDD, termed multi-rooted
ROBDDs [13] and Chapter 26 in [2] but also named as shared ROBDDs [11]. Usually it is used
in order to describe a set of distinct ROBDDs sharing some common substructures and thus
this representation improves the global size compared with the representation of each ROBDD
independently from the others. Our point of view is slightly different: a multi-rooted ROBDD
is the structure obtained by removing some upper layers in a standard ROBDD (see Fig. 4 for
an example).

By removing a specific number of top layers from an ROBDD, the resultant structure
maintains its status as a directed acyclic graph (DAG), albeit with multiple entry points
(callied sources, i.e. the roots of each ROBDD in the classical definition). We retain information
regarding the destination of half-edges originating from the removed top layers (these are
called the incoming half-edges). Fig. 4 illustrates a comparison between an ROBDD and a
multi-rooted ROBDD formed by eliminating the top three layers.

**Definition 7.** Let $\mathcal{N}$ be a set of nodes distributed in $k$ layers. An incoming half-edge pointing at a node of layer $\ell$ is said to be of level $\ell$. The profile of a set of incoming half-edges is the sequence $\mathbf{u} = (u_0, \dots, u_{k-1}, u_k)$ where there are $u_\ell$ incoming half-edges of level $\ell$. By extension $u_k$ denotes the number of half-edges going to the extra layer containing the constants.

**Definition 8 (Multi-rooted ROBDD).** A multi-rooted ROBDD with at most $k \ge 0$ variables and size $n \ge 0$ is represented as a pair $(M, \mathcal{U})$, where

The structure $M$ constitutes a layered DAG with $n$ decision nodes $\mathcal{N}$ distributed across $k$ layers, along with two constant nodes $\top, \bot$, such that any two subgraphs are non-identical (akin to ROBDDs);

From each decision node, there are two edges departing labeled 0 and 1 connecting this
node to another in a strictly deeper level;

Any two subgraphs are non-isomorphic (akin to robdds);

The set $\mathcal{U}$ is the set of incoming half-edges, where each incoming half-edge can be identified
by its destination in $\mathcal{N} \cup \{\top, \bot\}$;

All sources of the DAG (nodes of in-degree 0) must be the destination of at least one
incoming half-edge in $\mathcal{U}$;

There is a path from any decision node to both sink nodes.

As a special case, an ROBDD can be seen as a multi-rooted ROBDD having one source
(the root) and a set $\mathcal{U}$ reduced to one incoming half-edge pointing to the root. Furthermore,
as a small generalization of the classical multi-rooted ROBDDs, we allow several incoming
half-edges pointing to the same node (that in not relevant when we want to deal with a set
of ROBDDs where each source must correspond with a distinct function).

Looking at Fig. 4, let us number nodes (below the dotted line) from top to bottom and
left to right in the multi-rooted ROBDD shown in Fig. 4. Then, the leftmost $x_3$ is labeled as 1,
the second $x_3$ as 2, the rightmost $x_3$ as 3. The leftmost $x_4$ is labeled as 4, until $x_5$ as 7. The
constant nodes $\bot$ and $\top$ are respectively assigned labels 8 and 9. This numbering scheme
<figure><img src="image_8.png" /><figcaption>Figure 4 an ROBDD of size 13 (not counting the constant nodes $\perp$ and $\top$), with 6 variables and profile $p = (1, 2, 3, 3, 3, 1)$. (left) A DAG representation of the ROBDD; (right) Cutting off top three layers, we obtain a multi-rooted ROBDD with a set of incoming half-edges represented in red: the set of nodes has profile $p = (0, 0, 0, 3, 3, 1)$ and the set of incoming half-edges has profile $u = (0, 0, 0, 4, 3, 0, 0)$.</figcaption></figure>

results in the set $\mathcal{U}$ of incoming half-edges which we can identify with their destination nodes 1, 2, 2, 3, 4, 4, 5 (pointed by red half-edges in Fig. 4).

Additionally, we remark that the same multi-rooted ROBDD $M$ may be obtained from different ROBDDs by removing top layers, even varying in number. Again this property allows sharing computations for the counting or the sampling methods we will develop in the next sections.

## 3.2 Maximal profile and size of a $k$-variable ROBDD

In order to precisely quantify the complexity of algorithms for counting ROBDDs, we are interested in the maximal number of nodes on any level of an ROBDD with $k$ variables. It turns out that maximizing the size gives an ROBDD also with maximal number of nodes on any layer. In a sense the DAG is saturated.

### 3.2.1 Profile

In this section, we study profiles of ROBDDs. Let $p = (p_0, \dots, p_{k-1})$ the profile of an ROBDD with $k$ variables, i.e. the number of nodes in each layer from top to bottom, and the size $P = \sum_i p_i$. We introduce the notation $P_{<i} = \sum_{j<i} p_j$ and $P_{\ge i} = \sum_{j \ge i} p_j$. Note that $P = P_{<i} + P_{\ge i}$ for any $i \in \{0, \dots, k-1\}$ and by convention we state $P_{<0} = 0$ and $P_{\ge k} = 0$.

**Proposition 9 (Profiles).** Let $p = (p_0, \dots, p_{k-1})$ be a vector of non-negative integers. Then $p$ is the profile of a valid ROBDD if and only if for all $0 \le \ell \le k-1$, we have

$$p_{\ell} \le \min \left( P_{<\ell} + 1, P_{\ge \ell} + 2 - \lfloor \sqrt{P_{\ge \ell} + 2} \rfloor \right). \quad (1)$$

*Proof.* Top part of the DAG. From a classic property of binary trees, a binary tree with $P_{<\ell}$ internal nodes has $P_{<\ell} + 1$ outgoing available half-edges for the next level. Hence, we can add up as many nodes on level $\ell$ such that $p_{\ell} \le P_{<\ell} + 1$. This is also a sufficient condition. Bottom part of the DAG. Let us denote $B = P_{\ge \ell} + 2$ (number of nodes at and below layer $\ell$, constant nodes included). Then the number of pairs $p_{\ell}$ (of children) is less than or equal
XX:8 Counting ROBDDs With Respect to Size

to $(B - p_\ell)(B - p_\ell - 1)$ since each pair must be distinct from the others. This quadratic inequality is easily solved and gives

$$0 \le p_{\ell} \le B - \lfloor \sqrt{B} \rfloor.$$

Finally, a profile satisfying (4) always yields at least a valid ROBDD, as, for any node of any layer, we have always a valid choice for both outgoing edges. ◀

### 3.2.2 Upper bound for size

In order to maximize the number of nodes, we just have to maximize the profile satisfying inequality (4) of Proposition 13. This question was investigated in [14, 16]. However, we give an equivalent proof, and provide an explicit formula for the number of ROBDDs with $k$ variables stated in the following theorem.

**Theorem 10.** Let $k \ge 1$ be an integer. The maximal number of decision nodes in an ROBDD with $k$ variables is

$$2^{k-\theta} + 2^{2\theta} - 3, \quad \text{with } \theta = \lfloor \log_2 (k - \lfloor \log_2 (k) \rfloor) \rfloor.$$

The result of Theorem 14 (without the precise value of $\theta$) has already been stated and proved in [11, Theorem U, Equation (79)], but we propose in the following a more detailed proof. This formula is also the one given (without proof) by Pontus von Brömssen OEIS A327461².

The proof relies entirely on the following proposition specifying the maximal profile of an ROBDD.

**Proposition 11 (Maximal profile).** Let $k \ge 1$ be an integer and $\theta = \lfloor \log_2 (k - \lfloor \log_2 (k) \rfloor) \rfloor$. The profile $p = (p_0, \dots, p_{k-1})$ maximizing ROBDD size for $k$ variables satisfies

$$p_{\ell} = \begin{cases} 2^{\ell} & \text{if } \ell < k - \theta \\ 2^{2^{k-\ell}} - 2^{2^{k-\ell-1}} & \text{if } k - \theta \le \ell < k. \end{cases} \qquad (2)$$

First, we prove a technical lemma.

**Lemma 12.** Let $k \ge 1$ be an integer. There exists a unique pair of integers $(i, j)$ such that

$$k = 2^i + i + j \text{ with } 0 \le j \le 2^i.$$

Moreover, we have $i = \lfloor \log_2 (k - \lfloor \log_2 (k) \rfloor) \rfloor$.

**Proof.** Define the family of intervals of integers $\mathcal{I}_i = [2^i + i, 2^{i+1} + i]$. We easily prove that the intervals are disjoint and that $\bigcup_{i \ge 0} \mathcal{I}_i = \mathbb{N}_{>0}$.

Hence, for any positive integer $k$, there is a unique integer $i$ such that $k \in \mathcal{I}_i$ and defining $j = k - 2^i$ we get $0 \le j \le 2^i$. With this notation, we obtain an explicit formula: indeed let us write $k = 2^i + i + j$ with $0 \le j \le 2^i$. Consequently,

$$k - \lfloor \log_2(k) \rfloor = \begin{cases} 2^i + j & \text{if } 0 \le j < 2^i - i, \\ 2^i + j - 1 & \text{if } 2^i - i \le j \le 2^i. \end{cases}$$

In both cases, $0 \le j < 2^i - i$ or $2^i - i \le j \le 2^i$, this yields $i = \lfloor \log_2 (k - \lfloor \log_2 (k) \rfloor) \rfloor$. ◀

<footnote n="2">² Throughout this paper, a reference OEIS A... points to Sloane's Online Encyclopedia of Integer Sequences www oeis org.</footnote>
XX:10 Counting ROBDDs With Respect to Size

the bound $t_ℓ$ is equal to the one for complete binary trees and thus the constraints on non-redundant decision nodes is trivially valid. The second bound $b_ℓ$ ensures that there are sufficiently many nodes below layer $ℓ$ to ensure that all decision nodes at level $ℓ$ can point to different pairs of children. ◄

As an illustration we provide Table 2 with the first values of parameter $θ$ and the maximal number of decision nodes. A shifted version is presented in OEIS A327461 (each term is shifted by 2, because there the constants are counted in the size).

<table><caption>Table 1 The first values of parameter $θ$ and maximal number $M$ of decision nodes for $1 \le k \le 16$.</caption><thead><tr><th>k</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th><th>16</th></tr></thead><tbody><tr><th>θ</th><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>3</td><td>3</td><td>3</td><td>3</td><td>3</td><td>3</td></tr><tr><th>M</th><td>1</td><td>3</td><td>5</td><td>9</td><td>17</td><td>29</td><td>45</td><td>77</td><td>141</td><td>269</td><td>509</td><td>765</td><td>1277</td><td>2301</td><td>4349</td><td>8445</td></tr></tbody></table>

4 Main results and state of the art

Using the combinatorial context we just presented, we are now ready to state the main results of the paper, and then to put them in perspective with the existing literature about the structure of ROBDD seen as a combinatorial object, especially as a directed acyclic graph with specific building constraints.

4.1 Main results

In this paper, we present results in the context of ROBDDs for the representation of Boolean functions. Our contributions are twofold. First, we introduce a novel perspective on binary diagrams based on their layer decomposition, where each layer corresponds to a specific variable. This approach enables us to describe the global constraints satisfied by ROBDDs from a local viewpoint, leading to a new recursive formula for counting structures of a given profile, and more generally, of a given size. The algebraic framework we developed further optimizes calculations for profiles sharing the same prefix. Additionally, we establish an inclusion-exclusion counting formula that enumerates (i.e., provides a combinatorial interpretation for) the number of valid layers, given the number of edges reaching the current layer. Fig. 7 illustrates this scenario, showing the incoming red half-edges (their count), the focused layer, and an unstructured set of remaining nodes (where the only relevant information is its size).

Thanks to our combinatorial understanding of the layered structure, we derive a new algorithm that computes the exact distribution of ROBDDs up to size $n$ in $k$ variables with a time complexity of $O(kn^3 \log n)$ and an extra memory requirement of $O(n^2)$ for integers. To the best of our knowledge, this is the first polynomial-time algorithm computing the distribution of ROBDD sizes for Boolean functions. Unlike our earlier attempt in [4], which relied on a recursive decomposition of the ROBDD into left and right sub-ROBDDs, our current approach is iterative. Specifically, we compute the distribution layer by layer, allowing us to reuse the first $ℓ$ computations for all ROBDDs that share the same profile ($p_0, \dots, p_{ℓ-1}$).

We present in Fig. 5 the exact distribution of Boolean functions with 16 variables according to their ROBDD size. The red curve represents the probability distribution: the x-axis corresponds to the ROBDD size, and the y-axis indicates the probability of Boolean functions having a given ROBDD size. For 16 variables, we observe that approximately 3.5% of the functions have an ROBDD of size 8 306 (the maximum probability). The maximum size of ROBDDs for 16 variables is 8 845. The blue curve uses a logarithmic scale (base 2) to
<figure><img src="image_9.png" /><figcaption>Figure 5 16-variable Boolean function distribution according to their ROBDD size, ranging from 1 to 8 845.</figcaption></figure>

reveal that the distribution of Boolean functions with small ROBDDs is not constant at 0. Instead, it is simply *extremely* small compared to the peak values around size 8 300. The initial linear segment of the blue curve indicates an exponential growth in the number of ROBDDs as their size increases, up to approximately 6 000.

We significantly improve upon previous work, and all the extrapolated results presented in [14] for Boolean functions with up to 16 variables are now fully and precisely described. Using a personal computer, we can compute an exhaustive count of ROBDDs representing functions with up to 14 variables in just a few minutes. For Boolean functions with 15 and 16 variables, obtaining the full distributions requires a few hours of computation from a high-performance computer, using an optimized implementation and parallelizing.

Beyond computing the distribution of Boolean functions based on their ROBDD size, we are also able to describe the structure of the counted ROBDDs. This enables us to design a combinatorial construction algorithm for these structures. This algorithm, to be published in a future paper, is defined as an unranking algorithm that generates the ROBDD for a given number of variables, size, and rank (the rank corresponds to the position of the structure in a complex total order of ROBDDs of the same size). In this context, unranking algorithms are easily and often adapted to serve as uniform random samplers (for ROBDDs of a given size). Additionally, by leveraging our understanding of the combinatorics underlying the counting sequence, we can adapt the algorithm to sample ROBDDs with a given profile (rather than a global given size), either through the unranking approach or uniform random sampling.

As an illustration, we depict<fnref n="4" /> in Fig. 6 (left) the ROBDD of the *majority Boolean function*<fnref n="5" /> with 15 variables, whose size is only 64. In Fig. 6 (right), we show a uniformly sampled ROBDD with the same profile. Here, the uniform random sampling defines the edges between the nodes while satisfying the usual constraints of ROBDDs. Furthermore, we are able to construct an ROBDD of size 324 with the same profile as the majority function ROBDD, but with 35 variables, in a few seconds on a personal computer: when our focus is on ROBDDs of small sizes, we are able to compute beyond the 16-variable threshold for which we establish the complete distribution. This paper focus *uniquely* on computational aspects for determining the exact distribution of ROBDDs. We plan to present applications to random generation

<footnote n="4">⁴ The ROBDD nodes in Fig. 6 are labeled with integers, but the corresponding Boolean variable can be easily deduced from the layer to which the node belongs.</footnote>

<footnote n="5">⁵ The majority Boolean function returns TRUE if, during its evaluation, the number of TRUE inputs exceeds the number of FALSE inputs.</footnote>
XX:12 Counting ROBDDs With Respect to Size

<figure><img src="image_10.png" /><figcaption>■ **Figure 6** (left) The ROBDD for the majority function with 15 variables. (right) A uniformly sampled ROBDD with the same profile.</figcaption></figure>

of ROBDDs in a future paper.

4.2 Related work

One of the most essential references on the combinatorics of ROBDDs, viewed as directed
acyclic graphs (DAGs), is the volume [11] by Knuth. In our approach, we aim to follow a
similar path as Knuth's, seeking to understand why this data structure has become one of
the most widely used in computer science since the 1990s. Knuth's combinatorial perspective
provides a very general framework and highlights key reasons for its efficiency, while also
addressing some still unresolved questions in the field of ROBDDs. Currently, there is active
research focused on understanding the impact of variable orderings to produce smaller DAGs,
for instance. In our research, however, since we are interested in the complete distribution
of ROBDD sizes for Boolean functions with *k* variables, the chosen variable ordering has no
impact on the results.

An important milestone in understanding the distribution of Boolean functions based on
their ROBDD size was achieved by Wegener [17] and later refined by Gröpl *et al.* [9]. These
authors demonstrated that almost all functions have the same ROBDD size, up to a factor
of $1 + o(1)$, as the number of variables $k$ approaches infinity, a phenomenon known as the
Shannon effect (either strong or weak, depending on the value of $k$). The strong (respectively
weak) Shannon effect asserts that nearly all functions have ROBDD sizes comparable to the
largest ROBDDs, up to a factor of $1 + f(k)$, where $f(k) = o(1)$ (resp. $f(k) = \Omega(1)$) as $k$ tends
to infinity (see also [16]). The reader may find an illustration of this phenomenon in Fig. 5:
the red curve represents the exact probability distribution for $k = 16$ variables. Even for
functions depending on a small number of variables, the bias towards ROBDDs with sizes
close to the largest ones is remarkably strong.

A consequence of these initial analyses is that selecting a Boolean function with a small
ROBDD uniformly at random is a challenging task. This is despite the fact that, in practice,
desirable ROBDDs are often not of exponential size with respect to *k*. We have in mind the
ROBDDs of the symmetrical Boolean functions, which are of quadratic size in *k*, for example.

In [14], the authors investigate the size of ROBDDs as the number of variables *k* increases,
using experimental, numerical, and theoretical approaches. However, their primary method relies on an exhaustive enumeration of the decision trees representing all Boolean functions, which are subsequently compressed into ROBDDS. This approach is severely limited by the doubly exponential growth of the number of Boolean functions with $k$ variables. As a result, they were able to compute exact distributions for $k = 1, \dots, 4$. To extend their results, the authors extrapolated, with great precision, the distributions by sampling decision trees uniformly at random.

Later in the paper [4], we obtained similar combinatorial results. In that work, our global approach relied on a recursive decomposition of ROBDDS into left and right sub-ROBDDS rooted at the main node and using a postorder traversal, to prioritize the apparition of new nodes. Naturally, this decomposition ensures that the left child is a valid ROBDD, but this is not necessarily the case for the rightmost structure, as some pointers may reference nodes within the left child. Consequently, the combinatorics underlying this recursive decomposition is significantly more complex than classical structures, for example binary trees. Nevertheless, the profile of ROBDDS proved to be a valuable tool for improving algorithmic efficiency when calculating the distribution of Boolean functions with $k$ variables. In this initial attempt, our algorithmic approach remained exponential in the size of the ROBDDS, which limited us to computing complete distributions. We introduced a new approach based on a partial recursive decomposition, partitioning ROBDDS according to their profile (which describes the number of nodes per level in the DAG). A key improvement in [4] was the ability to restrict computations to a maximal size $n$ for ROBDDS, in contrast to the exhaustive-oriented approach of [14]. While this method was more efficient, the algorithms still had a complexity of at least $\Omega(n k^{3/2} \cdot k^2 / \log k)$ and required a significant amount of memory. Despite these challenges, after extensive computations, we successfully obtained the exact distributions of ROBDD sizes for up to $k = 9$ variables, partitioning the set of $2^{512}$ Boolean functions into ROBDDS with sizes ranging from 0 to 141. As a comparison, our newer approach, presented in this paper, achieves size $k = 16$ for a set of $2^{65536}$ Boolean functions and maximal size 8445.

# 5 Maximal profile and size of a $k$-variable ROBDD

In order to precisely quantify the complexity of algorithms for counting ROBDDS, we are interested in the maximal number of nodes on any layer of an ROBDD with $k$ variables. It turns out that maximizing the size results also in an ROBDD with maximal number of nodes on any layer. In a sense the DAG is saturated, layer-by-layer.

## 5.1 Profile

In this section, we study profiles of ROBDDS. Let $\mathbf{p} = (p_0, \dots, p_{k-1})$ the profile of an ROBDD with $k$ variables, i.e. the number of nodes in each layer from top to bottom, and the size $P = \sum_i p_i$. We introduce the notation $P_{<i} = \sum_{j<i} p_j$ and $P_{\ge i} = \sum_{j \ge i} p_j$. Note that $P = P_{<i} + P_{\ge i}$ for any $i \in \{0, \dots, k-1\}$ and by convention we state $P_{<0} = 0$ and $P_{\ge k} = 0$.

**Proposition 13 (Profiles).** Let $\mathbf{p} = (p_0, \dots, p_{k-1})$ be a vector of non-negative integers. Then $\mathbf{p}$ is the profile of a valid ROBDD if and only if, for all $0 \le \ell \le k-1$, we have

$$p_{\ell} \le \min \left( P_{<\ell} + 1, P_{\ge \ell} + 2 - \lfloor \sqrt{P_{\ge \ell} + 2} \rfloor \right). \quad (4)$$

**Proof.** Top part of the DAG. From a classic property of binary trees, a binary tree with $P_{<\ell}$ internal nodes has $P_{<\ell} + 1$ outgoing available half-edges for the next level. Hence, we can add up as many nodes on level $\ell$ such that $p_{\ell} \le P_{<\ell} + 1$. This is also a sufficient condition.
XX:14 Counting ROBDDs With Respect to Size

Bottom part of the DAG. Let us denote $B = P_{\ge \ell} + 2$ (number of nodes at and below layer $\ell$, constant nodes included). Then the number of pairs $p_\ell$ (of children) is less than or equal to $(B - p_\ell)(B - p_\ell - 1)$ since each pair must be distinct from the others. This quadratic inequality is easily solved and gives

$$0 \le p_{\ell} \le B - \lfloor \sqrt{B} \rfloor.$$

Finally, a profile satisfying (4) always yields at least a valid ROBDD, as, for any node of any layer, we have always a valid choice for both outgoing edges. ◀

## 5.2 Upper bound for size

In order to maximize the number of nodes, we just have to maximize the profile satisfying inequality (4) of Proposition 13. This question was investigated in [14, 16]. However, we give an equivalent proof, and provide an explicit formula for the number of ROBDDs with $k$ variables stated in the following theorem.

**Theorem 14.** Let $k \ge 1$ be an integer. The maximal number of decision nodes in an ROBDD with $k$ variables is

$$2^{k-\theta} + 2^{2^{\theta}} - 3, \quad \text{with } \theta = \lfloor \log_2 (k - \lfloor \log_2 (k) \rfloor) \rfloor.$$

The result of Theorem 14 has already been stated and proved in [11, Theorem U, Equation (79)], but without the precise value of $\theta$. We propose in the following a more detailed proof. This formula is also given (without any proof) by Pontus von Brömssen on the OEIS website as sequence OEIS A327461$^6$.

The proof relies entirely on the following proposition specifying the maximal profile of a ROBDD.

**Proposition 15 (Maximal profile).** Let $k \ge 1$ be an integer and $\theta = \lfloor \log_2 (k - \lfloor \log_2 (k) \rfloor) \rfloor$. The profile $p = (p_0, \dots, p_{k-1})$ maximizing ROBDD size for $k$ variables satisfies

$$p_{\ell} = \begin{cases} 2^{\ell} & \text{if } \ell < k - \theta \\ 2^{2^{k-\ell}} - 2^{2^{k-\ell-1}} & \text{if } k - \theta \le \ell < k. \end{cases} \quad (5)$$

First, we prove a technical lemma.

**Lemma 16.** Let $k \ge 1$ be an integer. There exists a unique pair of integers $(i, j)$ such that

$$k = 2^i + i + j \text{ with } 0 \le j \le 2^i.$$

Moreover, we have $i = \lfloor \log_2 (k - \lfloor \log_2 (k) \rfloor) \rfloor$.

**Proof.** Define the family of intervals of integers $I_i = [2^i + i, 2^{i+1} + i]$. We easily prove that the intervals are disjoint and that $\bigcup_{i \ge 0} I_i = \mathbb{N}_{>0}$.

Hence, for any positive integer $k$, there is a unique integer $i$ such that $k \in I_i$ and defining $j = k - 2^i$ we get $0 \le j \le 2^i$. With this notation, we obtain an explicit formula: indeed let us write $k = 2^i + i + j$ with $0 \le j \le 2^i$. Consequently,

$$k - \lfloor \log_2 (k) \rfloor = \begin{cases} 2^i + j & \text{if } 0 \le j < 2^i - i, \\ 2^i + j - 1 & \text{if } 2^i - i \le j \le 2^i. \end{cases}$$

In both cases, $0 \le j < 2^i - i$ or $2^i - i \le j \le 2^i$, this yields $i = \lfloor \log_2 (k - \lfloor \log_2 (k) \rfloor) \rfloor$. ◀

<footnote>$^6$Throughout this paper, a reference OEIS A... points to Sloane's Online Encyclopedia of Integer Sequences www oeis org.</footnote>
XX:16 Counting ROBDDs With Respect to Size

the bound $t_ℓ$ is equal to the one for complete binary trees and thus the constraint on non-redundant decision nodes is trivially valid. The second bound $b_ℓ$ ensures that there are sufficiently many nodes below layer $ℓ$ to ensure that all decision nodes at level $ℓ$ can point to different pairs of children. ◀

As an illustration, we provide Table 2 with the first values of parameter $θ$ and the maximal number of decision nodes. A shifted version is presented in OEIS A327461 (each term is shifted by 2, because there the constants are counted in the size).

<table><caption>■ Table 2 The first values of parameter $θ$ and maximal number $M$ of decision nodes for a ROBDD with $k$ variables $1 \le k \le 16$.</caption><thead><tr><th>k</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th><th>16</th></tr></thead><tbody><tr><th>θ</th><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>3</td><td>3</td><td>3</td><td>3</td><td>3</td><td>3</td></tr><tr><th>M</th><td>1</td><td>3</td><td>5</td><td>9</td><td>17</td><td>29</td><td>45</td><td>77</td><td>141</td><td>269</td><td>509</td><td>765</td><td>1277</td><td>2301</td><td>4349</td><td>8445</td></tr></tbody></table>

6 Distribution of ROBDDs with respect to size

The goal of this section is to apply an algebraic framework based on layers.

6.1 Layer configuration

In this section, we formalize the notion of valid layer configuration consisting in the description of a possible layer appearing in at least one ROBDD. Then we present an approach to enumerate the total number of ROBDDs with a specified profile, using this formalization.

In the following, for an integer $n$, we identify $[n]$ with a set of $n$ distinct elements. We describe how to define a layer independently of the others. It enables to pile them up in our combinatorial construction.

► **Definition 17 (Layer configuration).** For positive integers $q, p$ and $X$, let us denote

■ the set $[q]$ of incoming half-edges (we do not know where they come from);

■ the set $[p]$ of nodes in the current layer;

■ the set $[X]$ of destination nodes below the current layer (without knowledge of the layers they are in).

In our setting, all sets $[q]$, $[p]$ and $[X]$ are disjoint.

A layer configuration is a couple $(M, C)$ where

■ $M$ is a map $[q] \to [p] \cup [X]$ such that $M$ is surjective on $[p]$, i.e., $[p] \subseteq M([q])$;

■ $C$ is a sequence of $p$ distinct ordered pairs of distinct elements from $[X]$.

The number of valid layers configurations is denoted by $C_{q,p,X}$.

A layer configuration describes a valid layer in an ROBDD when considering $q$ unconstrained incoming half-edges, $p$ decisions nodes in the layer and $X$ nodes below the layer (see Fig. 7). Here an unconstrained incoming half-edge can point to any of the nodes (current layer included) and thus there are $p+X$ such choices. This formulation enables to state a recurrence on the numbers $C_{q,p,X}$ of valid layer configurations. Indeed, For a layer configuration to be valid, each of the $p$ nodes of the current layer must be pointed by at least one of the $q$ incoming half-edges (otherwise the structure is disconnected), and each of the $p$ nodes gives rise to two outgoing half-edges pointing to distinct pairs formed on the $X$ nodes below the current layer. Intuitively, the map $M$ describes where the incoming edges are pointing to in the current layer, and $C$ encodes the pairs of children of the nodes in the current layer.
<figure><img src="image_11.png" /><figcaption>Figure 7 A schematic view of a layer configuration.</figcaption></figure>

**Lemma 18 (Number of layer configurations).** For $q, p, X \ge 0$, the number $C_{q,p,X}$ of valid layer configurations is given by the recursive formula

$$C_{q,p,X} = \begin{cases} 0 & \text{if } q < p; \\ X^q & \text{if } p = 0; \\ (X+p) \cdot C_{q-1,p,X} + (X^2 - X - (p-1)) \cdot C_{q-1,p-1,X} & \text{otherwise.} \end{cases} \quad (7)$$

We derive an explicit formula for the values $C_{q,p,X}$, we have

$$C_{q,p,X} = \left( \prod_{i=0}^{p-1} (X^2 - X - i) \right) \cdot \left( \sum_{j=0}^{q-p} \binom{q}{j} \left\{ \begin{matrix} q-j \\ p \end{matrix} \right\} X^j \right), \quad (8)$$

where $\binom{q}{j}$ stands for the binomial coefficient and $\binom{n}{k}$ is the Stirling number of the second kind (counting the number ways to partition a set of n objects into k non-empty subsets).

In order to describe the combinatorial interpretation of this recurrence, we focus on the single recursive operation of adding a new edge.

**Proof.** First, in Recurrence (7), the two first cases are immediate. In a layer configuration, the map must be surjective from $[q]$ to $[p]$ which means $C_{q,p,X} = 0$ whenever $q < p$. Also, if $p = 0$, we are just counting mappings from $[q]$ to $[X]$, thus $C_{q,0,X} = X^q$.

Let us now focus on the case when $0 < p \le q$. We are considering a layer with $p$ nodes, with $q$ incoming half-edges and are interested in the possible configurations (plugging incoming half-edges to the top nodes and focusing on the remaining half-edges and the new ones outgoing from the $p$ nodes in the layer). We consider recursively the case starting with $q-1$ incoming half-edges and adding a new one. There are two cases: either the $p$ top nodes where already pointed by at least one of the $q-1$ incoming half-edges or only $p-1$ nodes where pointed by the $q-1$ incoming half-edges. Recall that we consider distinct nodes and distinct half-edges, thus adding a new half-edge or a new node does not imply any choice where to add it: we just append it to previous structure.

- Consider first a valid configuration with $q-1$ incoming half-edges, $p$ nodes in the layer and $p+X$ destinations. If we add a new incoming half-edge, either this half-edge points to one of the $p$ nodes or it crosses the layer for pointing to one of the $X$ nodes. This gives $(p+X)C_{q-1,p,X}$ possibilities.
XX:18 Counting ROBDDs With Respect to Size

Now suppose we have $q-1$ first incoming edges which only point to a set of $p-1$ nodes in the layer, leaving out an orphan node. This forces the new incoming half-edge to point to this orphan node to get a valid configuration. Now the pair of children attached to this node must be (i) a pair of distinct destination nodes; (ii) distinct from the other pairs coming out of the $p-1$ nodes in the same layer. Since there are $X$ destination nodes, we get $X(X-1) - (p-1)$ choices for this new pair of half-edges. We count in this case $(X^2 - X - (p-1))C_{q-1,p-1,X}$ configurations.

Putting together all these possibilities, Equation (7) is proved.

For the second part of the lemma, a proof by recurrence using properties of binomial numbers and Stirling numbers of the second kind leads to the result. ◀

We stress that the counting formulas (7) or (8) for the number of configurations is expressed thanks to a polynomial from $\mathbb{Z}[X]$, that is a linear combination of monomials. A key property of our approach is that each monomial $X^\ell$ in the formula can be directly interpreted as a sequence of $\ell$ unconstrained (or free) half-edges. This is the basis for our algebraic presentation of counting formulas. Fundamentally, we introduce a robust algebraic representation to encapsulate a form of inclusion-exclusion principle. This leads to the definition of a linear transformation on polynomials through substitutions, reformulating Lemma 18 in the following definition.

**Definition 19.** We define the family $(\phi_r)_{r \ge 0}$ of linear mappings, where each mapping $\phi_r : \mathbb{Z}[X] \to \mathbb{Z}[X]$ is defined with respect to the canonical basis $(X^m)_{m \ge 0}$ of monomials as

$$ \phi_r(X^m) = \begin{cases} 0 & \text{if } m < r; \\ X^m & \text{if } r = 0; \\ (X+r) \cdot \phi_r(X^{m-1}) + (X^2 - X - (r-1)) \cdot \phi_{r-1}(X^{m-1}) & \text{otherwise.} \end{cases} \quad (9) $$

Let us note this is only a rewriting of Lemma 18, i.e., we have $\phi_r(X^m) = C_{m,r,X}$.

The linearity property of the mappings $(\phi_r)_{r \ge 0}$ will prove to be crucial for achieving polynomial complexity of our counting algorithm. We recall that for a linear map $f : \mathbb{Z}[X] \to \mathbb{Z}[X]$ and two polynomials $P$ and $Q$ in $\mathbb{Z}[X]$, $f(P+Q) = f(P) + f(Q)$, and furthermore for any scalar $\lambda \in \mathbb{Z}$ we have $f(\lambda P) = \lambda f(P)$.

The polynomial representation of $\phi_r(X^m)$ translates an inclusion-exclusion principle, thus coefficients may be negative integers.

## 6.2 Basic counting

In the next theorem, we state the core result of this paper. It gives access to the number of multi-rooted ROBDDs for a given profile. Then, obviously, we can specialize this theorem to count the number of ROBDDs for a given profile.

**Theorem 20 (Multi-rooted ROBDDs counting formula).** Let $\mathbf{p} = (p_0, \dots, p_{k-1}) \in \mathbb{N}^k$ and $\mathbf{q} = (q_0, \dots, q_{k-1}, q_k) \in \mathbb{N}^{k+1}$. Let us consider multi-rooted ROBDDs with profile $\mathbf{p}$ and a set of incoming half-edges such that, for each layer $\mathcal{L}_i$ of level $i \in \{0, \dots, k\}$, there are $q_i$ incoming half-edges going to that layer or below. (By convention the layer $\mathcal{L}_k$ contains the two sink nodes.) The number of such combinatorial structures is counted by

$$ X^{q_k} \phi_{p_{k-1}}(X^{q_{k-1}} \phi_{p_{k-2}}(\dots X^{q_2} \phi_{p_1}(X^{q_1} \phi_{p_0}(X^{q_0}))\dots)) \text{ evaluated at } X=2. \quad (10) $$

We stress here that although the sequence $\mathbf{q} = (q_0, \dots, q_{k-1}, q_k)$ seems very similar to the sequence $\mathbf{u}$ of Definition 7, it is not exactly the same. Half-edges in Definition 7 are
totally specified with the level they are going to. In Theorem 20, the sequence **q** gives a more relaxed constraint for ROBDDs. For instance, the particular multi-rooted ROBDD depicted in Fig. 4 (right) has node profile **p** = (0, 0, 0, 3, 3, 1) and a set of incoming half-edges with profile **u** = (0, 0, 0, 4, 3, 0, 0). The counting formula will encompass this particular multi-rooted ROBDD whenever we consider the same node profile **p** = (0, 0, 0, 3, 3, 1) and a sequence **q** = (q₀, q₁, q₂, q₃, q₄, q₅, q₆) such that for all 0 ≤ *i* ≤ 5, Σᵢⱼ=₀ qⱼ ≥ Σᵢⱼ=₀ uⱼ and Σₚⱼ=₀ qⱼ = Σₚⱼ=₀ uⱼ.

<figure><img src="image_12.png" /><figcaption>■ **Figure 8** Illustration for the proof of 20. Two layers $\mathcal{L}$ and $\mathcal{L}'$ containing respectively $p$ and $p'$ are piled up. Straight half-edges are free to point anywhere below (there are respectively $q$ and $q'$ such half-edges incoming on layer $\mathcal{L}$ and $\mathcal{L}'$). Curved half-edges are non-free and must fit the constraints of the structure of an ROBDD.</figcaption></figure>

**Proof.** Let us consider two successive layers $\mathcal{L}$ and $\mathcal{L}'$ containing respectively $p$ and $p'$ nodes, and such that $q$ (respectively $q'$) incoming half-edges reside in layer $\mathcal{L}$ or below (respectively in layer $\mathcal{L}'$ or below). There are also $X$ nodes underneath layer $\mathcal{L}'$ (see Fig. 8).

By Lemma 18, if we had *j* independent incoming half-edges on layer *L*, this would entail $\phi_{p'}(X^j)$ possibilities for outgoing half-edges from layer *L*. The crucial point is that incoming half-edges from above layer *L*' are of course not independent.

The number of layer configurations for $\mathcal{L}$ is given by $C_{q,p,Y} = P(Y) = \sum_{j=0}^{n} a_j Y^j$, a polynomial in $\mathbb{Z}[Y]$ and where $Y = X + p'$. We interpret each monomial $Y^j$ in $\mathbb{P}(Y)$ as the number of ways $j$ independent outgoing edges can point to a set of $Y$ nodes, corresponding with $Y^j$ (free) choices. In a inclusion-exclusion flavor, there is a weight for each event given by the coefficients of the polynomial $P(Y)$. Also $q'$ independent half-edges are coming directly on layer $\mathcal{L}'$, so that the number of choices for destinations of all half-edges is counted by

$$ \sum_{i=0}^{n} a_j C_{j+q',p',X} = \sum_{i=0}^{n} a_j \varphi_{p'}(X^{j+q'}) = \varphi_{p'}(X^{q'} \sum_{j=0}^{n} a_j X^j) = \varphi_{p'}(X^{q'} \varphi_p(X^q)). $$

The process can be iterated for more layers yielding Equation (10). The final evaluation at $X = 2$ comes from the fact that there are two nodes (the constants $\top$ and $\bot$) under the full stack of layers. ◀

We introduce the following to simplify notation.

► **Definition 21.** For an application $\Psi(X)$ depending on $X$, $\text{eval}_2(\Psi(X))$ is the evaluation of $\Psi(X)$ at $X = 2$.
XX:20 Counting ROBDDs With Respect to Size

We stress here that the evaluation is made after applying $\Psi$ and that, in general, $\text{eval}_2(\Psi(X)) \neq \Psi(2)$, for instance if $\Psi$ is a linear map from $\mathbb{Z}[X]$ to $\mathbb{Z}[X]$.

As a first corollary, we get a way for counting the number of ROBDDs having a given profile. Indeed, we just consider a profile for the set of nodes and a one half-edge pointing to the layer of the root.

**Corollary 22.** *The number of k-variable ROBDDs for a profile $\mathbf{p} = (p_0, p_1, \dots, p_{k-1}) \in \mathbb{N}^k$ is counted by*

$$ \text{eval}_2 (\phi_{p_{k-1}}(\phi_{p_{k-2}}(\dots \phi_{p_1}(\phi_{p_0}(X))\dots))). \quad (11) $$

In the ROBDD case, we take $\mathbf{q} = (q_0 = 1, 0, \dots, 0)$, meaning there is one source node, i.e. the root, and one incoming half-edge pointing this root. Also, if we wish to consider that the root of is labeled by $x_0$, we just have to take $p_0 = 1$.

**Example 23.** Let us consider a profile $\mathbf{p} = (1, 2, 4, 2)$ for 4 variables $x_0, \dots, x_3$ and $\mathbf{q} = (1, 0, 0, 0, 0)$ in (10). Then, for $0 \le i \le 3$, we compute iteratively $\phi_{p_i}((\dots \phi_{p_0}(X))\dots)$:

$$ \begin{aligned} X &\xrightarrow{\phi_1} X^2 - X \\ &\xrightarrow{\phi_2} X^4 - 2X^3 + X \\ &\xrightarrow{\phi_4} X^8 - 4X^7 + 14X^5 - 6X^4 - 16X^3 + 5X^2 + 6X \\ &\xrightarrow{\phi_2} 28X^{10} + 28X^9 - 98X^8 - 112X^7 + 76X^6 + 92X^5 - 12X^4 - 8X^3 + 6X^2. \end{aligned} $$

Evaluating the last polynomial at $X = 2$, we get that there are 11160 ROBDDs with profile (1, 2, 4, 2). The power of our approach is that we could have stopped at any iteration, still getting the number of ROBDDs for the considered truncated profile. Noting $\phi_p(\cdot) = \phi_{p_i}((\dots \phi_{p_0}(\cdot))\dots)$ for $\mathbf{p} = (p_0, \dots, p_i)$, we get for successively for profile (1, 2, 4, 2)

<table><thead><tr><th><b>p</b></th><th><i>&phi;<sub>p</sub>(X)</i></th><th><i>eval<sub>2</sub>(&phi;<sub>p</sub>(X))</i></th></tr></thead><tbody><tr><td>( )</td><td><i>X</i></td><td>2</td></tr><tr><td>(1)</td><td><i>X<sup>2</sup> &minus; X</i></td><td>2</td></tr><tr><td>(1, 2)</td><td><i>X<sup>4</sup> &minus; 2X<sup>3</sup> + X</i></td><td>2</td></tr><tr><td>(1, 2, 4)</td><td><i>X<sup>8</sup> &minus; 4X<sup>7</sup> + 14X<sup>5</sup> &minus; 6X<sup>4</sup> &minus; 16X<sup>3</sup> + 5X<sup>2</sup> + 6X</i></td><td>0</td></tr><tr><td>(1, 2, 4, 2)</td><td><i>28X<sup>10</sup> + 28X<sup>9</sup> &minus; 98X<sup>8</sup> &minus; 112X<sup>7</sup> + 76X<sup>6</sup> + 92X<sup>5</sup> &minus; 12X<sup>4</sup> &minus; 8X<sup>3</sup> + 6X<sup>2</sup></i></td><td>11160</td></tr></tbody></table>

Note that, by convention for an empty profile, $\phi_p$ is the identity. The number 0 when considering the profile (1, 2, 4) may seem counterintuitive at first, but indeed a ROBDD can only have up to 2 nodes on its last layer, otherwise one node has to be a duplicate of one of the others. So there are indeed no ROBDDs with for profile (1, 2, 4).

## 6.3 Generating function for ROBDD size

The main goal of this section is to compute the distribution of Boolean functions in $k$ variables according to the ROBDD size. For $f \in \mathcal{B}_k$ a Boolean function, we let $\lambda(f)$ be the size of its ROBDD, i.e., its number of decision nodes. A convenient way to represent the distribution of the size $\lambda$ on $\mathcal{B}_k$ consists in computing the generating function [8]

$$ F_k(u) = \sum_{f \in \mathcal{B}_k} u^{\lambda(f)} = \sum_{i \ge 0} f_i u^i, $$
where $u$ is a formal variable marking the size. Then for $i \ge 0$, the coefficient<fnref n="8" /> $f_i = [u^i]F_k(u)$ is the number of ROBDDs of size $i$ with $k$ variables.

We first extend the formalism introduced in Section 6.2 and define a linear map $\varphi : \mathbb{Z}[u, X] \to \mathbb{Z}[u, X]$.

**Definition 24.** The linear map $\varphi : \mathbb{Z}[u, X] \to \mathbb{Z}[u, X]$ is defined via its action on the basis $(u^\ell X^m)_{\ell,m \ge 0}$ as

$$ \varphi : u^\ell X^m \mapsto \varphi(u^\ell X^m) = \sum_{r=0}^{m} u^{\ell+r} \phi_r(X^m). \qquad (12) $$

Using the notation $\mathrm{eval}_2(\cdot)$ for evaluating at $X = 2$, we have the following theorem.

**Theorem 25 (Generating function for ROBDD size).** The generating function enumerating Boolean functions by considering the ROBDD size is given by

$$ F_k(u) = \mathrm{eval}_2(\varphi^k(X)), $$

where $\varphi^k$ denotes the composition $\varphi \circ \dots \circ \varphi$.

**Proof.** Each application of $\varphi$ corresponds with adding a layer. The formal variable $u$ marks the number of decision nodes added on the current layer. ◀

# 7 Algorithms and complexity

This section is organized in three parts. Our approach relies on the linear mappings on $\mathbb{Z}[X]$ introduced in Definition 19. So we first present a convenient presentation for these linear mappings and a complexity analysis of the algorithms computing them. Then we present an algorithm to count the number of ROBDDs fitting a given profile $p$. In the last part, we present two algorithms computing the full distribution of ROBDDs with respect to size for a fixed number of variables $k$.

The time and space complexities are measured respectively in terms of arithmetical operations on $\mathbb{Z}$ and memory space used to store arbitrarily large integers in $\mathbb{Z}$.

The reader can find an implementation of the following algorithms in our ROBDD counting library.

As will become clear in this section, the main complexity issue is computing a representation of the family of linear mappings $(\phi_r)_{r \ge 0}$ which necessitates $O(n^3)$ memory space for storing integers. As $n$ may be very large, we will soon not be able to afford so much memory space. Consequently, we will present a strategy to keep memory space at $O(n^2)$, of course at the expanse of a degraded time complexity.

## 7.1 Linear mappings

First we focus on the complexity of computing the linear mappings $(\phi_r)_{r \ge 0}$ on the canonical basis of monomials $(X^\ell)_{\ell \ge 0}$.

Let us fix $k$ to be the number of variables (or layers) and let $n$ be the number of nodes. In our layer approach, when computing $\phi_r(X^m)$, implicitly we consider a case where there

<footnote n="8">⁸ The notation $[u^i]F_k(u)$ consists in the extraction of the coefficient of monomial $u^i$ in $F_k(u)$.</footnote>
XX:22 Counting ROBDDs With Respect to Size

are $m$ incoming half-edges from upper layers, meaning there are at most $m-1$ nodes above the current layer, and $r$ nodes in the current layer. A rough estimate, still giving the good order of growth, is that $m = O(n)$ and $r = O(n)$.

Looking at memory storage constraints, if we want to store all coefficients of polynomials

$$ (\phi_r(X^m))_{0 \le r \le m \le M}, $$

with $M = O(n)$, we need memory space for $O(n^3)$ integer coefficients, as each $\phi_r(X^m)$ is a polynomial of degree $m+r$.

In the worst case, when $n = O(2^k/k)$, this entails memory space $O(2^{3k}/k^3)$ for storing coefficients in $\mathbb{Z}$. Additionally, these coefficients may be integers of size $O(2^k)$ bits. Clearly computing and storing these coefficients is feasible only for relatively$^9$ small values of $k$.

We may have two different approaches for computing these mappings using either the recursive formula (9), or the closed formula (8).

Recursive formula.

We recall Equation (9) gives

$$ \phi_r(X^m) = \begin{cases} 0 & \text{if } m < r; \\ X^m & \text{if } r = 0; \\ (X+r)\phi_r(X^{m-1}) + (X^2 - X - (r-1))\phi_{r-1}(X^{m-1}) & \text{otherwise.} \end{cases} \quad (13) $$

This formula resembles (in structure) the one underlying the famous Pascal's triangle. It is possible to compute sequentially this triangle row after row, keeping in memory only the previous row.

► **Example 26.** As an example, we give the three first row of the triangle $(\phi_r(X^m))_{0 \le r \le m \le 3}$:

<table><thead><tr><th>r<br>m</th><th>0</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><th>0</th><td>1</td><td>-</td><td>-</td><td>-</td></tr><tr><th>1</th><td>X</td><td>X<sup>2</sup> - X</td><td>-</td><td>-</td></tr><tr><th>2</th><td>X<sup>2</sup></td><td>2X<sup>3</sup> - X<sup>2</sup> - X</td><td>X<sup>4</sup> - 2X<sup>3</sup> + X</td><td>-</td></tr><tr><th>3</th><td>X<sup>3</sup></td><td>3X<sup>4</sup> - 2X<sup>2</sup> - X</td><td>3X<sup>5</sup> - 3X<sup>4</sup> - 6X<sup>3</sup> + 3X<sup>2</sup> + 3X</td><td>X<sup>6</sup> - 3X<sup>5</sup> + 5X<sup>3</sup> - X<sup>2</sup> - 2X</td></tr></tbody></table>

Moreover, suppose the $(m-1)$-th row is computed. Multiplying a polynomial of degree $d$ by polynomials of degree 1 or 2 is easily done by performing $O(d)$ additions on integers (using shift-and-add techniques). Since polynomials $\phi_r(X^{m-1})$ and $\phi_{r-1}(X^{m-1})$ are polynomials of degree $m+r-1$ and $m+r-2$, we compute $\phi_r(X^m)$ using $O(m+r)$ additions of integers, i.e., it is linear in the size of the output $\phi_r(X^m)$ (which has $m+r$ coefficients). The $m$-th row of the triangle consists in $m+1$ polynomials of respective degree $m, m+1, \dots, 2m$. Hence, this row of polynomials necessitates $O(m^2)$ integer coefficients.

We summarize the results of this subsection in the following proposition.

► **Proposition 27.** The family of linear mappings $(\phi_r)_{0 \le r \le R}$ (with $R = O(n)$) represented as polynomials via their action on the basis $(X^i)_{i \ge 0}$ is computed in time $O(n^3)$ and space $O(n^3)$. If we only use them sequentially, with respect to $m$, $(\phi_r(X^m))_{0 \le r \le R}$, we can keep memory storage at $O(n^2)$.

<footnote n="9">⁹ We managed $k = 16$ with a careful implementation and a computer with 512 GB RAM memory.</footnote>
**Direct formula.**

In the case we want only to compute $\phi_r(X^m)$ for a given $r$ and a given $m$, we can use (8), that is

$$ \phi_r(X^m) = \left( \prod_{i=0}^{r-1} (X^2 - X - i) \right) \cdot \left( \sum_{j=0}^{m-r} \binom{m}{j} \left\{ \begin{matrix} m-j \\ r \end{matrix} \right\} X^j \right). $$

Looking at the formula, we need to compute/store binomial coefficients as well as Stirling numbers of the second kind (supposing $O(m^2)$ memory storage). Then $\phi_r(X^m)$ is the product of one polynomial of degree $2r$ (which is computed in time $O(r^2)$ and does not depend on $m$) and another one of degree $m-r$ resulting in a time complexity of $O((m+r)\log(m+r))$ where $m+r$ is the degree of the resulting polynomial.

Using the direct formula could be useful for computing the number of ROBDDs for a fixed profile, but it is not competitive against the recursive approach for computing the whole distribution for $k$ variables. If $m = O(n)$ and $r = O(m)$, we get $O(n^2)$ time complexity and $O(n^2)$ space complexity for computing one polynomial $\phi_r(X^m)$.

## 7.2 Fixed profile ROBDDs counting

In this subsection we address the problem of computing the number of ROBDDs with a given profile $p$. Although this algorithm is not used for computing the distribution, it provides useful insight.

The pseudocode provided in Algorithm 1 is a direct application of Corollary 22. The basic block computes $\phi_r(P)$ for $r \ge 0$ for any polynomial $P$ (see Algorithm 2 based on the linearity of $\phi_r$).

**Algorithm 1** Computing eval$_2(\phi_p(X))$
**Input:** a profile $p = (p_0, \dots, p_{k-1})$
**Output:** the number of ROBDDs with profile $p$
$P(X) \leftarrow X$
**for** $i$ **from** 0 **to** $k-1$ **do**
$\lfloor P(X) \leftarrow \phi_{p_i}(P(X)) \rfloor$
**return** eval$_2(P(X))$

**Algorithm 2** Computing $\phi_r(P)$
**Input:** an integer $r \ge 0$, a polynomial $P(X) = \sum_{m=0}^{d} p_m X^m \in \mathbb{Z}[X]$ 
**Output:** $\phi_r(P) \in \mathbb{Z}[X]$ 
$Q(X) \leftarrow 0$
**for** $m$ **from** $r$ **to** $d$ **do**
$\lfloor Q(X) \leftarrow Q(X) + p_m \phi_r(X^m) \rfloor$
**return** $Q$

The following Propositions 28 and 29 state the complexity of these algorithms supposing the linear mappings have already been computed. This means the resources (time and memory) necessary to compute the mappings are not taken into account in the two following propositions.

**Proposition 28 (Complexity of the basic step).** Let $P$ be a polynomial of degree $d$. Algorithm 2 computes $\phi_r(P)$ and performs $O(rd + d^2)$ arithmetical operations over $\mathbb{Z}$ to compute $\phi_r(P)$, using $O(d^2)$ memory space.

**Proof.** Each polynomial $\phi_r(X^m)$ is of degree $r + m = O(r + d)$. There are $d$ additions of polynomials of degree $O(r + d)$, hence the number of operations needed on coefficients is $O(rd + d^2)$ if $r > 0$ (and $O(1)$ if $r = 0$ since $\phi_0$ is the identity).

<figure><img src="image_13.png" /></figure>
**Proposition 29.** *Algorithm 1 computes the number of ROBDDs with k variables, with the given profile $\mathbf{p} = (p_0, \dots, p_{k-1})$ and size $n = \sum_i p_i$. It performs $O(kn^2)$ arithmetical operations over $\mathbb{Z}$ and uses $O(n)$ extra memory space to store integers.*

**Proof.** The number of ROBDDs is $\text{eval}_2(\phi_p(X))$. The polynomial $\phi_p(X)$ is computed by iterating $k$ times a linear map of type $\phi_r$ starting from an initial polynomial $X$. By Proposition 28, the algorithm performs $O(n^2)$ operations for each iteration since polynomials have $O(n)$ coefficients. The total computation thus performs $O(kn^2)$ arithmetical operations over $\mathbb{Z}$ and use $O(n)$ memory space to store coefficients. Evaluating $\phi_p(X^m)$ at $X = 2$ can be done in time complexity $O(n)$ (by Horner's method for instance). ◀

**Remark.** The time complexity when computing the number of ROBDDs with a fixed profile is dominated by the computation of linear mappings $(\phi_r)_{r \ge 0}$. If we compute on demand the linear mappings needed using the direct explicit formula, we get $O(kn^2 \log n)$ time complexity and $O(n^2)$ memory space. If we use the recursive approach for computing linear mappings, only storing in memory the ones we really use, we get $O(n^3 + kn^2)$ time complexity and $O(kn^2)$ for storing mappings.

## 7.3 Size-distribution of ROBDDs

We next present algorithms for computing the generating function $F_k(u)$ given in Proposition 25 enumerating Boolean functions for $k$ Boolean variables where the ROBDD size is marked by the formal variable $u$

$$F_k(u) = \text{eval}_2(\varphi^k(X)), \quad \text{where } \varphi^k \text{ denotes the composition} \underbrace{\varphi \circ \dots \circ \varphi}_{k \text{ times}},$$

and $\varphi(u^l X^m) = \sum_{r=0}^{m} u^{l+r} \phi_r(X)$ is introduced in Definition 24.

### A first algorithm

A straightforward approach is an application of the formula proved in Proposition 25, i.e. iterating $\varphi$.

We introduce a convenient representation for linear mapping $\varphi$ through its action on the canonical basis $(X^i)_{i \ge 0}$. We pose $P_i^{(m)}(u) = [X^i]\varphi(X^m) \in \mathbb{Z}[u]$, i.e. $P_i^{(m)}(u)$ is the coefficient of $X^i$ in $\varphi(X^m)$, and thus we write

$$\varphi(X^m) = \sum_{i=0}^{2m} P_i^{(m)}(u)X^i. \qquad (14)$$

A differential equation links $\varphi(X^m)$ to $\varphi(X^{m-1})$. Indeed, we get from (12) and (9)

$$\varphi(X^m) = \sum_{r=0}^{m} u^r \phi_r(X^m) = \begin{cases} 1 & \text{if } m=0; \\ u(X^2 - X - u \frac{\partial}{\partial u})\varphi(X^{m-1}) & \text{if } m > 0. \end{cases} \qquad (15)$$

Then, from (15) we derive the recurrence

$$P_i^{(m)}(u) = uP_{i-2}^{(m-1)}(u) + (1-u)P_{i-1}^{(m-1)}(u) + (1-u)u\frac{\partial}{\partial u}P_i^{(m-1)}(u), \qquad (16)$$

which in turn allows computing efficiently $\varphi(X^m)$. In the case we use $\varphi(X^m)$ for consecutive values $m = 0, 1, 2, \dots$, we can profit from the algebraic structure of polynomials $(\varphi(X^m))_{m>0}$
to compute them keeping only the previous bivariate polynomial: $\varphi(X^m)$ only depends on $\varphi(X^{m-1})$. This allows to keep memory requirements to $O(n^2)$ coefficients. We use this "trick" in Algorithms 3 on Line (⋆). Of course, this is a kind of inefficient since we could have stored all bivariate polynomials for future use to avoid doing the same computation again and again. But this would be at the expense of $O(n^3)$ memory space. Thus, the algorithmic strategy depends on the balance between time efficiency (although still of the same order) and memory space we wish have at disposal.

<figure><img src="image_14.png" /><figcaption>**Algorithm 3 Computing $\varphi(Q(u, X))$**</figcaption></figure>

**Input:** A bivariate polynomial $Q(u, X) = \sum_{m=1}^{d} q_m(u) X^m \in \mathbb{Z}[u, X]$ and $\deg_u(q_m(u)) \le d$
**Output:** $\varphi(Q(u, X)) \in \mathbb{Z}[u, X]$
$S(u, X) \leftarrow 1 \quad \triangleright \varphi(X^0)$
$R(u, X) \leftarrow 0$
**for** $m$ **from** 1 **to** $d$ **do**
> $S(u, X) \leftarrow u(X^2 - X - \frac{\partial}{\partial u})S(u, X)$ \quad (⋆)
> $\triangleright S(u, X) = \varphi(X^m)$ **computed in $O(m^2)$ time and space**
> **using (15) and (16)**
> $R(u, X) \leftarrow R(u, X) + q_m(u)S(u, X)$
**return** $R(u, X)$

In Algorithm 3, in the worst case, the bivariate polynomial $Q(u, X)$ may be of $\deg_X(Q) = n + 1$ and $\deg_u(Q) = n$ (a tree with $n$ nodes marked by the formal variable $u$ has exactly $n + 1$ outgoing half-edges corresponding to the variable $X$) and thus has $O(n^2)$ coefficients. There are two main steps in the inner loop:

(i) updating $S(u, X)$ (the current $\varphi(X^m)$) is done in $O(n^2)$ arithmetic operations;

(ii) updating $R(u, X)$ (the partial result) is done in $O(n^2+nM(n))$, where the quantity $M(n)$ is the number of operations required to multiply two polynomials of degree $O(n)$.

Naive multiplication of two polynomials of degree $n$ yields $M(n) = O(n^2)$ arithmetical operations on integers. A more refined approach may achieve $M(n) = O(n \log n)$ operations for polynomials of large degree. The total time complexity of Algorithm 3 is thus $O(n^3 \log n)$ if $\deg_X(Q(u, X)) = O(n)$.

Iterating $k$ times the application $\varphi$ starting with the polynomial $X$, and then evaluating at $X = 2$ yields Algorithm 4 which performs $O(kn^3 \log n)$ arithmetic operations using $O(n^2)$ memory storage. The last step, evaluating $Q(u, X)$ at $X = 2$, is done by substituting $X = 2$ and adding the resulting polynomials of $\mathbb{Z}[u]$ (there are $O(n)$ of these) resulting in a $O(n^2)$ complexity.

<figure><img src="image_15.png" /><figcaption>**Algorithm 4 Computing $F_k(u)$**</figcaption></figure>

**Input:** An integer $k \ge 0$
**Output:** Size distribution generating function $F_k(u) \in \mathbb{Z}[u]$ for ROBDDS with $k$ variables
$Q(u, X) \leftarrow X \quad \triangleright Q \in \mathbb{Z}[u, X]$
**for** $\ell$ **from** 0 **to** $k-1$ **do**
> $Q(u, X) \leftarrow \varphi(Q(u, X))$
**return** $\mathrm{eval}_2(Q(u, X))$

► **Remark.** In practice, we can truncate polynomials, keeping only the terms useful along the computation. Indeed, the formal variable $u$ marks the number of nodes, and the degree in
XX:26 Counting ROBDDs With Respect to Size

$X$ is relative to the number of nodes in upper levels. For variable $X$, if we add a layer of $r$ nodes to a top tree with $T$ nodes, we are assured that we will only need to compute some $\varphi(X^i)$ for $i \le T + 1$: we can truncate all resulting polynomials in the variable $X$ at degree less or equal to $T + r + 1$ (the maximal number of outgoing half-edges after adding the layer). Conversely, for variable $u$, we can ignore all term $u^j$, where $j$ exceeds the maximal number of nodes.

For instance for 4 variables, maximal size is 9: we could only keep 54 coefficients out of 134 in the bivariate polynomial $\varphi^4(X)$ leaving out all monomials of degree strictly more than 9 in $u$ and strictly more than 10 in $X$. We could apply these optimizations in previous Algorithm 4, but it is a bit cumbersome to implement and specify. Next section presents a bottom-up approach which naturally computes exactly the coefficients that are needed and nothing more.

An improved algorithm

There is room for improvement in the previous algorithm. The main ingredients for efficiency gain are

(i) a bottom-up approach, i.e., going from the bottom layer to the top layer and computing quantities $\varphi^\ell(X^m)$ evaluated at $X = 2$ using a recurrence on $\ell$;

(ii) using our knowledge of the maximal profile to control the size (i.e., degree) of the polynomials, and thus compute only the coefficients that are really needed.

Regarding (i), we first recall that the notation $\text{eval}_2(P(u, X))$ for a bivariate polynomial $P(u, X)$ corresponds to the evaluation at $X = 2$. We will use the recurrence obtained thanks to the linearity of $\varphi$

$$ \begin{aligned} \text{eval}_2 (\varphi^{\ell+1}(X^m)) &= \text{eval}_2 (\varphi^{\ell}(\varphi(X^m))) \\ &= \text{eval}_2 \left( \varphi^{\ell} \left( \sum_{j=0}^{2m} P_j^{(m)}(u) X^j \right) \right) \\ &= \sum_{j=0}^{2m} P_j^{(m)}(u) \text{eval}_2 (\varphi^{\ell}(X^j)). \end{aligned} \tag{17} $$

This gives access to an efficient way of computing $(\text{eval}_2(\varphi^{\ell+1}(X^m)))_{0\le m \le n+1}$ from $(\text{eval}_2(\varphi^\ell(X^m)))_{0\le m \le n}$ if we have access to the representation of $\varphi$ via (14) and (16). For $\ell$ fixed, $\text{eval}_2(\varphi^\ell(X^m))$ is a polynomial of degree $O(n)$ in the variable $u$. Equation (17) uses $2m = O(n)$ multiplications of two polynomials of degree $O(n)$ in the variable $u$, giving a $O(n^2 \log n)$ complexity. Hence, computing the whole sequence for $0 \le m \le n + 1$ (and fixed $\ell$) yields a total of $O(n^2)$ coefficients computed thanks to $O(n^3 \log n)$ arithmetical operation on integers.

As for (ii), given the maximal profile of a ROBDD, at a given layer $\ell$, we know exactly the number $T$ of nodes in upper layers. Then, we only need to consider $\varphi(X^m)$ for $0 \le m \le T + 1$ (again because a tree with $T$ internal nodes has $T + 1$ outgoing half-edges which is the upper bound for the number of outgoing edges in a DAG). For a ROBDD of size $n$, the number of nodes in any layer is $O(n)$.

This approach yields Algorithm 5 in the Appendix, which has $O(kn^3 \log n)$ time complexity and necessitates $O(n^2)$ integer coefficients in memory. Although the complexity is the same as the one of Algorithm 4, the involved constants in the big-O's are smaller. For instance, the number of coefficients effectively computed is approximately halved even when truncating polynomials. Additionally, the code can easily be parallelized. Note that a layer with $m$ incoming half-edges and $r$ nodes results in at most $m + r$ outgoing edges. Hence, in the most
inner loop of Algorithm 5, we may restrict the number of outgoing half-edges to be at most $m + \min(m, p_{\max})$, where $p_{\max}$ is the maximal number of nodes in the current layer (for a given $k$, see Proposition 15). Indeed, the number $r$ of nodes we can add to the layer, is less or equal to $m$ (to preserve connectivity of the DAG) and also $p_{\max}$ (by definition).

Finally, we summarize the results in the following theorem.

**Theorem 30.** Let $n = O(2^k/k)$ the maximal size of a ROBDD for $k$ variables and $F_k(u)$ the generating function (given in Proposition 25) enumerating Boolean functions for $k$ Boolean variables where the ROBDD size is marked by the formal variable $u$. Algorithms 4 or 5 compute $F_k(u)$ using $O(kn^3 \log n) = O(2^{3k}/k)$ arithmetical operations on integers and $O(n^2) = O(2^{2k}/k^2)$ memory space for integers coefficients.

The total time and space complexities are both polynomial with respect to the maximal size $O(2^k/k)$ of a ROBDD for $k$ variables. Hence, this is a huge improvement compared to exponential brute force algorithms enumerating all $2^{2^k}$ Boolean functions and then computing their ROBDD size obtained after a compaction process. With a careful implementation, we achieve the computation of $F_k(u)$ for $k$ up to 16 variables on a high-performance computer with 512 GB RAM memory. We use the flint [15] library for operations on polynomials and OpenMP [6] for parallelizing. This implementation leads to the complete distribution for Boolean functions in 16 variables represented in Fig. 5.

## 8 Conclusion

As an application of the counting approach of this paper, we are able to draw efficiently and uniformly at random ROBDDs either according to a given size, or even a given profile. This could give an experimental approach to better understand variable reordering procedures for ROBDDs. The tools are already present in our BDDgen library for counting and generating. A dedicated paper is under preparation.

This is a great improvement when comparing to the classical uniform random generation over the set of Boolean functions, that is drastically biased to the largest ROBDDs due to the Shannon effect. For instance with 12 variables, the probability of drawing uniformly a Boolean function giving an ROBDD of (quadratic in $k$) size $144 = 2^2$ is approximately $1.212 \cdot 10^{-957}$.

An interesting future work consists in exhibiting the BDD structures where our counting and sampling methods can be applied, such as (non-reduced) OBDD, or ZDD for example.

Finally, another research direction consists in noting that the generating function of ROBDDs with both size and number of variables can be specified thanks to an iterative process as in Theorem 25. It would be interesting to see if the machinery of analytic combinatorics [8] is amenable to this kind of specification.

## References

1. R. E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. *IEEE Trans. Computers*, 35(8):677-691, 1986.

2. W.-K. Chen, editor. *The VLSI Handbook*. CRC Press, 1999. doi:10.1201/9781420049671.

3. K. Claessen and J. Hughes. Quickcheck: A lightweight tool for random testing of haskell programs. *SIGPLAN Not.*, 35(9):268-279, 2000.

4. J. Clément and A. Genitrini. Binary decision diagrams: From tree compaction to sampling. In *LATIN: Theoretical Informatics - 14th Latin American Symposium, Proceedings*, volume 12118 of LNCS, pages 571-583. Springer, 2020.
5 J. Clément and A. Genitrini. An Iterative Approach for Counting Reduced Ordered Binary Decision Diagrams. In *48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)*, volume 272 of Leibniz International Proceedings in Informatics, pages 36:1–36:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.MFCS.2023.36.

6 L. Dagum and R. Menon. Openmp: An industry-standard api for shared-memory programming. *IEEE Comput. Sci. Eng.*, 5(1):46–55, January 1998. doi:10.1109/99.660313.

7 A. Darwiche and P. Marquis. A knowledge compilation map. *J. Artif. Int. Res.*, 17(1):229–264, sep 2002.

8 P. Flajolet and R. Sedgewick. *Analytic Combinatorics*. Cambridge University Press, New York, NY, USA, 1 edition, 2009.

9 C. Gröpl, H. J. Prömel, and A. Srivastav. Ordered binary decision diagrams and the shannon effect. *Discret. Appl. Math.*, 142(1-3):67–85, 2004. doi:10.1016/j.dam.2003.02.003.

10 R. Heradio, D. Fernandez-Amoros, J. A. Galindo, D. Benavides, and D. Batory. Uniform and scalable sampling of highly configurable systems. *Empirical Softw. Engg.*, 27(2), 2022. doi:10.1007/s10664-021-10102-5.

11 D. E. Knuth. *The Art of Computer Programming, Volume 4A, Combinatorial Algorithms*. Addison-Wesley Professional, 2011.

12 L. Kruger, S. Jha, E.-J. Goh, and D. Boneh. Secure Function Evaluation with Ordered Binary Decision Diagrams. In *CCS'06*, pages 410–420. ACM, 2006.

13 S.-I. Minato, N. Ishiura, and S. Yajima. Shared binary decision diagram with attributed edges for efficient boolean function manipulation. In R. C. Smith, editor, *Proceedings of the 27th ACM/IEEE Design Automation Conference. Orlando, Florida, USA, June 24-28, 1990*, pages 52–57. IEEE Computer Society Press, 1990. doi:10.1145/123186.123225.

14 J. Newton and D. Verna. A theoretical and numerical analysis of the worst-case size of reduced ordered binary decision diagrams. *ACM TCL*, 20(1):6:1–6:36, 2019.

15 The FLINT team. *FLINT: Fast Library for Number Theory*, 2025. Version 3.2.1, https://flintlib.org.

16 J. Vuillemin and F. Béal. On the BDD of a Random Boolean Function. In *ASIAN'04*, pages 483–493, 2004.

17 I. Wegener. The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions. In *GTCCS'94*, pages 252–263, 1994.

18 I. Wegener. *Branching Programs and Binary Decision Diagrams*. SIAM, 2000.
# A Appendix for Section 7

## A.1 Linear mapping $\varphi$

In order to illustrate Section 7 we provide polynomials $\varphi(X^m) = \sum_{i=1}^{2m} P_i^{(m)}(u)X^i$ thanks to (16) for $m \in \{1, \dots, 8\}$.

<table><thead><tr><th rowspan="2">$\varphi(X)$</th><th rowspan="2">$P_i^{(1)}(u)$</th><th colspan="2">$\varphi(X^2)$</th><th colspan="2">$\varphi(X^3)$</th><th colspan="2">$\varphi(X^4)$</th></tr><tr><th>$i$</th><th>$P_i^{(2)}(u)$</th><th>$i$</th><th>$P_i^{(3)}(u)$</th><th>$i$</th><th>$P_i^{(4)}(u)$</th></tr></thead><tbody><tr><td>1</td><td>$-u+1$</td><td>1</td><td>$u^2-u$</td><td>1</td><td>$-2u^3+3u^2-u$</td><td>1</td><td>$6u^4-12u^3+7u^2-u$</td></tr><tr><td>2</td><td>$u$</td><td>2</td><td>$-u+1$</td><td>2</td><td>$-u^3+3u^2-2u$</td><td>2</td><td>$5u^4-14u^3+12u^2-3u$</td></tr><tr><td></td><td></td><td>3</td><td>$-2u^2+2u$</td><td>3</td><td>$5u^3-6u^2+1$</td><td>3</td><td>$-16u^4+26u^3-8u^2-2u$</td></tr><tr><td></td><td></td><td>4</td><td>$u^2$</td><td>4</td><td>$-3u^2+3u$</td><td>4</td><td>$-6u^4+20u^3-17u^2+2u+1$</td></tr><tr><td></td><td></td><td></td><td></td><td>5</td><td>$-3u^3+3u^2$</td><td>5</td><td>$14u^4-18u^3+4u$</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td>$u^3$</td><td>6</td><td>$-6u^3+6u^2$</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td>7</td><td>$-4u^4+4u^3$</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td>8</td><td>$u^4$</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">$\varphi(X^5)$</th><th rowspan="2">$P_i^{(5)}(u)$</th><th colspan="2">$\varphi(X^6)$</th></tr><tr><th>$i$</th><th>$P_i^{(6)}(u)$</th></tr></thead><tbody><tr><td>1</td><td>$-24u^5+60u^4-50u^3+15u^2-u$</td><td>1</td><td>$120u^6-360u^5+390u^4-180u^3+31u^2-u$</td></tr><tr><td>2</td><td>$-26u^5+80u^4-85u^3+35u^2-4u$</td><td>2</td><td>$154u^6-534u^5+685u^4-390u^3+90u^2-5u$</td></tr><tr><td>3</td><td>$65u^5-135u^4+75u^3-5u$</td><td>3</td><td>$-323u^6+819u^5-650u^4+120u^3+43u^2-9u$</td></tr><tr><td>4</td><td>$45u^5-140u^4+140u^3-45u^2$</td><td>4</td><td>$-316u^6+1065u^5-1275u^4+620u^3-89u^2-5u$</td></tr><tr><td>5</td><td>$-66u^5+110u^4-25u^3-25u^2+5u+1$</td><td>5</td><td>$350u^6-720u^5+310u^4+160u^3-105u^2+5u$</td></tr><tr><td>6</td><td>$-20u^5+70u^4-65u^3+10u^2+5u$</td><td>6</td><td>$211u^6-696u^5+750u^4-260u^3-15u^2+9u+1$</td></tr><tr><td>7</td><td>$30u^5-40u^4+10u^2$</td><td>7</td><td>$-196u^6+330u^5-50u^4-120u^3+30u^2+6u$</td></tr><tr><td>8</td><td>$-10u^4+10u^3$</td><td>8</td><td>$-50u^6+180u^5-175u^4+30u^3+15u^2$</td></tr><tr><td>9</td><td>$-5u^5+5u^4$</td><td>9</td><td>$55u^6-75u^5+20u^3$</td></tr><tr><td>10</td><td>$u^5$</td><td>10</td><td>$-15u^5+15u^4$</td></tr><tr><td></td><td></td><td>11</td><td>$-6u^6+6u^5$</td></tr><tr><td></td><td></td><td>12</td><td>$u^6$</td></tr></tbody></table>

<table><caption>$\varphi(X^7)$</caption><thead><tr><th>$i$</th><th>$P_i^{(7)}(u)$</th></tr></thead><tbody><tr><td>1</td><td>$-720u^7+2520u^6-3360u^5+2100u^4-602u^3+63u^2-u$</td></tr><tr><td>2</td><td>$-1044u^7+4074u^6-6160u^5+4480u^4-1561u^3+217u^2-6u$</td></tr><tr><td>3</td><td>$1904u^7-5705u^6+5866u^5-2065u^4-175u^3+189u^2-14u$</td></tr><tr><td>4</td><td>$2373u^7-8897u^6+12579u^5-8120u^4+2205u^3-126u^2-14u$</td></tr><tr><td>5</td><td>$-2107u^7+5138u^6-3150u^5-1015u^4+1442u^3-308u^2$</td></tr><tr><td>6</td><td>$-1932u^7+6881u^6-8785u^5+4550u^4-574u^3-154u^2+14u$</td></tr><tr><td>7</td><td>$1315u^7-2639u^6+714u^5+1330u^4-770u^3+35u^2+14u+1$</td></tr><tr><td>8</td><td>$707u^7-2422u^6+2730u^5-980u^4-105u^3+63u^2+7u$</td></tr><tr><td>9</td><td>$-476u^7+805u^6-70u^5-385u^4+105u^3+21u^2$</td></tr><tr><td>10</td><td>$-105u^7+385u^6-385u^5+70u^4+35u^3$</td></tr><tr><td>11</td><td>$91u^7-126u^6+35u^4$</td></tr><tr><td>12</td><td>$-21u^6+21u^5$</td></tr><tr><td>13</td><td>$-7u^7+7u^6$</td></tr><tr><td>14</td><td>$u^7$</td></tr></tbody></table>
XX:30 Counting ROBDDs With Respect to Size

$\varphi(X^8)$

<table><thead><tr><th>i</th><th>P<sub>i</sub><sup>(8)</sup>(u)</th></tr></thead><tbody><tr><td>1</td><td>5040u<sup>8</sup> - 20160u<sup>7</sup> + 31920u<sup>6</sup> - 25200u<sup>5</sup> + 10206u<sup>4</sup> - 1932u<sup>3</sup> + 127u<sup>2</sup> - u</td></tr><tr><td>2</td><td>8028u<sup>8</sup> - 34992u<sup>7</sup> + 61124u<sup>6</sup> - 54180u<sup>5</sup> + 25305u<sup>4</sup> - 5782u<sup>3</sup> + 504u<sup>2</sup> - 7u</td></tr><tr><td>3</td><td>-13004u<sup>8</sup> + 44960u<sup>7</sup> - 56686u<sup>6</sup> + 29050u<sup>5</sup> - 2296u<sup>4</sup> - 2618u<sup>3</sup> + 614u<sup>2</sup> - 20u</td></tr><tr><td>4</td><td>-19559u<sup>8</sup> + 81676u<sup>7</sup> - 134008u<sup>6</sup> + 107786u<sup>5</sup> - 42546u<sup>4</sup> + 6720u<sup>3</sup> - 41u<sup>2</sup> - 28u</td></tr><tr><td>5</td><td>14280u<sup>8</sup> - 40012u<sup>7</sup> + 30968u<sup>6</sup> + 6944u<sup>5</sup> - 18886u<sup>4</sup> + 7462u<sup>3</sup> - 742u<sup>2</sup> - 14u</td></tr><tr><td>6</td><td>18004u<sup>8</sup> - 70952u<sup>7</sup> + 106078u<sup>6</sup> - 72380u<sup>5</sup> + 19670u<sup>4</sup> + 210u<sup>3</sup> - 644u<sup>2</sup> + 14u</td></tr><tr><td>7</td><td>-9380u<sup>8</sup> + 21364u<sup>7</sup> - 6888u<sup>6</sup> - 16100u<sup>5</sup> + 14196u<sup>4</sup> - 3108u<sup>3</sup> - 112u<sup>2</sup> + 28u</td></tr><tr><td>8</td><td>-8196u<sup>8</sup> + 30316u<sup>7</sup> - 40320u<sup>6</sup> + 21504u<sup>5</sup> - 2079u<sup>4</sup> - 1400u<sup>3</sup> + 154u<sup>2</sup> + 20u + 1</td></tr><tr><td>9</td><td>3940u<sup>8</sup> - 7672u<sup>7</sup> + 742u<sup>6</sup> + 6230u<sup>5</sup> - 3500u<sup>4</sup> + 140u<sup>3</sup> + 112u<sup>2</sup> + 8u</td></tr><tr><td>10</td><td>1918u<sup>8</sup> - 6748u<sup>7</sup> + 7840u<sup>6</sup> - 2870u<sup>5</sup> - 420u<sup>4</sup> + 252u<sup>3</sup> + 28u<sup>2</sup></td></tr><tr><td>11</td><td>-1008u<sup>8</sup> + 1708u<sup>7</sup> - 56u<sup>6</sup> - 980u<sup>5</sup> + 280u<sup>4</sup> + 56u<sup>3</sup></td></tr><tr><td>12</td><td>-196u<sup>8</sup> + 728u<sup>7</sup> - 742u<sup>6</sup> + 140u<sup>5</sup> + 70u<sup>4</sup></td></tr><tr><td>13</td><td>140u<sup>8</sup> - 196u<sup>7</sup> + 56u<sup>5</sup></td></tr><tr><td>14</td><td>-28u<sup>7</sup> + 28u<sup>6</sup></td></tr><tr><td>15</td><td>-8u<sup>8</sup> + 8u<sup>7</sup></td></tr><tr><td>16</td><td>u<sup>8</sup></td></tr></tbody></table>

A typical example of calculus by the recurrence relation (16), for instance computing $P_5^{(4)}(u)$, is

$$
\begin{aligned}
P_5^{(4)}(u) &= uP_3^{(3)}(u) + (1-u)P_4^{(3)}(u) + (1-u)u\frac{\partial}{\partial u}P_5^{(3)}(u) \\
&= u(u^3 - 6u^2 + 1) + (1-u)(-3u^2 + 3u) + (1-u)u(-3 \times 3u^2 + 3 \times 2u) \\
&= 14u^4 - 18u^3 + 4u.
\end{aligned}
$$

## A.2 First algorithm: top-down approach

Iterating $\varphi$ four times starting from $X$ gives the following bivariate polynomials. The distribution is obtained by setting $X = 2$ in the result. Monomials of degree larger than 9 in $u$ (the maximal size of the ROBDD) and 10 in $X$ (maximal number of outgoing half-edges for any layer) are discarded.

<table><tr><td>j</td><td>[X<sup>j</sup>]<sub>1</sub>(X)</td></tr><tr><td>1</td><td>-u + 1</td></tr><tr><td>2</td><td>u</td></tr></table>

<table><tr><td>j</td><td>[X<sup>j</sup>]<sub>2</sub>(X)</td></tr><tr><td>1</td><td>u<sup>3</sup> - 2u + 1</td></tr><tr><td>2</td><td>-2u<sup>2</sup> + 2u</td></tr><tr><td>3</td><td>-2u<sup>3</sup> + 2u<sup>2</sup></td></tr><tr><td>4</td><td>u<sup>3</sup></td></tr></table>

<table><thead><tr><th>j</th><th>[X<sup>j</sup>]<sub>3</sub>(X)</th></tr></thead><tbody><tr><td>1</td><td>6u<sup>7</sup> - 8u<sup>6</sup> - 3u<sup>5</sup> + 4u<sup>4</sup> + 3u<sup>3</sup> - 3u + 1</td></tr><tr><td>2</td><td>5u<sup>7</sup> - 12u<sup>6</sup> + 4u<sup>5</sup> + 8u<sup>4</sup> - 2u<sup>3</sup> - 6u<sup>2</sup> + 3u</td></tr><tr><td>3</td><td>-16u<sup>7</sup> + 16u<sup>6</sup> + 14u<sup>5</sup> - 10u<sup>4</sup> - 10u<sup>3</sup> + 6u<sup>2</sup></td></tr><tr><td>4</td><td>-6u<sup>7</sup> + 20u<sup>6</sup> - 11u<sup>5</sup> - 12u<sup>4</sup> + 9u<sup>3</sup></td></tr><tr><td>5</td><td>14u<sup>7</sup> - 12u<sup>6</sup> - 12u<sup>5</sup> + 10u<sup>4</sup></td></tr><tr><td>6</td><td>-8u<sup>6</sup> + 8u<sup>5</sup></td></tr><tr><td>7</td><td>-4u<sup>7</sup> + 4u<sup>6</sup></td></tr><tr><td>8</td><td>u<sup>7</sup></td></tr></tbody></table>
<table><thead><tr><th>j</th><th>[X<sup>j</sup>]<i>φ</i>(<i>φ</i>(<i>φ</i>(X)))</th></tr></thead><tbody><tr><td>1</td><td>1454u<sup>9</sup> - 208u<sup>8</sup> - 239u<sup>7</sup> - 52u<sup>6</sup> + 16u<sup>5</sup> + 16u<sup>4</sup> + 6u<sup>3</sup> - 4u + 1</td></tr><tr><td>2</td><td>1811u<sup>9</sup> - 1192u<sup>8</sup> - 436u<sup>7</sup> + 54u<sup>6</sup> + 88u<sup>5</sup> + 24u<sup>4</sup> - 8u<sup>3</sup> - 12u<sup>2</sup> + 4u</td></tr><tr><td>3</td><td>-4722u<sup>9</sup> - 1146u<sup>8</sup> + 580u<sup>7</sup> + 358u<sup>6</sup> + 26u<sup>5</sup> - 56u<sup>4</sup> - 28u<sup>3</sup> + 12u<sup>2</sup></td></tr><tr><td>4</td><td>-5436u<sup>9</sup> + 2048u<sup>8</sup> + 1149u<sup>7</sup> - 28u<sup>6</sup> - 190u<sup>5</sup> - 48u<sup>4</sup> + 30u<sup>3</sup></td></tr><tr><td>5</td><td>4818u<sup>9</sup> + 2656u<sup>8</sup> - 382u<sup>7</sup> - 488u<sup>6</sup> - 58u<sup>5</sup> + 64u<sup>4</sup></td></tr><tr><td>6</td><td>5496u<sup>9</sup> - 988u<sup>8</sup> - 970u<sup>7</sup> - 32u<sup>6</sup> + 118u<sup>5</sup></td></tr><tr><td>7</td><td>-1728u<sup>9</sup> - 1604u<sup>8</sup> + 40u<sup>7</sup> + 188u<sup>6</sup></td></tr><tr><td>8</td><td>-2169u<sup>9</sup> + 132u<sup>8</sup> + 258u<sup>7</sup></td></tr><tr><td>9</td><td>178u<sup>9</sup> + 302u<sup>8</sup></td></tr><tr><td>10</td><td>298u<sup>9</sup></td></tr></tbody></table>

A typical calculus that gives the second table:

$$ 
\begin{aligned}
\varphi(\varphi(X)) &= \varphi((-u+1)X + uX^2) \\
&= (-u+1)\varphi(X) + u\varphi(X^2) \\
&= (-u+1)(-u+1)X + uX^2 \\
&\quad + u((u^2-u)X + (-u+1)X^2 + (-2u^2+2u)X^3 + u^2X^4) \\
&= (u^3 - 2u + 1)X + (-2u^2 + 2u)X^2 + (-2u^3 + 2u^2)X^3 + u^3X^4
\end{aligned}
$$

As an illustration, terms in $u^9$ and $u^5$ (in bold) can be collected to compute the number of ROBDDs with 4 variables with respective size 9 and 5

$$ \text{size 9: } 2982^{10} + 1782^{9} - 21692^{8} - 17282^{7} + 54962^{6} + 48182^{5} - 54362^{4} - 47222^{3} + 18112^{2} + 14542^{1} = 11160 $$

$$ \text{size 5: } 1182^{6} - 582^{5} - 1902^{4} + 262^{3} + 882^{2} + 162^{1} = 3248. $$

### A.3 Second algorithm: bottom-up approach

The pseudocode for the bottom-up approach is given in Algorithm 5 on Page 32.
<figure><img src="image_16.png" /><figcaption>**Algorithm 5 Computing eval₂ ($\varphi^k(X)$)**</figcaption></figure>

**Input:** integer $k$: number of variables
**Output:** $F_k(u) = \text{eval}_2(\varphi^\ell(X)) \in \mathbb{Z}[u]$ the generating functions for ROBDDs
$\theta \leftarrow \lfloor \log_2 (k - \lfloor \log_2 (k) \rfloor) \rfloor$
$N \leftarrow 2^{k-\theta} - 1 + 2^{2^\theta}$ ▷ $N$ is maximal total number of nodes for $k$ variables
$T \leftarrow N$ ▷ $T$ stores the max. number of nodes on layers $< k - \ell$ (top)
$V = (V_0(u), \dots, V_{N+1}(u))$ stores the sequence $(\varphi^\ell(X^i))_{0 \le i \le N+1}$ evaluated at
$X=2$
$V \leftarrow (1, 2, \dots, 2^{N+1})$ ▷ Initial sequence $(X^i)_{0 \le i \le N+1}$ evaluated at $X=2$
$W \leftarrow (0, 0, \dots, 0)$ ▷ $W$ auxiliary array of size $N+2$ needed for updating $V$
**for $\ell$ from 1 to $k$ do**
| $p_{\max} \leftarrow \begin{cases} 2^{k-\ell} & \text{if } k-\ell < \theta \\ 2^{2^\ell} - 2^{2^{\ell-1}} & \text{otherwise} \end{cases}$ ▷ Maximal number of nodes at current layer
| $k-\ell$
| $T \leftarrow T - p_{\max}$
| $S(u, X) \leftarrow 1$ ▷ $S = \varphi(X^0)$ is a bivariate polynomial in $\mathbb{Z}[u, X]$
**for $m$ from 1 to $T+1$ do**
| $S(u, X) \leftarrow u(X^2 - X - \frac{\partial}{\partial u})S(u, X)$ (*) ▷ $S(u, X) = \varphi(X^m)$ computed in $O(m^2)$ time and space using (15) and
| (16)
| $Q(u) \leftarrow 0$
**for $j$ from 0 to $m+\min(m, p_{\max})$ do**
| $P(u) \leftarrow [X^j]S(u, X)$
| $Q(u) \leftarrow Q(u) + V_j(u) \times P(u)$
| $W_m(u) \leftarrow Q(u)$
**swap**($V, W$) ▷ Update of $V$
**return** $V_1(u)$ ▷ this is $(\varphi^k(X))$ evaluated at $X=2$

Now, when considering 4 variables, the maximal size is 9 and corresponding profile is $p = (1, 2, 4, 2)$. The algorithm computes in a bottom-up manner eval₂($\varphi^\ell(X^m)$) for $\ell = 0, \dots, 4$. This gives the following tables.

<table><thead><tr><th>m</th><th>eval<sub>2</sub> (φ<sup>0</sup>(X<sup>m</sup>)) = eval<sub>2</sub> (X<sup>m</sup>)</th></tr></thead><tbody><tr><td>0</td><td>1</td></tr><tr><td>1</td><td>2</td></tr><tr><td>2</td><td>4</td></tr><tr><td>3</td><td>8</td></tr><tr><td>4</td><td>16</td></tr><tr><td>5</td><td>32</td></tr><tr><td>6</td><td>64</td></tr><tr><td>7</td><td>128</td></tr><tr><td>8</td><td>256</td></tr><tr><td>9</td><td>512</td></tr><tr><td>10</td><td>1024</td></tr></tbody></table>

<table><thead><tr><th>m</th><th>eval<sub>2</sub> (φ<sup>1</sup>(X<sup>m</sup>)) = eval<sub>2</sub> (φ(X<sup>m</sup>))</th></tr></thead><tbody><tr><td>0</td><td>1</td></tr><tr><td>1</td><td>2u + 2</td></tr><tr><td>2</td><td>2u<sup>2</sup> + 10u + 4</td></tr><tr><td>3</td><td>18u<sup>2</sup> + 38u + 8</td></tr><tr><td>4</td><td>110u<sup>2</sup> + 130u + 16</td></tr><tr><td>5</td><td>570u<sup>2</sup> + 422u + 32</td></tr><tr><td>6</td><td>2702u<sup>2</sup> + 1330u + 64</td></tr><tr><td>7</td><td>12138u<sup>2</sup> + 4118u + 128</td></tr><tr><td>8</td><td>52670u<sup>2</sup> + 12610u + 256</td></tr></tbody></table>

<table><thead><tr><th>m</th><th>eval<sub>2</sub> (φ<sup>2</sup>(X<sup>m</sup>)) = eval<sub>2</sub> (φ(φ(X<sup>m</sup>)))</th></tr></thead><tbody><tr><td>0</td><td>1</td></tr><tr><td>1</td><td>2u<sup>3</sup> + 8u<sup>2</sup> + 4u + 2</td></tr><tr><td>2</td><td>74u<sup>4</sup> + 90u<sup>3</sup> + 68u<sup>2</sup> + 20u + 4</td></tr><tr><td>3</td><td>1080u<sup>5</sup> + 1518u<sup>4</sup> + 1010u<sup>3</sup> + 404u<sup>2</sup> + 76u + 8</td></tr><tr><td>4</td><td>11160u<sup>6</sup> + 25440u<sup>5</sup> + 18542u<sup>4</sup> + 8058u<sup>3</sup> + 2060u<sup>2</sup> + 260u + 16</td></tr></tbody></table>
<table><thead><tr><th>m</th><th>eval<sub>2</sub>(φ<sup>3</sup>(X<sup>m</sup>)) = eval<sub>2</sub>(φ(φ(φ(X<sup>m</sup))))</th></tr></thead><tbody><tr><td>0</td><td>1</td></tr><tr><td>1</td><td>74u<sup>5</sup> + 88u<sup>4</sup> + 62u<sup>3</sup> + 24u<sup>2</sup> + 6u + 2</td></tr><tr><td>2</td><td>11160u<sup>8</sup> + 23280u<sup>7</sup> + 17666u<sup>6</sup> + 9002u<sup>5</sup> + 3262u<sup>4</sup> + 934u<sup>3</sup> + 198u<sup>2</sup> + 30u + 4 (‡)</td></tr></tbody></table>

<table><thead><tr><th>m</th><th>eval<sub>2</sub>(φ<sup>4</sup>(X<sup>m</sup>)) = eval<sub>2</sub>(φ(φ(φ(X<sup>m</sup)))))</th></tr></thead><tbody><tr><td>0</td><td>1</td></tr><tr><td>1</td><td>11160u<sup>9</sup> + 23280u<sup>8</sup> + 17666u<sup>7</sup> + 8928u<sup>6</sup> + 3248u<sup>5</sup> + 960u<sup>4</sup> + 236u<sup>3</sup> + 48u<sup>2</sup> + 8u + 2</td></tr></tbody></table>

In the last table, the distribution generating function eval₂(φ⁴(X)) for ROBDDS with 4 variables is represented in bold.

As a typical example of computation corresponding with line marked by (‡), if we wish to compute eval₂(φ³(X²)), we first read φ(X²) from Appendix A.1, i.e.,

$$ \varphi(X^2) = (u^2 - u)X + (-u + 1)X^2 + (-2u^2 + 2u)X^3 + u^2 X^4. $$

Then we compute eval₂(φ²(φ(X²))) by linearity. This yields

$$ \begin{aligned} \text{eval}_2(\varphi^3(X^2)) &= (u^2 - u) \text{eval}_2(\varphi^2(X)) + (-u + 1) \text{eval}_2(\varphi^2(X^2)) + (-2u^2 + 2u) \text{eval}_2(\varphi^2(X^3)) + u^2 \text{eval}_2(\varphi^2(X^4)) \\ &= (u^2 - u)(2u^3 + 8u^2 + 4u + 2) \\ &\quad + (-u + 1)(74u^4 + 90u^3 + 68u^2 + 20u + 4) \\ &\quad + (-2u^2 + 2u)(1080u^5 + 1518u^4 + 1010u^3 + 404u^2 + 76u + 8) \\ &= 11160u^8 + 23280u^7 + 17666u^6 + 9002u^5 + 3262u^4 + 934u^3 + 198u^2 + 30u + 4. \end{aligned} $$