Topological sequences and their enumeration

Let $P$ be a set with a partial ordering (given by a relation denoted by $\prec$) and a well-ordering (given by a relation denoted by $<$). Further, the partial ordering is embedded in the well-ordering i..e, $x\prec y$ implies $x<y$.

A sequence $\mathbf{X}= (x_1,x_2,\ldots,x_m)$ containing elements of $P$ is called a topological sequence if [1]

  1. For $1\leq j \leq m$ and $x \in P$, $x \prec x_j$ implies $x = x_i$ for some $i < j$;
  2. If $m > 0$, there exists $x \in P$ such that $x < x_m$ and $x \neq x_i$, for $1 < i \leq m$.

Let us call a $i$-th position in a topological sequence, $\mathbf{X}$, interesting (term due to Srivatsan) if $x_i> x_{i+1}$. By definition, the last position of a sequence is considered interesting. The index of a topological sequence is defined to be the sum of all $i$ for all interesting positions i.e.,

(1)
\begin{align} \textrm{index}(\mathbf{X}) =\sum_j \left\{j ~|~ j \textrm{ is interesting}\right\}\ . \end{align}

Definition: Let us call a sequence that satisfies condition 1 (but not necessarily condition 2) as an almost topological sequence.[2] The reason for creating this definition is because such sequences do occur as sub-sequences of topological sequences.

An example due to Knuth

Let $P$ denote the set of three-dimensional lattice points i.e.,

(2)
\begin{align} P=\Big\{(i,j,k)~|~ i,j,k=1,2,3,\ldots \Big\} \end{align}

with the partial ordering $(i,j,k)\preceq (i',j',k')$ if $i\leq i'$, and $j\leq j'$ and $k\leq k'$. Let us choose the well-ordering to be given by the lexicographic ordering i.e.,

(3)
\begin{equation} (i,j,k)< (i',j',k') \end{equation}

if and only if

(4)
\begin{align} i< i' \quad \textrm{ or } (i=i' \textrm{ and } j<j') \quad \textrm { or } (i=i',\ j=j' \textrm{ and } k<k')\ . \end{align}

Consider the topological sequence

(5)
\begin{align} \mathbf{X}=\{(1,1,1), (1,1,2), (1,1,3), \mathbf{(2,1,1)}, (1,2,1), \mathbf{(1,3,1)} \} \end{align}

where we have indicated the interesting positions in boldface. This sequence has index $10=4+6$.

Topological sequences and solid partitions.

Let $d(N)$ denote the number of topological sequences with index $N$ and $c(N)$ denote the number of solid partitions of $N$. A theorem of Knuth relates these two sets of numbers as follows:

(6)
\begin{align} p_3(N)\equiv c(N) = \sum_{k=0}^N d(k)\ p_1(N-k)\ , \end{align}

where $p_1(N)$ are the number of one-dimensional partitions of $N$. Equivalently, the generating function of solid partitions decomposes into a product of the generating function of the numbers of topological sequences and the generating function of one-dimensional partitions. Since topological sequences are much easier to enumerate, Knuth went ahead and wrote a program to generate all topological sequences of index $\leq N$ (for some fixed $N$). This is the program that was the starting point of the project.

We list below the topological sequences at depths 2 and 3.

(7)
\begin{align} \textbf{Depth 2:}\ \big\{(111) (121)\big \} \quad \textrm{and}\quad \big\{(111) (211)\big \} \quad \implies \boxed{d(2)=2}\ . \qquad\qquad \end{align}
(8)
\begin{align} \textbf{Depth 3:}\ \big\{(111) (112) (121)\big \}\ ; \big\{(111) (112) (211)\big \}\ ; \big\{(111) (121) (131)\big \}\ ; \big\{(111) (121) (211)\big \} \ ;\big\{(111) (211) (311)\big \} \quad \implies \boxed{d(3)=5}\ . \end{align}

Equivalence classes of almost topological sequences

We say that two sequences $\mathbf{X}= (x_1,x_2,\ldots,x_m) \sim \mathbf{Y}= (y_1,y_2,\ldots,y_m)$ are related if the elements of $\mathbf{Y}$ are a permutation of the elements of $\mathbf{X}$. Of course, not all permutations of an almost topological sequence lead to another almost topological sequence as some of them violate condition 1. in the definition of a topological sequence. However, even after imposing the restriction to permutations that lead to other topological sequences, the relation remains an equivalence relation. As an example consider the following three sequences:

(9)
\begin{align} \big\{(1,1,1) (1,1,2) (1,1,3) (1,2,1)\big\}\quad,\quad \big\{(1,1,1) (1,1,2) (1,2,1) (1,1,3)\big\}\quad,\quad \big\{(1,1,1) (1,2,1) (1,1,2) (1,1,3)\big\}\quad. \end{align}

It is easy to see that these three sequences form a single equivalence class. However, the last two are not topological sequences as they violate condition 2 and hence are almost topological sequences. We thus choose to work with equivalence classes of almost topological sequences.

Nodes and equivalence classes at depth 4

Below we have shown representatives of equivalence classes in boldface. In a given equivalence class, the topological sequence with lowest index is chosen as the representative of the class. This is important for the parallelization. At depth 4 there are 33 nodes in 13 equivalence classes. The number given at the end of each sequence is its index. The number of topological sequences at depth 4 is 12 — these happen to be the ones in boldface excluding the very first entry. All equivalence classes barring the first one below have representatives that are topological sequences. At any depth, we will see that all equivalences classes barring one will have representatives that are topological sequences. The solitary equivalence class that misses out is the one with all entries of the form $(1,1,z)$.

(1,1,1) (1,1,2) (1,1,3) (1,1,4) 4 (this is not a topological sequence as it violates condition 2 in the definition.)
(1,1,1) (1,1,2) (1,1,3) (1,2,1) 4
(1,1,1) (1,1,2) (1,1,3) (2,1,1) 4
(1,1,1) (1,1,2) (1,2,1) (1,1,3) 7 (this is not a topological sequence as it violates condition 2 in the definition.)
(1,1,1) (1,1,2) (1,2,1) (1,2,2) 4
(1,1,1) (1,1,2) (1,2,1) (1,3,1) 4
(1,1,1) (1,1,2) (1,2,1) (2,1,1) 4
(1,1,1) (1,1,2) (2,1,1) (1,1,3) 7 (this is not a topological sequence as it violates condition 2 in the definition.)
(1,1,1) (1,1,2) (2,1,1) (1,2,1) 7
(1,1,1) (1,1,2) (2,1,1) (2,1,2) 4
(1,1,1) (1,1,2) (2,1,1) (3,1,1) 4

(1,1,1) (1,2,1) (1,1,2) (1,1,3) 6 (this is not a topological sequence as it violates condition 2 in the definition.)
(1,1,1) (1,2,1) (1,1,2) (1,2,2) 6
(1,1,1) (1,2,1) (1,1,2) (1,3,1) 6
(1,1,1) (1,2,1) (1,1,2) (2,1,1) 6
(1,1,1) (1,2,1) (1,3,1) (1,1,2) 7 (this is not a topological sequence as it violates condition 2 in the definition.)
(1,1,1) (1,2,1) (1,3,1) (1,4,1) 4
(1,1,1) (1,2,1) (1,3,1) (2,1,1) 4
(1,1,1) (1,2,1) (2,1,1) (1,1,2) 7(this is not a topological sequence as it violates condition 2 in the definition.)
(1,1,1) (1,2,1) (2,1,1) (1,3,1) 7
(1,1,1) (1,2,1) (2,1,1) (2,2,1) 4
(1,1,1) (1,2,1) (2,1,1) (3,1,1) 4

(1,1,1) (2,1,1) (1,1,2) (1,1,3) 6(this is not a topological sequence as it violates condition 2 in the definition.)
(1,1,1) (2,1,1) (1,1,2) (1,2,1) 6
(1,1,1) (2,1,1) (1,1,2) (2,1,2) 6
(1,1,1) (2,1,1) (1,1,2) (3,1,1) 6
(1,1,1) (2,1,1) (1,2,1) (1,1,2) 9(this is not a topological sequence as it violates condition 2 in the definition.)
(1,1,1) (2,1,1) (1,2,1) (1,3,1) 6
(1,1,1) (2,1,1) (1,2,1) (2,2,1) 6
(1,1,1) (2,1,1) (1,2,1) (3,1,1) 6
(1,1,1) (2,1,1) (3,1,1) (1,1,2) 7(this is not a topological sequence as it violates condition 2 in the definition.)
(1,1,1) (2,1,1) (3,1,1) (1,2,1) 7
(1,1,1) (2,1,1) (3,1,1) (4,1,1) 4

Nodes vs Equivalence classes at various depths

Depth 5 6 7 8 9 10 11 12 13 14
Nodes 135 633 3207 17,589 102,627 636,033 4,161,141 28,680,717 207,318,273 1,567,344,549
Eq. classes 24 48 86 160 282 500 859 1479 2485 4167

Note: The number of equivalence classes at depth k is equal to the number of plane partitions of k. The first few numbers of plane partitions are:

$1, 1, 3, 6, 13, 24, 48, 86, 160, 282, 500, 859, 1479, 2485, 4167, 6879, 11297, 18334, 29601, 47330, 75278\ldots$

Remark: (March 2, 2012) Ekhad and Zeilberger[3] enumerate Solid Standard Young Tableaux with k boxes which were shown to be the same as the number of almost topological sequences at depth k in [2].

Bibliography
1. D. E. Knuth, “A note on solid partitions,” Math. Comp. 24 (1970) 955–961.
2. S. Balakrishnan, S. Govindarajan and N. S. Prabhakar, On the asymptotics of higher-dimensional partitions J.Phys.A A45 (2012) 055001 arXiv:1105.6231.
3. Shalosh B. Ekhad and D. Zeilberger, Computational and Theoretical Challenges on Counting Solid Standard Young Tableaux, arXiv:1202.6229.

Note: This was a private wiki page until it was made public on March 2, 2012 with some cosmetic changes.


Page maintained by Suresh Govindarajan

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License