Linear k-Chord Diagrams

Donovan Young St Albans, Hertfordshire AL1 4SZ United Kingdom

               donovan.m.young@gmail.com

Abstract

We generalize the notion of linear chord diagrams to the case of matched sets of size k, which we call k-chord diagrams. We provide formal generating functions and recurrence relations enumerating these k-chord diagrams by the number of short chords, where the latter is defined as all members of the matched set being adjacent, and is the generalization of a short chord or loop in a linear chord diagram. We also enumerate k-chord diagrams by the number of connected components built from short chords and provide the associated generating functions in this case. We show that the distributions of short chords and connected components are asymptotically Poisson, and provide the associated means. Finally, we provide recurrence relations enumerating non-crossing k-chord diagrams by the number of short chords, generalising the Narayana numbers, and establish asymptotic normality, providing the associated means and variances. Applications to generalized games of memory are also discussed.

1 Introduction and basic notions

A chord diagram is a set of n chords drawn between 2n distinct points (which we call vertices) on a circle, such that each vertex participates in exactly one chord. In a linear chord diagram the circle is replaced by a linear arrangement of 2n vertices, and the chords are represented as arcs. The study of chord diagrams has a long and varied history. Early results by Touchard [12] and Riordan [10] studied the number of crossings^{1}. Kreweras and Poupard [7] studied linear chord diagrams. One of their results is the enumeration of short chords, which are defined as chords formed on an adjacent pair of vertices^{2}. They provided recurrence relations and closed form expressions for the number of configurations with exactly ℓ short chords. They also showed that the mean number of short chords is 1, which implies that the total number of short chords is equinumerous with the total number of linear chord diagrams, cf. [2]. Kreweras and Poupard [7] showed further that all higher factorial moments of the distribution approach 1 in the n → ∞ limit, thus establishing the Poisson nature of the asymptotic distribution.

1Cf. Pilaud and Rué [9] for a modern approach and further developments, and also Krasko and Omelchenko [6] for a more complete list of references.

2Short chords are also called “loops” as in [6], or originally “paires courtes” in [7].

Figure 1: A configuration of non-crossing chords.

Kreweras and Poupard [7] also introduced the concept of a “free pair”^{3}. A free pair is a chord which is not crossed by any other chord, and only contains other free pairs, see Figure 1. We will refer to these as non-crossing chords. In Section 4 we will review Kreweras and Poupard’s result that the number of linear chord diagrams consisting entirely of noncrossing chords is in bijection with Dyck paths and is hence counted by the Catalan numbers, and that the number of them with exactly ℓ short chords is counted by the Narayana numbers.

In this paper, we consider a generalization of linear chord diagrams which we refer^{4} to as linear k-chord diagrams. In a k-chord diagram the basic matching represented by a chord is enlarged from a pair of vertices to a set of k vertices, i.e., a k-chord, see Figure 2; a usual chord diagram corresponds to the case k = 2.

Figure 2: A linear k-chord diagram with k = 4 and n = 5. This is a configuration with 2 short chords, 3 non-crossing chords, and 1 connected component (formed by the two adjacent short chords).

The concept of a short chord generalizes directly, as follows:

Definition 1. A short chord is a k-chord formed on a set of adjacent vertices.

We will also be concerned with the notion of a connected component of short chords, see Figure 2.

Definition 2. A connected component in a linear k-chord diagram is a set of adjacent short chords.

3They refer to this as “une paire libre”.

4Pilaud and Rué [9] call an essentially equivalent object a “hyperchord diagram”.

The concept of a non-crossing chord can be generalized to k-chord diagrams as follows:

Definition 3. A non-crossing chord is a k-chord which is not crossed by any other k-chord and only contains other non-crossing chords.

Before presenting the main results of the paper, it is useful to establish a few basic facts.

Proposition 4. The number of linear k-chord diagrams of length kn is given by

N_{k,n} = \frac{(kn)!}{(k!)^{n} n!}.

Proposition 5. The number of number of linear k-chord diagrams of length kn without any short chords is given by

∑_{j=0}^{n}(−1)^{j} N_{k,n−j} ρ_{j},

where ρ_{j} represents the number of ways of choosing j disjoint sub-paths, each with k vertices, from the path of length kn. We define ρ_{0} to be 1.

Proof. The proof proceeds via inclusion-exclusion. We note that for each of the ρ_{j} choices of j sub-paths on which to place j short chords, there remains N_{k,n−j} configurations of the remaining n − j k-chords. There will be some number of configurations among these N_{k,n−j} with exactly q short chords. Then N_{k,n−j} ρ_{j} counts the configurations with exactly q + j short chords \binom{q+j}{j} times. Let N(q) be the number of configurations with exactly q short chords, we therefore have that

∑_{j=0}^{n}(−1)^{j} N_{k,n−j} ρ_{j} = ∑_{j=0}^{n}(−1)^{j} ∑_{q=0}^{n−j} \binom{q + j}{j}N(q + j)

= N(0) + ∑_{q+j=1}^{n} N(q + j) ∑_{j=0}^{q+j}(−1)^{j}\binom{q + j}{j},

and so all but the zero-short-chord configurations cancel.

Theorem 6. The mean number of short chords in a linear k-chord diagram of length kn is given by

\binom{kn}{k}^{−1}n (kn − (k − 1)) .

Proof. The proof proceeds through the linearity of expectation. Let the random variable X_{j} take the value 1 when the j^{th} consecutive set of k vertices forms a short chord and 0 otherwise. Once a short chord is thusly placed, by Proposition 4, there are N_{k,n−1} ways of placing the remaining k-chords on the kn − k remaining vertices. Thus E(X_{j}) = N_{k,n−1}/N_{k,n}. We therefore have that E(∑_{j} X_{j}) = ∑_{j} E(X_{j}) = (kn − (k − 1)) N_{k,n−1}/N_{k,n}, where we have used the fact that there are (kn − (k − 1)) consecutive sets of k vertices.

The result of Theorem 6 shows that the total number of k-chords in all diagrams of a fixed length does not equal the total number of diagrams, unless k = 2. In the limit of long diagrams, the mean scales as lim_{n→∞} \binom{kn}{k}^{−1}n (kn − (k − 1)) = k! k^{1−k} n^{2−k}, and is hence generally suppressed for large n.

2 Enumeration by short chords

We begin by enumerating configurations by number of short chords.

Theorem 7. The number d_{n,ℓ} of linear k-chord diagrams of length kn with exactly ℓ short chords is

d_{n,ℓ} = \frac{1}{ℓ!} ∑_{j=ℓ}^{n} \frac{(k(n − j) + j)! (−1)^{j−ℓ}}{(k!)^{n−j} (n − j)! (j − ℓ)!}.

Proof. This follows from direct calculation from Lemma 10.

In what follows, OEIS denotes the On-Line Encyclopedia of Integer Sequences [11].

n \ℓ 0  1  2  3  4  5 6
1 0  1
2 7  2  1
3 219  53  7  1
4 12861  2296  226  16  1
5 1215794 171785 13080 710 30 1
6 169509845 19796274 1228655 53740 1835 50 1

Table 1: The number d_{n,ℓ} of linear k-chord diagrams of length kn with exactly ℓ short chords, for the case k = 3. OEIS sequence \underline{A334056}; the k = 4 case is \underline{A334057} and the k = 5 case is \underline{A334058}.

Lemma 8. The number of ways of choosing j pairwise non-overlapping subpaths, each of length k, from the path of length ℓ is

\binom{ℓ − j(k − 1)}{j}.

Proof. For each of the j subpaths, collapse the vertices of that subpath onto the left-most vertex, and mark it. We are left with ℓ − j(k − 1) vertices, j of which are marked. Thus there are \binom{ℓ−j(k−1)}{j} choices for the positions of the marked vertices.

Lemma 9. The number of linear k-chord diagrams of length kn with at least j short chords is given by

\frac{(k(n − j))!}{(k!)^{n−j} (n − j)!}\binom{kn − j(k − 1)}{j}.

Proof. We choose j pairwise non-overlapping subpaths, enumerated according to Lemma 8, to place the short chords upon. By Proposition 4, for each such choice we have N_{k,n−j} ways of placing the remaining k-chords.

Lemma 10. The number of linear k-chord diagrams of length kn with exactly ℓ short chords is given by

[z^{ℓ}] ∑_{j=0}^{n} \frac{(k(n − j))!}{(k!)^{n−j} (n − j)!}\binom{kn − j(k − 1)}{j}(z − 1)^{j}.

Proof. This follows from inclusion-exclusion, cf. [13, p. 112].

2.1 Two recurrence relations

Kreweras and Poupard [7] gave a recurrence relation for the d_{n,ℓ} for the case of k = 2,

ℓ d_{n,ℓ} = (2n − ℓ) d_{n−1,ℓ−1} + ℓ d_{n−1,ℓ} ⇔ k = 2.

They obtained this by considering the removal of a short chord at a given position in the chord diagram. This short chord is either nested directly inside another chord, such that its removal does not change the number of short chords, or it is not. A sum over all possible positions of the given short chord then results in the recurrence relation. We now give a generalization of this recurrence relation to the case of general k. Rather than attempt to repeat Kreweras and Poupard’s arguments, which should be possible but rather complicated due to dealing with the ends of the diagram, we prove our recurrence relation directly from Theorem 7.

Theorem 11. The numbers d_{n,ℓ} satisfy the following recurrence relation

ℓ d_{n,ℓ} = (kn − ℓ(k − 1)) d_{n−1,ℓ−1} + ℓ(k − 1) d_{n−1,ℓ}.

Proof. We use the result of Theorem 7 and consider d_{n−1,ℓ−1} − d_{n−1,ℓ}. In each of the two summands, we shift the summation variable j → j − 1. This procedure results in a relative sign difference between the summands. In d_{n−1,ℓ−1} the sum begins at j = ℓ as before, whereas in d_{n−1,ℓ}, it now begins at j = ℓ+1. We proceed by stripping off the j = ℓ term from d_{n−1,ℓ−1}

d_{n−1,ℓ−1} − d_{n−1,ℓ} = \frac{(k(n − ℓ) + ℓ − 1)!}{(k!)^{n−ℓ} (n − ℓ)!} \frac{1}{(ℓ − 1)!}

+ ∑_{j=ℓ+1}^{n} \frac{(k(n − j) + j − 1)! (−1)^{j−ℓ}}{(k!)^{n−j} (n − j)!} (\frac{1}{(j − ℓ)!(ℓ − 1)!} + \frac{1}{(j − ℓ − 1)!ℓ!})

= \frac{(k(n − ℓ) + ℓ − 1)!}{(k!)^{n−ℓ} (n − ℓ)!} \frac{1}{(ℓ − 1)!} + ∑_{j=ℓ+1}^{n} \frac{(k(n − j) + j − 1)! (−1)^{j−ℓ}}{(k!)^{n−j} (n − j)!} (\frac{j/ℓ}{(j − ℓ)!(ℓ − 1)!}) .

It follows that

kn d_{n−1,ℓ−1} − ℓ(k − 1) (d_{n−1,ℓ−1} − d_{n−1,ℓ})

= \frac{(k(n − ℓ) + ℓ − 1)!}{(k!)^{n−ℓ} (n − ℓ)!} \frac{(kn − ℓ(k − 1))}{(ℓ − 1)!}

+ ∑_{j=ℓ+1}^{n} \frac{(k(n − j) + j − 1)! (−1)^{j−ℓ}}{(k!)^{n−j} (n − j)!} (\frac{kn − j(k − 1)}{(j − ℓ)!(ℓ − 1)!})

= \frac{1}{(ℓ − 1)!} ∑_{j=ℓ}^{n} \frac{(k(n − j) + j)! (−1)^{j−ℓ}}{(k!)^{n−j} (n − j)! (j − ℓ)!} = ℓ d_{n,ℓ}.

Krasko and Omelchenko [6] gave another recurrence relation for the d_{n,ℓ} in the case of k = 2,

d_{n+1,ℓ} = d_{n,ℓ−1} + (2n − ℓ)d_{n,ℓ} + (ℓ + 1)d_{n,ℓ+1} ⇔ k = 2.

This relation is found by considering the addition of a new chord, with one end anchored outside the existing vertices. The other end of the chord could be placed in various positions: adjacent to the anchored end hence forming an external short chord, in a location which disturbs no existing short chord, or within an existing short chord and hence breaking it up. These cases account, respectively, for the three terms in the recurrence relation. To generalize this to a k-chord diagram we must account for a larger variety of cases.

Theorem 12. The numbers d_{n,ℓ} satisfy the following recurrence relation

d_{n+1,ℓ} = d_{n,ℓ−1} + d_{n,ℓ} ∑_{h=1}^{k−1} \binom{kn − (k − 1)ℓ + k − h − 1}{k − h} + ∑_{p=1}^{k−1} C_{n,ℓ,p,k} d_{n,ℓ+p},

where the C_{n,ℓ,p,k} are given by

C_{n,ℓ,p,k} = ∑_{h=1}^{k−p} ∑_{f=0}^{k−p−h} \binom{kn − (k − 1)(ℓ + p) + f − 1}{f}[x^{k−h−f}y^{p}] (1 + y − y(1 − x)^{1−k})^{−ℓ−1} .

Figure 3: The first term in the recurrence relation in Theorem 12. A new k-chord (shown in red dashes) is added as a short chord to the end of an existing configuration.

Proof. The recurrence relation arises from the addition of a new k-chord, at least one strand of which is anchored to the right of all existing vertices, to a configuration of length kn. One of the ways we could add these vertices is as a short chord placed on the end of the existing configuration, as in Figure 3. This accounts for the first term in the recurrence relation.

We now consider the various positions which the strands of the new k-chord could occupy. If they remain to the right of all existing vertices, we consider them to be at home. If a strand is not at home, but is placed such that it does not disturb any existing short chord, we say that it is in the forest. If the existing configuration has ℓ + p short chords, there are kn − (k − 1)(ℓ + p) forest positions.

The second term in the recurrence relation arises from leaving h ≥ 1 strands at home, and placing the remaining f = k−h strands into forest positions only, i.e., no strand which is not at home is placed within an existing short chord. The number of ways of accomplishing this is the same as the number of ways of placing f = k − h identical balls into kn − (k − 1)ℓ distinguishable bins.

The third term in the recurrence relation accounts for the general case: h ≥ 1 strands are left at home, f ≥ 0 occupy forest positions, and the remainder disturb existing short chords. An example is shown in Figure 4. The result follows from the preceding treatment of forest positions (there are now kn−(k −1)(ℓ+p) of these) in conjunction with Lemma 14, where the j balls represent the k − h − f strands which disturb short chords, and the p bins represent the p disturbed short chords, each of which can be disturbed in up to k − 1 positions.

Figure 4: A general configuration from Theorem 12, with k = 4, n = 3, ℓ = 0, h = 2, f = 1, and p = 1.

Example 13. The recurrence relation for the case k = 3 is given by

d_{n+1,ℓ} = d_{n,ℓ−1}

+ \frac{(3n − 2ℓ + 3)(3n − 2ℓ)}{2} d_{n,ℓ} + (ℓ + 1)(6n − 4ℓ + 1) d_{n,ℓ+1} + 2(ℓ + 1)(ℓ + 2) d_{n,ℓ+2}.

Lemma 14. The number of ways of placing j identical balls into a selection of p, out of ℓ + p distinguishable bins, each containing k − 1 distinguishable sub-bins, such that no bin is empty (though any sub-bin could be), is

[x^{j}y^{p}] (1 + y − y(1 − x)^{1−k})^{−ℓ−1} .

Proof. We first note that there are \binom{ℓ+p}{p} ways to choose the p bins. To enumerate the possible ways of filling the sub-bins we consider the weak compositions of 1, 2, 3, … into k − 1 parts. For a given bin, let f(x) be the generating function such that [x^{m}]f(x) counts the number of ways of placing m balls into the k − 1 sub-bins. We have that

f(x) = \binom{k − 1}{k − 2}x + \binom{k}{k − 2}x^{2} + \binom{k + 1}{k − 2}x^{3} + ⋯ = (1 − x)^{1−k} − 1.

To now account for p bins, we take f(x)^{p}, and note that

∑_{p} \binom{ℓ + p}{p}f(x)^{p}y^{p} = (1 + y − y(1 − x)^{1−k})^{−ℓ−1} .

3 Generating functions

In this section we establish formal generating functions enumerating configurations firstly by number of short chords (Theorem 17),

F_{k}(w, z) = ∑_{n≥0} ∑_{ℓ=0}^{n} d_{n,ℓ} w^{n}z^{ℓ} = ∑_{j≥0} \frac{(kj)!}{j!(k!)^{j}} \frac{w^{j}}{(1 + w(1 − z))^{kj+1}} ,

where the power of w corresponds to n and the power of z corresponds to the number of short chords, and secondly by the number of connected components (Theorem 21)

C_{k}(y, z) = ∑_{n,q≥0} c_{n,q} y^{n}z^{q} = ∑_{j≥0} \frac{(kj)!}{j!(k!)^{j}} y^{j} (\frac{1 − y(1 − z)}{1 − y^{2}(1 − z)})^{kj+1} ,

where the power of y corresponds to n and the power of z corresponds to the number of connected components. These generating functions are not convergent, but nevertheless provide compact expressions for the numbers they count.

3.1 Counting by number of short chords

Proposition 15. The generating function which counts the number of ways of choosing j pairwise non-overlapping subpaths, each of length k, from a path of length ℓ is

L_{k}(x, y) = \frac{1}{1 − y(1 + x^{k}y^{k−1})},

where the power of x corresponds to the total number of vertices in all chosen sub-paths, and the power of y corresponds to the length of the path.

Proof. By direct expansion L_{k}(x, y) = ∑_{p≥0} ∑_{j=0}^{p} \binom{p}{j}x^{kj} y^{(k−1)j+p}, so [x^{kj}y^{ℓ}]L_{k}(x, y) = \binom{ℓ−j(k−1)}{j}. By Lemma 8, the proposition is proven.

Lemma 16. The generating function which counts the number of linear k-chord diagrams of length kn with at least j short chords is given by

N_{k}(w^{k}, z^{k}) = ∫_{0}^{∞} dt e^{−t} \frac{1}{2πi} ∮_{|x|=ϵ} \frac{dx}{x} e^{x^{k}/k!} L_{k} (\frac{zx}{t}, \frac{wt}{x}) ,

where [w^{n}z^{j}] N_{k}(w, z) is the number of linear k-chord diagrams of length kn with at least j short chords.

Proof. We begin by noting that

[w^{kn}z^{kj}] ∫_{0}^{∞} dt e^{−t} L_{k} (\frac{zx}{t}, \frac{wt}{x}) = ∫_{0}^{∞} dt e^{−t} t^{kn−kj}\binom{kn − j(k − 1)}{j}x^{kj−kn}

= (kn − kj)!\binom{kn − j(k − 1)}{j}x^{kj−kn},

where we have made use of Lemma 8. We now note that

[x^{kn−kj}]e^{x^{k}/k!} = \frac{1}{(k!)^{n−j} (n − j)!},

and so the contour integral selects precisely this term in the expansion of e^{x^{k}/k!}. We therefore have that

[w^{kn}z^{kj}] ∫_{0}^{∞} dt e^{−t} \frac{1}{2πi} ∮_{|x|=ϵ} \frac{dx}{x} e^{x^{k}/k!} L_{k} (\frac{zx}{t}, \frac{wt}{x}) = \frac{(kn − kj)!}{(k!)^{n−j} (n − j)!}\binom{kn − j(k − 1)}{j},

and by Lemma 9 the proof is complete.

Theorem 17. The generating function which counts the number of linear k-chord diagrams of length kn with exactly ℓ short chords is given by

F_{k}(w, z) = ∑_{j≥0} \frac{(kj)!}{j!(k!)^{j}} \frac{w^{j}}{(1 + w(1 − z))^{kj+1}} ,

where the power of w corresponds to n and the power of z corresponds to ℓ.

Proof. We use Lemma 16 to find the generating function for at least j short chords, and then replacing z → z − 1 at the end, as per Lemma 10, yields the desired result. We note that

\frac{1}{2πi} ∮_{|x|=ϵ} \frac{dx}{x} e^{x^{k}/k!}L_{k} (\frac{zx}{t}, \frac{wt}{x}) = \frac{1}{2πi} ∮_{|x|=ϵ} dx \frac{e^{x^{k}/k!}}{x (1 − (wz)^{k}) − tw},

where we have made use of Proposition 15. We proceed by evaluating the residue at x = tw/(1 − (wz)^{k})

N_{k}(w^{k}, z^{k}) = ∫_{0}^{∞} dt e^{−t} \frac{1}{1 − (wz)^{k}} exp (\frac{t^{k}w^{k}}{k! (1 − (wz)^{k})^{k}} )

= ∫_{0}^{∞} dt e^{−t} \frac{1}{1 − (wz)^{k}} ∑_{j≥0} \frac{1}{j!} (\frac{t^{k}w^{k}}{k! (1 − (wz)^{k})^{k}} )^{j} ,

where the integration over t is understood to be performed term-by-term in the expansion of the exponential, thus yielding a factor of (kj)!. Note that w and z appear uniformly with exponent k; we can therefore remove the exponents by considering N_{k}(w, z) in place of N_{k}(w^{k}, z^{k}). Finally, we have that

F_{k}(w, z) = N_{k}(w, z − 1) = ∑_{j≥0} \frac{(kj)!}{j!(k!)^{j}} \frac{w^{j}}{(1 + w(1 − z))^{kj+1}} .

3.2 Counting by number of connected components

We now turn our attention to counting configurations by the number of connected components, as defined in Definition 2. Let there be q connected components; it is clear that there are therefore at least q − 1 and at most q + 1 regions devoid of short chords, depending on whether the first and last vertices are occupied by short chords or not. We will require the number ρ_{j} of ways of choosing j non-overlapping sub-paths from this disjoint collection of regions. Proposition 5 will then count the number of “zero-short-chord” configurations on these regions.

Lemma 18. The numbers which count ρ_{j} (cf. Proposition 5) for the case of a single component of size km, where m ≥ 1, are denoted ρ_{j}^{(1)}(m). We have that

ρ_{j}^{(1)}(m) = [x^{kj}y^{kn−km}]L_{k}(x, y)^{2}.

Proof. The result follows from Proposition 15. The sum over the position of the connected component is accounted for through the symbolic method.

Each further component which is added produces a new region, which, rather than being bounded on one side by the ends of the k-chord diagram, is bounded by two connected components. It is clear that these new regions must not be allowed to have zero length; this is accomplished by subtracting 1 from L_{k}(x, y).

Lemma 19. The numbers ρ_{j}^{(q)}(m_{1}, …, m_{q}) which count ρ_{j} for the case of q connected components, of sizes km_{1}, …, km_{q}, summed over positions, is

ρ_{j}^{(q)}(m_{1}, …, m_{q}) = [x^{kj}y^{kn−k ∑ m_{p}}] L_{k}(x, y)^{2} (L_{k}(x, y) − 1)^{q−1} .

Proof. This follows from the symbolic method.

Lemma 20.

∑_{j=0}^{ñ}(−1)^{j}N_{k,ñ−j} ρ_{j}^{(q)}(m_{1}, …, m_{q})

= [y^{kñ}] ∫_{0}^{∞} dt e^{−t} \frac{1}{2πi} ∮_{|x|=ϵ} \frac{dx}{x} e^{x^{k}/k!} L_{k} (\frac{xe^{iπ/k}}{t} , \frac{yt}{x})^{2} (L_{k} (\frac{xe^{iπ/k}}{t} , \frac{yt}{x}) − 1)^{q−1} ,

where ñ = n − ∑ m_{p}.

Proof. The scaling of the x and y variables, together with the result of Lemma 19, imply that

[y^{kñ}]L_{k} (\frac{xe^{iπ/k}}{t} , \frac{yt}{x})^{2} (L_{k} (\frac{xe^{iπ/k}}{t} , \frac{yt}{x}) − 1)^{q−1}

= ∑_{j=0}^{ñ}(−1)^{j}x^{kj−kñ} t^{kñ−kj}ρ_{j}^{(q)}(m_{1}, …, m_{q}).

Note that the integration over t then enacts the replacement t^{kñ−kj} → (kñ − kj)!. We now consider

[x^{0}] e^{x^{k}/k!} ∑_{j=0}^{ñ}(−1)^{j}x^{kj−kñ} (kñ − kj)!ρ_{j}^{(q)}(m_{1}, …, m_{q})

= [x^{0}] ∑_{ℓ} \frac{x^{kℓ}}{(k!)^{ℓ}ℓ!} ∑_{j=0}^{ñ}(−1)^{j}x^{kj−kñ} ρ_{j}^{(q)}(m_{1}, …, m_{q})

= ∑_{j=0}^{ñ}(−1)^{j} \frac{(kñ − kj)!}{(k!)^{ñ−j}(ñ − j)!}ρ_{j}^{(q)}(m_{1}, …, m_{q}),

and so the contour integral in x picks out precisely this expression.

n \q 0  1  2  3  4
1 0  1
2 7  3
3 219  56  5
4 12861  2352  183  4
5 1215794 174137 11145 323 1
6 169509845 19970411 1078977 30833 334

Table 2: The numbers c_{n,q} of linear k-chord diagrams of length kn with exactly q connected components for the case k = 3. OEIS sequence \underline{A334060}; the k = 2 case is \underline{A334059} and the k = 4 case is \underline{A334061}.

Theorem 21. The numbers c_{n,q} = [y^{n}z^{q}]C_{k}(y, z) count the number of k-chord diagrams of length kn with exactly q connected components, where

C_{k}(y, z) = ∑_{j≥0} \frac{(kj)!}{j!(k!)^{j}} y^{j} (\frac{1 − y(1 − z)}{1 − y^{2}(1 − z)})^{kj+1} .

Proof. We now make use of Lemma 20 and sum over the sizes m_{1}, …, m_{q} of the connected components

C_{k}(y^{k}, z) − C_{k}(y^{k}, 0) = ∑_{q≥1} z^{q} ∑_{{m_{p}≥1}} y^{k ∑ m_{p}} ∑_{j=0}^{ñ}(−1)^{j}N_{k,ñ−j} ρ_{j}^{(q)}(m_{1}, …, m_{q})

= ∑_{q≥1} z^{q} (\frac{y^{k}}{1 − y^{k}} )^{q} ∫_{0}^{∞} dt e^{−t} \frac{1}{2πi} ∮_{|x|=ϵ} \frac{dx}{x} e^{x^{k}/k!} L_{k} (\frac{xe^{iπ/k}}{t} , \frac{yt}{x})^{2} (L_{k} (\frac{xe^{iπ/k}}{t} , \frac{yt}{x}) − 1)^{q−1}

= ∫_{0}^{∞} dt e^{−t} \frac{1}{2πi} ∮_{|x|=ϵ} \frac{dx}{x} e^{x^{k}/k!} ∑_{q≥1} \frac{−x^{2}(zy^{k})^{q}(xy^{k} − ty)^{q−1}}{(y^{k} − 1)^{q}(x − ty + xy^{k})^{1+q}}

= ∫_{0}^{∞} dt e^{−t} \frac{1}{2πi} ∮_{|x|=ϵ} \frac{dx}{x} e^{x^{k}/k!} \frac{x^{2}z y^{k}}{(x(1 + y^{k}) − ty)(x(1 − y^{2k}(1 − z)) − ty(1 − y^{k}(1 − z)))}

= ∫_{0}^{∞} dt e^{−t} (\frac{1 − y^{k}(1 − z)}{1 − y^{2k}(1 − z)} exp \frac{t^{k}}{k!} (\frac{y(1 − y^{k}(1 − z))}{1 − y^{2k}(1 − z)})^{k} − \frac{1}{1 + y^{k}} exp \frac{t^{k}}{k!} (\frac{y}{1 + y^{k}} )^{k}) .

The integration over t proceeds term-by-term in an expansion of the exponentials as was seen in Theorem 17. In going from the penultimate line to the last, the contour integral picks-up two residues, one of which produces precisely minus the generating function for the zero-short chord configurations, i.e., −F_{k}(y, 0) from Theorem 17, corresponding to the case of zero connected components. Adding this back as a z^{0} term, and replacing y^{k} → y we obtain the advertised result for C_{k}(y, z).

3.3 Asymptotic distributions

We expect the asymptotic distribution of short chords, i.e.,

lim_{n→∞} \frac{d_{n,ℓ}}{N_{k,n}} ,

to be Poisson with mean given by (the large-n limit of) Theorem 6

λ = lim_{n→∞} \binom{kn}{k}^{−1}n (kn − (k − 1)) = k! k^{1−k} n^{2−k}.

The distribution of connected components

lim_{n→∞} \frac{c_{n,q}}{N_{k,n}} ,

should have the same distribution. This is because for long diagrams, most configurations with ℓ short chords will also have ℓ trivially connected components. We begin by considering short chords. Theorem 22. The asymptotic distribution of short chords is Poisson with mean λ = k! k^{1−k} n^{2−k}. Proof. Using Lemma 10, we have that

lim_{n→∞} \frac{d_{n,ℓ}}{N_{k,n}} = [z^{ℓ}] lim_{n→∞} ∑_{j=0}^{n}(k!)^{j} \frac{n!}{(n − j)!} \frac{(k(n − j))!}{(kn)!}\binom{kn − j(k − 1)}{j}(z − 1)^{j}

= [z^{ℓ}] ∑_{j=0}^{∞}(k!)^{j}n^{j} \frac{1}{(kn)^{kj}} \frac{(kn)^{j}}{j!} (z − 1)^{j} = [z^{ℓ}] ∑_{j=0}^{∞} \frac{1}{j!} (\frac{k!}{k^{k−1}n^{k−2}} )^{j} (z − 1)^{j}

= [z^{ℓ}] ∑_{j=0}^{∞} \frac{λ^{j}}{j!} (z − 1)^{j}.

It follows that the j^{th} factorial moment is λ^{j}, and hence the distribution is Poisson. Theorem 23. The asymptotic distribution of connected components is Poisson with mean λ = k! k^{1−k} n^{2−k}. Proof. We begin by expanding the generating function given in Theorem 21

\frac{c_{n,q}}{N_{k,n}} = \frac{1}{N_{k,n}} [y^{n}z^{q}] ∑_{j≥0} \frac{(kj)!}{j!(k!)^{j}} y^{j} (\frac{1 − y(1 − z)}{1 − y^{2}(1 − z)})^{kj+1}

= ∑_{j≥0} \frac{N_{k,j}}{N_{k,n}} [y^{n}z^{q}] ∑_{p,r} y^{j+p+2r}(z − 1)^{p+r}\binom{kj + 1}{p}\binom{kj + r}{r}(−1)^{r}

= ∑_{j≥0} \frac{N_{k,j}}{N_{k,n}} [y^{n}z^{q}] ∑_{ℓ,r} y^{j+ℓ+r}(z − 1)^{ℓ}\binom{kj + 1}{ℓ − r}\binom{kj + r}{r}(−1)^{r}

= [z^{q}] ∑_{ℓ,r} \frac{N_{k,n−ℓ−r}}{N_{k,n}} (z − 1)^{ℓ}\binom{k(n − ℓ − r) + 1}{ℓ − r}\binom{k(n − ℓ − r) + r}{r}(−1)^{r}.

We now take the n → ∞ limit

lim_{n→∞} \frac{c_{n,q}}{N_{k,n}} = [z^{q}] ∑_{ℓ,r} \frac{(k!)^{ℓ+r}}{k^{k(ℓ+r)}n^{(k−1)(ℓ+r)}} (z − 1)^{ℓ} \frac{(kn)^{ℓ−r}}{(ℓ − r)!} \frac{(kn)^{r}}{r!} (−1)^{r}

= [z^{q}] ∑_{ℓ,r} \frac{(−1)^{r}}{ℓ!} \binom{ℓ}{r} (\frac{k!}{k^{k} n^{k−1}} )^{r} (z − 1)^{ℓ} λ^{ℓ} = [z^{q}] ∑_{ℓ} (1 − \frac{k!}{k^{k} n^{k−1}} )^{ℓ} \frac{(z − 1)^{ℓ} λ^{ℓ}}{ℓ!}

≃ [z^{q}] ∑_{ℓ} \frac{(z − 1)^{ℓ} λ^{ℓ}}{ℓ!} .

It follows that the j^{th} factorial moment is λ^{j}, and hence the distribution is Poisson.

4 Non-crossing configurations

For the case of linear chord diagrams the enumeration of so-called non-crossing configurations, where no two chords cross each other, is by now standard combinatorical lore. For the sake of completeness, and in order to motivate the case for general k, we repeat the main elements of the arguments given by Kreweras and Poupard [7], who established a bijection with Dyck paths. The mapping is as follows: traversing the path of length 2n from left to right, we map the start of a chord to an up step (0, +1), and the end of a chord with a down step (+1, 0).

Figure 5: The bijection between non-crossing configurations and lattice paths for the case of k = 3.

To establish the mapping in the other direction, we associate consecutive up steps with the starting vertices of successively nested chords. It is clear that there are n up steps and n down steps, and that the first step is always an up step. A short chord is mapped to a peak, i.e., to an up step immediately followed by a down step. Therefore the Narayana numbers \binom{n}{ℓ}\binom{n}{ℓ−1}/n give the number of non-crossing configurations with exactly ℓ short chords, and the Catalan numbers \binom{2n}{n}/(n + 1) count the total number of non-crossing configurations. The bijection to lattice paths can be extended for general k, to paths which begin and end on the line y = (k − 1)x. A short chord, traversed left to right, is represented by k − 1 up steps followed by a single down step, see Figure 5^{5}.

In order to generalize the counting to linear k-chord diagrams we establish the following recurrence.

Theorem 24. The number T_{m,ℓ} of non-crossing linear k-chord diagrams of length km with exactly ℓ short chords, obeys the following recurrence relation

T_{m+1,ℓ} = ∑_{\begin{matrix}∑ m_{i}=m \\ ∑ ℓ_{i}=ℓ \end{matrix}} ∏_{i=1}^{k} T_{m_{i},ℓ_{i}} − T_{m,ℓ} + T_{m,ℓ−1}, T_{0,0} = 1.

Proof. The proof proceeds diagrammatically, see Figure 6. The first term accounts for all possible nestings of smaller non-crossing diagrams in the k − 1 arches, and also to the left, of an additional k-chord. This term counts one set of configurations incorrectly, which are those pictured on the right in Figure 6. When the arches are empty, corresponding to m_{i>1} = 0, ℓ_{i>1} = 0, the additional k-chord is also a short chord. Thus this set of configurations must be subtracted, and hence the second term in the recurrence relation. The third term adds back the correction.

Figure 6: Configurations of non-crossing linear k-chord diagrams for the case of k = 4. The circles represent all non-crossing linear 4-chord diagrams with m_{i} 4-chords, ℓ_{i} of which are short chords.

Corollary 25. The generating function for the T_{m,ℓ} is T (x, y) = ∑_{m,ℓ≥0} T_{m,ℓ} x^{m}y^{ℓ} and obeys

T (x, y) − 1 = xT (x, y)^{k} − x(1 − y)T (x, y).

Proof. This is shown by multiplying the recurrence relation of Theorem 24 by x^{m+1}y^{ℓ} and summing over m and ℓ.

Corollary 26. The total number of of non-crossing linear k-chord diagrams of length km is given by the Fuss-Catalan number

T_{m} = ∑_{ℓ=1}^{m} T_{m,ℓ} = \frac{1}{(k − 1)m + 1}\binom{km}{m}.

chords, cf. \underline{A091320}.

5There is an additional bijection for the case of k = 3 to (rooted) non-crossing trees [8], where the (nonroot) vertices correspond to chords, their level to the nesting level of the chords, and the leaves to short

Proof. This can be established via Lagrange inversion on Corollary 25, with y = 1. We have that

x = \frac{T (x, 1) − 1}{T (x, 1)^{k}} = f(T (x, 1)),

g_{m} = lim_{w→1} \frac{d^{m−1}}{dw^{m−1}} (\frac{w − 1}{f(w) − f(1)})^{m} = lim_{w→1} \frac{d^{m−1}w^{km}}{dw^{m−1}} = \frac{(km)!}{((k − 1)m + 1)!},

T (x, 1) = 1 + ∑_{m>0} g_{m} \frac{x^{m}}{m!} = 1 + ∑_{m>0} \frac{x^{m}}{(k − 1)m + 1}\binom{km}{m}.

The Fuss-Catalan numbers appear as \underline{A062993} in the OEIS.

Kreweras and Poupard [7] also give a closed expression for the number d_{n,ℓ,m} of linear chord diagrams on the path of length 2n with m non-crossing chords and ℓ short chords

d_{n,ℓ,m} = \frac{2n − 2m + 1}{m}\binom{m}{ℓ}\binom{2n − m}{ℓ − 1} d_{n−m,0} ⇔ k = 2.

They obtain this by considering disconnected regions consisting solely of non-crossing chords. They note that upon removing these regions, and joining the remaining components, one is necessarily left with a zero-short-chord configuration of length 2n−2m; hence the appearance of the number of such configurations, i.e., d_{n−m,0}. For a general value of k, we have the following theorem.

Theorem 27. The number d_{n,ℓ,m} of linear k-chord diagrams of length kn with exactly ℓ short chords, and exactly m non-crossing chords is given by

d_{n,ℓ,m} = [x^{m}y^{ℓ}] T (x, y)^{kn−km+1} d_{n−m,0},

where d_{n−m,0} is the number of zero-short-chord configurations.

Proof. We consider a general linear k-chord diagram on the path of length kn. Let there be p disjoint regions, each consisting solely of non-crossing k-chords. When we remove these regions, we are left with a path of length kn − km where m is the number of non-crossing k-chords. There are thus \binom{kn−km+1}{p} distinct ways of placing the p regions. We need to sum over all possible sizes of these regions, and also over all possible distributions of the ℓ short chords amongst the p regions. These sums take place automatically using the symbolic method by adding a factor of (T (x, y) − 1)^{p}, where we subtract 1 because the regions cannot be empty. Finally, we multiply by d_{n−m,0}, because the configuration on the path of length kn − km is necessarily one with no short chords. We therefore have that

d_{n,ℓ,m} = d_{n−m,0} ∑_{p} \binom{kn − km + 1}{p}[x^{m}y^{ℓ}] (T (x, y) − 1)^{p} = [x^{m}y^{ℓ}] T (x, y)^{kn−km+1} d_{n−m,0}.

n \ℓ 1 2 3  4  5 6 7
1 1
2 2 1
3 4 7 1
4 8 30 16 1
5 16 104 122 30 1
6 32 320 660 365 50 1
7 64 912 2920 2875 903 77 1

Table 3: The number T_{n,ℓ} of non-crossing linear k-chord diagrams with exactly ℓ short chords for the case k = 3. OEIS sequence \underline{A091320}; the k = 4 case is \underline{A334062} and the k = 5 case is \underline{A334063}.

4.1 Asymptotic distribution of short chords

In this section we consider the asymptotic distribution of short chords amongst non-crossing configurations, i.e.,

lim_{n→∞} \frac{T_{n,ℓ}}{T_{n}} .

It has been established that the Narayana numbers (i.e., the k = 2 case) are asymptotically normally distributed, cf. [5], with mean μ = n/2 and variance σ^{2} = n/8. In this section we appeal to the methods of Flajolet and Noy [3, Theorem 5] to establish the following generalization.

Theorem 28. The numbers T_{n,ℓ} of non-crossing linear k-chord diagrams of length kn, with exactly ℓ short chords, are asymptotically normally distributed with mean μ and variance σ^{2} given by

μ = (\frac{k − 1}{k})^{k−1} n, σ^{2} = (\frac{k − 1}{k})^{2k} \frac{k}{(k − 1)^{2}} (1 − 2k + (k − 1) (\frac{k}{k − 1})^{k}) n.

Proof. The methods used by Flajolet and Noy [3, Theorem 5] extend the analytic combinatorics of implicitly defined generating functions, as treated in Flajolet and Sedgewick [4, Section VI.7], to the case of bivariate generating functions. In the univariate case (i.e., setting y = 1 in T (x, y)), it is straightforward to establish an asymptotic expansion

T (x, 1) = d_{0} + d_{1}\sqrt{1 − x/ρ} + O(1 − x/ρ),

which then implies the asymptotic growth

[x^{n}]T (x, 1) ∼ γ \frac{ρ^{−n}}{\sqrt{πn^{3}}} (1 + O(n^{−1})) , ρ = \frac{(k − 1)^{k−1}}{k^{k}} , γ = \sqrt{\frac{k}{2(k − 1)^{3}}} .

The method of Flajolet and Noy is to extend this to the bivariate case by considering y as a parameter. We begin by expressing the recurrence relation of Theorem 24 as follows:

T (x, y) = x ϕ (T (x, y)) ⇒ ϕ(u) = (1 + u)^{k} − (1 − y)(1 + u).

We are then tasked with solving the so-called characteristic equation

ϕ(τ(y)) − τ(y)ϕ′(τ(y)) = 0,

which in our case is

(1 + τ)^{k} − (1 − y)(1 + τ) − τ (k(1 + τ)^{k−1} − (1 − y)) = 0.

Solving this equation in an expansion of τ(y) about y = 1, we find

τ(y) = \frac{1}{k − 1} + \frac{k}{(k − 1)^{2}} (\frac{k − 1}{k})^{k} (y − 1) − \frac{k}{(k − 1)^{2}} (\frac{k − 1}{k})^{2k} (y − 1)^{2} + O ((y − 1)^{3}) ,

which further implies an expansion for

ρ(y) = \frac{τ(y)}{ϕ (τ(y))}.

Flajolet and Noy establish that this implies the following asymptotic growth

[x^{n}]T (x, y) = γ(y) ρ(y)^{−n} (1 + O(n^{−1/2})) ,

where γ(y) is an analytic function of y. The asymptotic normality is then established through results due to Bender and Richmond [1]. The probability generating function for the distribution is given by

\frac{[x^{n}]T (x, y)}{[x^{n}]T (x, 1)} = \frac{γ(y)}{γ(1)} (\frac{ρ(y)}{ρ(1)})^{−n} (1 + O(n^{−1/2})) .

The mean and variance are computed in the usual way

μ = −\frac{ρ′(1)}{ρ(1)}, σ^{2} = −\frac{ρ′′(1)}{ρ(1)} − \frac{ρ′(1)}{ρ(1)} + (\frac{ρ′(1)}{ρ(1)})^{2} ,

and this results in

μ = (\frac{k − 1}{k})^{k−1} n, σ^{2} = (\frac{k − 1}{k})^{2k} \frac{k}{(k − 1)^{2}} (1 − 2k + (k − 1) (\frac{k}{k − 1})^{k}) n.

Corollary 29. The mean μ and variance σ^{2} are given by the following expressions in the k → ∞ limit

μ = \frac{n}{e}, σ^{2} = \frac{e − 2}{e^{2}} n.

5 Applications to generalized games of memory

In the game of memory, n distinct pairs of cards are placed in an array. The present author [14, 15] has enumerated configurations for 2 × n rectangular arrays in which exactly ℓ of the pairs are found side-by-side, or over top of one another, thus forming 1 × 2 or 2 × 1 dominoes. The enumeration of these configurations always carries a factor of n!, which counts the orderings of the n distinguishable pairs. It is therefore easier to drop this factor, and thus treat the pairs as indistinguishable. For the case of 1 × 2n arrays the configuration of the cards is then in one-to-one correspondence with linear chord diagrams, where the dominoes correspond to short chords.

More generally, the array which the cards are placed on can be specified by a graph G on 2n vertices, representing the positions of the cards, and such that an edge of G indicates adjacency in the array — for example, a rectangular array would be specified by a grid graph of the same dimension. A matched pair of cards occupying two adjacent vertices of G then constitutes a domino. The present author [14] obtained the mean for the distribution of dominoes for general arrays was obtained in terms of the number of edges of the graph G.

The results of the present paper lend themselves to a generalized game of memory in which n distinct sets of k matched cards are placed in an array specified by a graph G on kn vertices. The notion of a domino then generalizes to that of a polyomino, see Figure 7. The results of the previous sections may be interpreted as pertaining to this generalized game, where the array is a single row of length kn, and so G is the path on kn vertices.

Definition 30. A polyomino is a set of k matching cards which occupy a connected subgraph of G with k vertices.

Figure 7: A configuration with a single polyomino (the red cards marked “R”) in a generalized game of memory with k = 3 and n = 3, played on a square array.

We may employ a slightly more general version of Theorem 6 to compute the mean number of polyominoes.

Theorem 31. The mean number of polyominoes in a generalized game of memory played on a graph with kn vertices and r connected subgraphs, each with k vertices, is given by

\binom{kn}{k}^{−1}nr.

Proof. The proof proceeds through the linearity of expectation. Let the random variable X_{j} take the value 1 when the j^{th} connected subgraph forms a polyomino matching and 0 otherwise. Once a polyomino is thusly placed, by Proposition 4, there are N_{k,n−1} ways of placing the remaining cards on the kn − k remaining vertices of the graph. Thus E(X_{j}) = N_{k,n−1}/N_{k,n}. We therefore have that E(∑_{j=1}^{r} X_{j}) = ∑_{j=1}^{r} E(X_{j}) = r N_{k,n−1}/N_{k,n}.

It is interesting to consider how this mean scales with n → ∞ for hypercubical grid (or other regular) graphs. For fixed k, we expect the number r of subgraphs on k vertices to scale as n. We thus expect the mean to scale as n^{2}/n^{k} = n^{2−k}. Indeed, for large hypercubical grid graphs of dimension d, the present author [14, Corollary 2] showed that the mean number of dominoes approaches d (and is hence O(n^{0})). For k > 2, polyominoes are instead suppressed as n grows large.

We may also introduce the notion of a connected component of polyominoes, see Figure 8.

Definition 32. A connected component is a set of polyominoes which occupy a single connected subgraph of G.

Figure 8: A configuration in a generalized game of memory with k = 3 and n = 5 with two connected components: the red “R” and blue “B” cards form one connected component and the pink “P” cards form another.

The notion of non-crossing configurations is more subtle to generalize beyond the case of the linear array, and a precise definition will be left to further work. The problem of enumerating configurations in generalized games of memory by polyominoes, connected components, and (suitably defined) non-crossing arrangements is interesting, and likely very difficult to obtain exact results for in general.

References

[1] E. Bender and L. B. Richmond, Central and local limit theorems applied to asymptotic enumeration II: multivariate generating functions, J. Combin. Theory Ser. A 34 (1983), 255–265.

[2] N. T. Cameron and K. Killpatrick, Statistics on linear chord diagrams, Discrete Math. Theor. Comput. Sci. 21 (2019) #11. Available at https://dmtcs.episciences.org/

    6038/pdf.

[3] P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math. 204 (1999), 203–229.

[4] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[5] J. Fullman and A. Roellin, Stein’s method and Narayana numbers, arxiv preprint, 2018.

Available at https://arxiv.org/abs/1808.09609.

[6] E. Krasko and A. Omelchenko, Enumeration of chord diagrams without loops and parallel chords, Electron. J. Combin. 24 (2017), Article P3.43.

[7] G. Kreweras and Y. Poupard, Sur les partitions en paires d’un ensemble fini totalement ordonné, Publications de l’Institut de Statistique de l’Université de Paris 23 (1978), 57–74.

[8] M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math. 180 (1998), 301– 313.

[9] V. Pilaud and J. Rué, Analytic combinatorics of chord and hyperchord diagrams with k crossings, Adv. Appl. Math. 57 (2014), 60–100

[10] J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp. 29 (1975), 215–222.

[11] N. J. A. Sloane et al., The on-line encyclopedia of integer sequences, 2020. Available at

https://oeis.org.

[12] J. Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math. 4 (1952), 2–25.

[13] H. S. Wilf, Generatingfunctionology, Academic Press Inc., 1990.

[14] D. Young, The number of domino matchings in the game of memory, J. Integer Sequences 21 (2018), Article 18.8.1.

[15] D. Young, Generating functions for domino matchings in the 2 × k game of memory, J. Integer Sequences 22 (2019), Article 19.8.7.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05C70, 60C05. Keywords: chord diagram, perfect matching.

(Concerned with sequences \underline{A062993}, \underline{A091320}, \underline{A334056}, \underline{A334057}, \underline{A334058}, \underline{A334059}, \underline{A334060}, \underline{A334061}, \underline{A334062}, and \underline{A334063}.)

Received August 11 2020; revised versions received August 12 2020; September 29 2020. Published in Journal of Integer Sequences, October 13 2020.

Return to Journal of Integer Sequences home page.