# A Noncommutative Enumeration Problem

Authors: Maria Simonetta Bernabei; Horst Thaler
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

We tackle the combinatorics of coloured hard-dimer objects. This is achieved by identifying coloured hard-dimer configurations with a certain class of rooted trees that allow for an algebraic treatment in terms of noncommutative formal power series. A representation
in terms of matrices then allows to find the asymptotic behaviour of these objects.


---

## Body

## 1. Introduction

The aim is to count coloured hard-dimer configurations which are objects as shown in Figure1.Figure 1
A coloured hard-dimer configuration(n=12) with 2 blue dimers, 1 red dimer, and 3 inner vertices.More precisely, we define a coloured hard-dimer configuration (CHDC) to be a finite sequenceσn, of n blue and red vertices, together with coloured dimers on σn which must not intersect. Here a coloured dimer is an edge connecting two nearest vertices of the same colour see Figure 1. The dimer’s colour is given by the colour of its boundary vertices. In graph-theoretic language CHDCs are a subclass of labeled graphs whose vertices and edges carry one of two possible labels. Without loss of generality, we may assume that a CHDC is a subset of ℝ and its vertices belong to ℤ. We include also the empty CHDC, that is, the configuration when no dimers are present.The enumeration problem we have in mind goes as follows:given a sequenceσnand a triple of nonnegative integers(i,j,k),wherei,jcount the numbers of blue, red dimers andkthe number of inner vertices, that is, vertices that are connected to their left and right vertex. How many CHDCs of a given type(i,j,k)are there onσn, whereσnas well asnmay be arbitrary?The strategy is to identify the set of CHDCs with a certain class of trees the elements of which can be encoded into monomials of a noncommutative formal power series∑xaxx, where the x’s are words over the alphabet {b,r}. This means that the indeterminates b and r are supposed to be noncommutative and a particular word x just corresponds to a particular sequence of blue and red vertices σn. The coefficients ax collect the information of CHDCs of a given type on σn.The motivation for studying this kind of objects is due to their appearance in causally triangulated(2+1)-dimensional gravity. It was shown in [1], by using special triangulations of spacetime, that the discrete Laplace transform of the one-step propagator can be expressed as follows:(1.1)Z(u,v,w)=∑n∈Ne-γnZn(u,v,w),
with(1.2)Zn(u,v,w)=∑σn1Zσnhcd(-u,-v,w),Zσnhcd(u,v,w)=∑CHDCsD|σnu|D|bv|D|rw|∩D|.
The parameters γ,u,v,w are related to physical and geometrical constants. Now, the exponents |D|b,|D|r,|∩D| just count, for a given CHDC D, the number of blue dimers, red dimers, and inner vertices, respectively. A glance at Zσnhcd shows that it involves precisely the combinatorial numbers we are after in this paper.In Section2, we show how to make CHDCs into monomials, and thereby solve the enumeration problem from above. In Section 3, we give an alternative way to express the coefficients ax by means of a linear representation of the indeterminates b,r. The formal power series that allow such a representation are called recognizable. Finally, we use this result to investigate the growth behaviour of the number of CHDCs.


## 2. From CHDCs to Noncommutative Series

In this section we will establish a bijection between CHDCs and a certain class of trees. This is achieved by first identifying CHDCs with a particular class of graphs denotedGhcd which in turn will be identified with the corresponding class of trees denoted Thcd.BijectionCHDCs⇔Ghcd: for a given CHDC, we endow its vertices with the order inherited from ℤ. An extra vertex × is added in the first place, which becomes the root of the graph. Then, all the vertices which are next neighbors are connected through an edge. Finally, the vertices which in the original CHDC are the starting and end points of a dimer are linked via an extra edge to the right, as seen from the root (see Figure 2(a)). We note that only the closest vertices of the same colour may get an extra link and that these become trivalent, unless we consider the last vertex, in which case it becomes bivalent. The set of rooted graphs we obtain in this manner is denoted as Ghcd, and it is obvious that we have established a bijection between the latter and the set of CHDCs.Figure 2
Illustration of the one-to-one correspondence between a coloured hard-dimer, its graph, and its tree.BijectionGhcd⇔Thcd: when a graph in Ghcd is given, we move beginning from the root in clockwise direction and cut an edge if the graph remains connected. The cut edge is replaced by two edges ending in univalent vertices called buds (black arrow) and leafs (white arrow), respectively. The procedure is repeated until we reach the last vertex (see Figure 2(b)). We note that buds and three vertices are always connected by one edge only, whereas leafs and three vertices may be interlaced by a certain number of bivalent red or blue vertices. The set of rooted trees we obtain following this procedure is denoted as Thcd. Vice versa, when a tree in Thcd is given, we may, starting from the root, move in clockwise direction and merge the bud leave pairs to edges getting a graph in Ghcd.We have thus established a bijection between the set of CHDCs and the setThcd. The next goal is to find an algebraic formulation of the enumeration problem for elements in Thcd. For this, we adapt ideas from [2] and assign the charges +1, −1 and 0 to leaves, buds and univalent coloured vertices, respectively. With this choice any tree has charge 0 and any subtree different from a bud has charge 0 or +1. For this reason, we distinguish between S (resp., R) trees, if and only if(a)
their total charge is 0 (resp., 1),(b)
any descendant subtree different from a bud has charge 0 or 1.Furthermore, we subdivide these two groups intoSb, Rb and Sr, Rr trees depending on whether the first vertex after the root is blue or red.Now, we are able to write down a system of equations for the four types of trees which will turn out to be linear. Since we are interested in counting the number of CHDCs on a fixed sequence of blue and red vertices we assign noncommutative variablesb and r to blue and red vertices, respectively. Furthermore, for a given sequence σn we group together all CHDCs with the same numbers i, j, and k. This can be achieved by encoding a blue or red dimer through the assignment of commutative variables b3 and r3, respectively. Particularly, the variables b3 and r3 are assigned to those trivalent blue and red vertices, respectively, which possess a bud leg pair as subtree. Finally, to every bivalent vertex sitting in between a three vertex and a leaf, we assign a commutative variable y.We are thus naturally led to consider the treesSb, Sr, Rb, and Rr as elements of the noncommutative algebra K〈〈b,r〉〉 of formal power series, where K is the commutative polynomial ring K=ℤ[b3,r3,y]. A formal series will be written in the form P=∑xaxx, where the sum runs over all words of the alphabet {b,r} with coefficients ax≡(P,x). For example, the tree and the corresponding graph in Figure 2 read(2.1)b32r3y3r*b*r*r*b*r*b*b*r*b*r*b,
where * stands for the noncommutative product in K〈〈b,r〉〉. As we can read in Figure 3 below, our trees have to satisfy the following consistency equations:(2.2)Sb=b+b*(Sb+Sr)+b3b*Rb,Sr=r+r*(Sb+Sr)+r3r*Rr,Rb=b+b*(Sb+Sr)+yr*(1-yr)-1*b*(Sb+Sr)+yr*(1-yr)-1*b,Rr=r+r*(Sb+Sr)+yb*(1-yb)-1*r*(Sb+Sr)+yb*(1-yb)-1*r.
Substituting the expressions of Rb and Rr into the equations for Sb and Sr, we get by elementary algebra the following system of equations:(2.3)Sb=[b+b3b*(1-yr)-1*b]︸=:Ab*Sb+Ab*Sr+Ab,Sr=[r+r3r*(1-yb)-1*r]︸=:Ar*Sr+Ar*Sb+Ar,
that is,(2.4)(1-Ab)*Sb-Ab*Sr=Ab,-Ar*Sb+(1-Ar)*Sr=Ar.
The system (2.4) can be solved easily with the result(2.5)Sb=[1-Ab*(1-Ar)-1]-1*Ab*(1-Ar)-1=(1-Ar)*(1-Ar-Ab)-1-1.
By symmetry, we also get(2.6)Sr=(1-Ab)*(1-Ar-Ab)-1-1.Figure 3
The possible building blocks from the perspective of an arbitrary vertex. The corresponding building blocks forRr are obtained by exchanging colors and variables (b↔r).Theorem 2.1.
LetSb=∑xaxx be the formal series given as part of the unique solution of (2.4) in K〈〈b,r〉〉. Then, all coefficients of words x starting with letter r are zero and the nontrivial coefficients ax are given as finite sums
(2.7)ax=∑i,j,k∈N0mi,j,k(x)b3ir3jyk,
where the multiplicities mi,j,k(x) count the number of coloured hard-dimer configurations D on x with fixed (i,j,k). In particular, the evaluation ax(b3=1,r3=1,w=1) gives the number of CHDCs on the sequence σn corresponding to x. The symmetric assertion holds for Sr.Remark 2.2.
It is clear from (2.4) that S=Sb+Sr solves the equation (1-(Ab+Ar))*S=Ab+Ar with solution given by S=(1-(Ab+Ar))-1*(Ab+Ar). Moreover, for S=∑xcxx, the evaluation cx(b3=1,r3=1,w=1) gives the number of CHDCs on σn≡x irrespective of whether it starts with b or r.Proof of Theorem2.1.
Let# be one of the subscripts b, r and decompose S#=∑n=0∞S#n, where S#n comprises the sum of terms in S# with length |x|=n. In the same manner, we write R#=∑n=0∞R#n. An elementary computation shows that S#=#+{higherorderterms} and likewise for R#, which implies that a solution to (2.4) gives rise to sequences (S#n)n≥-1 and (R#n)n≥-1 obeying the following recursive equations (n≥1):
(2.8)Sbn=b+b*(Sbn-1+Srn-1)+b3b*Rbn-1,Srn=r+r*(Sbn-1+Srn-1)+r3r*Rrn-1,Rbn=b+b*(Sbn-1+Srn-1)+∑k=1n-2ykrk*b*(Sbn-1-k+Srn-1-k)+yn-1rn-1*b,Rrn=r+r*(Sbn-1+Srn-1)+∑k=1n-2ykbk*r*(Sbn-1-k+Srn-1-k)+yn-1bn-1*r,
with initial conditions S#c=0, R#c=0 for c∈{-1,0} and S#1=R#1=#. Vice versa, for sequences (S#n)n≥-1, (R#n)n≥-1 obeying (2.8) and related initial conditions, their sums S#∶=∑n=-1∞S#n and R#∶=∑n=-1∞R#n will satisfy (2.4). Therefore, we may equivalently look at the system (2.8). But the elements S#n contain precisely the sum of those terms from K〈〈b,r〉〉 which are algebraic counterparts of trees in Thcd that have n coloured vertices the first one of which is #. This is due to the fact that there is a one-to-one correspondence between trees from Thcd and trees of charge 0 that are constructed recursively according to the building blocks from Figure 3. For a fixed x, the coefficient ax is a sum of elements in K which stem from trees that are constructible for the particular sequence of blue and red vertices given by x. Since the indeterminates b3, r3, y are commutative, trees will contribute the same term b3ir3jyk, whenever the numbers of vertices corresponding to a b3, r3, y indeterminate, coincide. Therefore, the integer in front of b3ir3jyk gives the number of CHDCs with i blue dimers, j red dimers, and k inner vertices fixed.


## 3. The SolutionS as a Recognizable Series

Here, we show in addition thatS=Sb+Sr is a recognizable series. Let A be a finite alphabet, A* the corresponding free monoid of words, and R a semiring. A formal series P=∑x∈A*axx with ax∈R is called recognizable if there is some n≥1, a homomorphism of semirings (or simply a representation)(3.1)μ:A*⟶Rn×n,
where Rn×n carries its multiplicative structure and tuples λ,γ∈Rn such that for all words x(3.2)ax=λ⊤⋅μ(x)⋅γ.
Further material on recognizable series is exposed in [3, 4].In order to find a representation forS, we look at the prefixes of a given x and note that for a given prefix w of x, we may decompose the set of CHDCs on x into three disjoint subsets by looking at the restriction of a CHDC to w.X1w:
the boundary points of dimers (if any) either lie entirely inside or outside ofw,X2w:
a blue dimer starts inw and ends outside of w,X3w:
a red dimer starts inw and ends outside of w.Strictly speaking, we consider, in the above decomposition, the larger set of uncompleted CHDCs, meaning that the last vertex of a CHDC may be the starting or inner point of an uncompleted dimer; see Figure4.Figure 4
Two examples of uncompleted CHDCs.Now, the three sets are identified with the canonical basis elements of theK-module K3; that is, Xjw=(δij)1≤i≤3, j∈{1,2,3}. If the last vertex of w is blue or red, we assign matrices (B)ij or (R)ij to the latter. For this, let wl be the last letter of w. Then, the matrix entries are nonzero according to whether Xiw∖wl⊂Xjw, wl∈{b,r}, holds or does not hold. In accordance with the assignments of variables made in Section 2, we now choose entries #3 when a dimer of colour # is being completed and y when a dimer gets an additional inner vertex. The entries 1 indicate either that a single vertex is added or that a vertex becomes the starting point of a dimer. Explicitly, the matrices read(3.3)B=(110b30000y),R=(1010y0r300).
We choose λ=(1,0,0) which means that we start from the empty CHDC. In the end, the (complete) CHDCs can be read off by setting γ=(1,0,0). We may summarize this discussion in the following.Proposition 3.1.
The noncommutative formal seriesS is a recognizable series with representation
(3.4)μ:{b,r}*⟶K3×3,
given by μ(b)=B, μ(r)=R and tuples λ, γ.The result above allows to study the asymptotic behaviour of the number of CHDCs onσn when n tends to infinity. According to Proposition 3.1,  S is a recognizable series, and the evaluation at b3=r3=y=1 again gives a recognizable series. Namely, for(3.5)M=S(b3=1,r3=1,y=1),
the corresponding representation is given by μ′:{b,r}*→ℤ3×3 through(3.6)μ′(b)=B(b3=1,y=1),μ′(r)=R(r3=1,y=1),
and the tuples are(3.7)λ′=λ,γ′=γ.
Note that according to Remark 2.2,  cx=(M,x) counts the number of CHDCs on the sequence of blue and red sites corresponding to x.It is convenient to discuss the asymptotics of CHDCs within the framework of ergodic dynamical systems. To be precise, letB′∶=μ′(b), R′∶=μ′(r) and define ν as the probability measure on {B′,R′} given by ν(B′)=ν(R′)=1/2. Then, as ergodic dynamical system (Ω,ℱ,ℙ,θ), we choose the following.(i)
Ω={B′,R′}ℕ, that is, the set of sequences ω=(ω1,ω2,…) with ωi∈{B′,R′}.Ifgn(ω)=ωn denotes the coordinate maps then ℱ should be the σ-algebra generated by the gn’s.(ii)
ℙ is the product measure ℙ=∏n=1∞ν.(iii)
θ is the shift operator θ(ω)=(ω2,ω3,…).Upon turning{b,r}ℕ into a probability space that is isomorphic to (Ω,ℱ,ℙ), we may state the following theorem.Theorem 3.2.
Forω∈{b,r}ℕ, let ωn∶=(ω1,…,ωn), and let Dn(ω) denote the number of CHDCs on ωn. There exists a finite constant random variable α on ({b,r}ℕ,ℱ,ℙ) such that for almost all ω∈{b,r}ℕ(3.8)1nln⁡Dn(ω)⟶α,asn⟶∞.
This means that the number of CHDCs grows exponentially and that asymptotically this growth rate is the same for almost all ω.Proof.
If we define the matrix-valued random variables by(3.9)Xn(ω)=g1(ω)g2(ω)⋯gn(ω),
then
(3.10)Yn=-ln⁡(λ′⊤⋅Xn⋅γ′)
defines a subadditive sequence of random variables; that is,
(3.11)Ym+n≤Ym∘θn+Yn,∀m,n.
To see subadditivity, we first note that with the natural identifications
(3.12)ωn⟷v:(ω1,…,ωn)=ω1*⋯*ωn=v∈{b,r}*,
we may write λ′⊤·Xn(ω)·γ′=(M,v). Writing x=xn*xm, with |xn|=n and |xm|=m, subadditivity follows from the combinatorial fact that (M,x)≥(M,xn)(M,xm). Now, Kingman’s subadditive ergodic theorem, see [5] and [6, Theorem  IV.1.2], applied to our ergodic dynamical system (Ω,ℱ,ℙ,θ) implies that there exists a random variable β such that
(3.13)lim⁡n→∞(Ynn)=β=E[β],P-a.s.
In addition, one has β=infn(n-1𝔼[Yn]). If β>-∞ convergence holds also in L1(ℙ). A priori, it is not clear whether β>-∞ which we clarify now. By Jensen’s inequality, we find
(3.14)E[n-1Yn]≥-n-1ln⁡(λ′⊤⋅E[Xn]⋅γ′)=-n-1ln⁡(λ′⊤⋅Zn⋅γ′),
where Z=(B′+R′)/2. The eigenvalues of the matrix Z are (3/2,1/2,0), and the diagonalization of Z shows that limn→∞-n-1ln(λ′⊤·Zn·γ′)=-ln(3/2). This in turn implies 𝔼[n-1Yn]≥const., for all n, for some n-independent finite constant, and consequently β=infn(𝔼[n-1Yn])≥const. We have thus established almost sure convergence of
(3.15)1nln⁡Dn=-Ynn⟶-β=:α,asn⟶∞.Remark 3.3.
We conjecture thatα from Theorem 3.2 is given by α=ln(3/2). This conjecture is based on the following heuristic argument. From the explicit diagonalization of Z, we find that 𝔼[Dn]=λ′⊤·Zn·γ′=(3/2)n-1 and from (3.14), we deduce 0≤α≤ln(3/2). Moreover, by (3.8), we may write Dn=bneαn, with (1/n)lnbn→0,ℙ-a.s. Now, assuming α<ln(3/2), it would follow that 𝔼[bn]=2/3γn, with γ>1, for which there is no evidence as far as numerical calculations are concerned.



---

*Source: 403140-2012-01-29.xml*