Symmetric partitions and pairings

Ferenc Oravecz

1999

Abstract The lattice of partitions and the sublattice of non-crossing partitions of a finite set are important objects in combinatorics. In this paper another sublattice of the partitions is investigated, which is formed by the symmetric partitions. The measure whose nth moment is given by the number of non-crossing symmetric partitions of n elements is determined explicitly, just as the ”symmetric” analogue of the free Poisson law.

1. Preliminaries

For a linearly ordered set S, π = {V_{1}, V_{2}, …, V_{p}} is a partition of S if the V_{i} (non empty) sets are pairwise disjoint and the union of them is S. The sets V_{i} are called the blocks of the partition. We call the partition π crossing if in π there are two blocks V_{i} and V_{j} (i ≠ j) and elements v_{1}, v_{2} ∈ V_{i}, w_{1}, w_{2} ∈ V_{j} such that v_{1} < w_{1} < v_{2} < w_{2}. Otherwise a partition is called non-crossing. A partition π of S is called pair-partition or pairing if every block of π contains exactly two elements of S. Of course the number of elements in S must be even if S admits such a partition.

It is well known (and can be verified easily) that the number of partitions of a set of n elements is given by the nth Bell number B_{n} satisfying

B_{0} = 1,
B_{n+1} = ∑_{k=0}^{n} \binom{n}{k}B_{k},

while the number of pair-partitions of a set of 2n elements is \frac{(2n)!}{2^{n}n!} (see [2] for example).

An interesting fact about the non-crossing partitions is that the number of non-crossing partitions of a set of n elements equals the number of noncrossing pair-partitions of a set of 2n elements, being the nth Catalan number c_{k} = \frac{1}{n+1} \binom{2n}{n} (see [4] and [6] ).

One can define a partial order structure on the set of partitions (or noncrossing partitions) of an n element set in the following way: let π_{1} ≤ π_{2} if and only if each block of π_{1} is contained in a block of π_{2}. With this order both the set of all partitions and the set of non-crossing partitions of an n element set becomes a lattice (see [4] and [2]).

It is also interesting to see the connection between the number of certain partitions and certain probability distributions. The most important examples are the following. It is easy to check that the nth moment of the standard Gaussian law is given by the number of pair-partitions of a set of n elements. On the other hand, the number of non-crossing pair-partitions of a set of n elements give the nth moment of the standard Wigner law (it is also called the semicircle law), which is the analogue of the Gaussian law in free probability theory (see e.g. [3]). The nth moment of a Poisson law of mean λ is a polynomial of λ in which the coefficient of λ^{i} is the number of all partitions of a set of n elements into i blocks. Again, taking the polynomial of λ in which the coefficient of λ^{i} is the number of non-crossing partitions of a set of n elements into i blocks, we get the nth moment of the Marchenko-Pastur distribution, which from many points of view is the free analogue of the Poisson law (see [5]).

2. Combinatorial Results

In this paper we examine another special type of partitions which are given by the following

Definition 2.1. A partition π of the linearly ordered set S = {s_{1}, s_{2}, …, s_{n}} is symmetric, if whenever s_{i} and s_{j} are in the same block, then so are s_{n+1−i} and s_{n+1−j}.

The reason to call these partitions symmetric is that in their linear representation (where instead of S we take the set {1, 2, …, n} of the real line, and the blocks of π are represented by ”bridges” connecting the elements of the same blocks) is symmetric to its center, or (which means the same) inverting the order in S the linear representation does not change. In Fig.

1. one can see the linear representation of π_{1} = {{1, 4} , {2} , {3, 5, 6}} and π_{2} = {{1, 6} , {2, 3} , {4, 5}} of {1, 2, 3, 4, 5, 6}, the latter being symmetric.

∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘
π_{1} π_{2}
F ig. 1.

Note that from the linear representation of a partition it can also be seen immediately weather it is crossing or non-crossing. If it is possible to draw the bridges corresponding to the blocks without crossing each-other, then the corresponding partition is non-crossing (as for example π_{2} of Fig. 1.), while if it is not possible, the partition is crossing (as for example π_{1} of Fig. 1.). It is also easy to see from the linear representation weather the given partition is a pairing, as for example π_{2} of Fig. 1.

Note that just as in the case of all (non-crossing) partitions, both the set of all symmetric partitions and the set of non-crossing symmetric partitions of an n element set form a lattice with respect to the usual partial order ≤ of partitions.

Proposition 2.1. Both the number of non-crossing symmetric partitions of a set of n elements and the number of non-crossing symmetric pair-partitions of a set of 2n elements is \binom{n}{[\frac{n}{2}]} (the numbers in the center of the Pascal triangle).

Proof. Let A_{n} denote the number of non-crossing symmetric partitions of n elements. First we show that for the sequence {A_{n}} the following recursion holds

A_{2l+1} = 2A_{2l} − c_{l}  for l = 0, 1, 2, …
A_{2l+2} = 2A_{2l+1} for l = 0, 1, 2, …,

where c_{l} is the lth Catalan number (being the number of all non-crossing partitions of l elements), with A_{0} = c_{0} = 1.

Taking any non-crossing symmetric partition π of S_{0} = {1, 2, …, l, l + 2, …, 2l + 1}, π̃ = π ∪ {{l + 1}} is a non-crossing symmetric partition of S = {1, 2, …, 2l + 1}. Starting from different partitions of S_{0} we clearly get different partitions of S. This way we get A_{2l} non-crossing symmetric partition of S.

We get different - still symmetric and non-crossing - partitions of S if we define the inserted central element l + 1 the member of that block which contains the biggest element i_{0} ≤ l together with its ”symmetric pair” 2l + 1 − i_{0}. The only case when such a block does not exist is when every element of any block is in the same half of the set, and as in this case the partition of the first l elements define the partition of the last l elements (because of the requirement of symmetry), the number of these cases is c_{l}, the number of non-crossing partitions of l elements. This gives another A_{2l} − c_{l} partitions, as starting from different partitions of S_{0} we clearly get different partitions of S again. It is also clear, that this A_{2l} − c_{l} partitions differ from the A_{2l} ones obtained before; to check this it is enough to take the block of the central element.

What is left is to show that any symmetric non-crossing partition of S can be obtained by one of this two methods. For this let us take any non-crossing symmetric partition ν of S. The element l + 1 can either form a block by itself, or can be the center element of a block which contains both smaller and greater elements, in a symmetric arrangement. In the first case it is clear that the partition ν can be obtained by the first method from the partition ν_{0} = ν \{l + 1} of S_{0}. In the second case, as the partition is non-crossing, the block which contains the biggest element i_{0} ≤ l together with its ”symmetric pair” 2l + 1 − i_{0} is the block of the central element. So now the partition ν can be obtained by the second method from the partition of S_{0} which occur by eliminating the central element from its block (and from the set itself).

Now starting from any non-crossing symmetric partition of 2l+1 elements, we can obtain a non-crossing symmetric partition of 2l + 2 elements in two different ways again. Duplicating the central element (s_{l+1}), we can define them in the same block or in different ones. (In the first case the number of blocks does not change, while in the second case it increases by one.) Starting from different partitions both procedures give different partitions of the obtained 2l + 2 elements, and of course the two methods can never give the same partition; to check this it is enough to take the block(s) of the two central elements.

We show that any symmetric non-crossing partition of 2l+2 elements can be obtained by one of this two methods. For this let us take any non-crossing symmetric partition η of a set of 2l + 2 elements. The elements s_{l+1} and s_{l+2} can be either in the same block or in different ones. In the first case it is clear that the partition η can be obtained by the first method from the partition η_{0} of 2l + 1 elements which occur by fusing the elements s_{l+1} and s_{l+2}. In the second case the partition η can be obtained from the same partition η_{0} of 2l + 1 elements by the second method.

The fact that the sequence \binom{n}{[\frac{n}{2}]} satisfies the same recursion with the same starting element can be verified directly.

For the second part of the statement we recall a well known natural bijection between the set of non-crossing partitions of n elements and the set of non-crossing pair-partitions of 2n elements. Let π = {V_{1}, V_{2}, …, V_{k}} be a non-crossing partition of S = {s_{1}, s_{2}, …, s_{n}} . Let Ŝ be the ordered set {s_{1}^{−}, s_{1}^{+}, s_{2}^{−}, s_{2}^{+}, …, s_{n}^{−}, s_{n}^{+}} , and let π̂ be the partition whose blocks are defined in the following way: whenever V_{i} = {s_{i_{1}}, s_{i_{2}}, …, s_{i_{m}}} ∈ π, let {s_{i_{1}}^{−}, s_{i_{m}}^{+}} , {s_{i_{1}}^{+}, s_{i_{2}}^{−}} , {s_{i_{2}}^{+}, s_{i_{3}}^{−}} , …, {s_{i_{m−1}}^{+}, s_{i_{m}}^{−}} ∈ π̂. (For an example see Fig 2.) It is obvious that this map preserves symmetricity, which completes the proof. □

_{s_{1}}^{∘} _{s_{2}}^{∘} _{s_{3}}^{∘} _{s_{4}}^{∘} _{s_{5}}^{∘} _{s_{6}}^{∘} _{s_{7}}^{∘}  ⟷ _{s_{1}^{−}}^{∘} _{s_{1}^{+}}^{∘} _{s_{2}^{−}}^{∘} _{s_{2}^{+}}^{∘} _{s_{3}^{−}}^{∘} _{s_{3}^{+}}^{∘} _{s_{4}^{−}}^{∘} _{s_{4}^{+}}^{∘} _{s_{5}^{−}}^{∘} _{s_{5}^{+}}^{∘} _{s_{6}^{−}}^{∘} _{s_{6}^{+}}^{∘} _{s_{7}^{−}}^{∘} _{s_{7}^{+}}^{∘}
F ig. 2.

We note, that for the number of all symmetric partitions and all symmetric pair-partitions we could not find any useful expressions apart from obvious recurrences.

3. Solution of the moment problem in the case of symmetric partitions

In this part we consider the question weather the sequence of numbers of certain symmetric partitions of n elements (n = 0, 1, 2, …) can be obtained as the moment sequence of some probability measure μ.

Theorem 3.1. The moment sequence of the probability distribution

μ = \frac{1}{2π} \sqrt{\frac{2 + x}{2 − x}}χ(x)dx,

where χ stands for the characteristic function of the interval [−2, 2], is {A_{n}}_{n∈N}, that is the sequence of numbers of all non-crossing symmetric partitions of n elements ( n = 0, 1, 2, …).

Proof. Let us denote the nth moment of the measure μ by m_{n}. Integration by parts gives

m_{2l} = \frac{1}{2π} ∫_{−2}^{2} x^{2l}\sqrt{\frac{2 + x}{2 − x}}dx = \frac{1}{2π} [2π4^{l} − 4l ∫_{−2}^{2} x^{2l−1} arcsin(\frac{x}{2})dx] and

m_{2l+1} = \frac{1}{2π} ∫_{−2}^{2} x^{2l+1}\sqrt{\frac{2 + x}{2 − x}}dx = \frac{1}{2π} (2l + 1) ∫_{−2}^{2} x^{2l}\sqrt{4 − x^{2}}dx.

Another integration by parts - applied to the expression obtained for m_{2l} - gives m_{2l} = 2m_{2l−1}. (In the integral we recognize the above forms of m_{2l} and m_{2l−1}, leading to m_{2l} = 4lm_{2l−1} − (2l − 1) m_{2l}, which yields the given result.) In a similar manner, integration by parts applied to the expression obtained for m_{2l+1} gives m_{2l+1} = \frac{2l+1}{l+1}m_{2l}. m_{0} and m_{1} can be computed directly; one gets m_{0} = 1 and m_{1} = 1. The fact that the sequence \binom{n}{[\frac{n}{2}]} satisfies the same recursions with the same starting element can be verified directly, which completes the proof.□

Remark 3.2. The constructive way to obtain the measure μ is via its moment generating series. The moment generating series defined by the numbers A_{n} is

M(x) = ∑_{n=0}^{∞} A_{n}x^{n} = ∑_{k=0}^{∞} A_{2k}x^{2k} + ∑_{k=0}^{∞} A_{2k+1}x^{2k+1}

Applying the recursions A_{2k} = 2A_{2k−1} and A_{2k+1} = 2A_{2k} − c_{k} one gets

M(x) = \frac{1 − xW (x)}{1 − 2x},

where W (x) stands for the moment generating series ∑_{n=0}^{∞} c_{n}x^{2n} of the standard Wigner law :

W (x) = \frac{1 − \sqrt{1 − 4x^{2}}}{2x^{2}}

(see e.g. [3]). Solving the above equation for M(x) one gets

M(x) = \frac{2x + \sqrt{1 − 4x^{2}} − 1}{2x − 4x^{2}},

which gives the Cauchy transform of the corresponding probability measure:

G(z) = \frac{1}{z}M(\frac{1}{z}) = \frac{1}{2} [\sqrt{\frac{z + 2}{z − 2}} − 1] .

According to the Stieltjes inversion formula this determines the corresponding measure

\frac{μ}{dx} = lim_{y↓0} [−\frac{1}{π} Im G(x + iy)] = \frac{1}{2π} \sqrt{\frac{2 + x}{2 − x}}χ(x).

From these results one can check that

G (z) = \frac{1}{z − 1 − G_{w} (z)},

where

G_{w} (z) = \frac{z − \sqrt{z^{2} − 4}}{2}

is the Cauchy transform of the standard Wigner law, having the continued fraction form

G_{w} (z) = \frac{1}{z − \frac{1}{z − \frac{1}{...}}}

(see e.g. [3]), so we obtain

G (z) = \frac{1}{z − 1 − \frac{1}{z − \frac{1}{z − \frac{1}{...}}}} ,

which in turn gives the orthogonal polynomials for μ defined by

P_{0} (x) = 1,
P_{1} (x) = x − 1,
xP_{n} (x) = P_{n+1} (x) + P_{n−1} (x)  (n ≥ 1).

We note, that there is no such probability distribution for which the moment sequence equals the sequence of numbers of (non-crossing) symmetric pair-partitions of n elements (n = 0, 1, 2, …). The necessary criteria for a sequence of numbers {a_{i}}_{i=0,1,2...} to be the moment sequence of some probability measure is that the determinant

| \begin{matrix}a_{0} & a_{1} & … & a_{k} \\ a_{1} & a_{2} & … & a_{k−1} \\ . & . & . & . \\ a_{k} & a_{k+1} & … & a_{2k} \end{matrix} |

must be non-negative for every k = 0, 1, 2, … (see e.g. [1]). Calculating the corresponding 4×4 determinants we get negative numbers in both (crossingand non-crossing) cases. (In the non-crossing case the same follows from the fact that for the probability measure μ of Theorem 3.1. suppμ ⫅̸ [0, ∞).)

Theorem 3.3. The moment sequence of the probability distribution of parameter λ ( λ > 0)

μ_{λ} = \{ \begin{matrix}\frac{1}{2π} \sqrt{\frac{(1+λ)+x}{(1+λ)−x}(1 − \frac{(1−λ)^{2}}{x^{2}} )}χ(x)dx if λ ≥ 1 \\ (1 − λ)δ_{0} + \frac{1}{2π} \sqrt{\frac{(1+λ)+x}{(1+λ)−x}(1 − \frac{(1−λ)^{2}}{x^{2}} )}χ̃(x)dx if λ < 1 \end{matrix} ,

where χ stands for the characteristic function of the set [−1 − λ, 1 − λ] ∪ [−1 + λ, 1 + λ] and χ̃ stands for the characteristic function of the set [−1 − λ, −1 + λ] ∪ [1 − λ, 1 + λ] is given by

m_{n}^{(λ)} = ∑_{i=1}^{n} A_{n}^{(i)}λ^{i},

where A_{n}^{(i)} means the number of non-crossing symmetric partitions of a set of n elements into i blocks.

Proof. First one have to derive a recursive formula for the numbers A_{n}^{(i)}. This can be done following the ideas of the proof of proposition 2.1., arriving to

A_{0}^{(0)} = A_{n}^{(1)} = A_{n}^{(n)} = 1 if n ≥ 1,
A_{n}^{(k)} = 0 if 0 ≤ n < k or k = 0 < n,
A_{2n+1}^{(2k)} = A_{2n}^{(2k−1)} + A_{2n}^{(2k)} − Q_{n}^{(k)} for 1 ≤ k ≤ n,
A_{n}^{(k)} = A_{n−1}^{(k−1)} + A_{n−1}^{(k)} if 1 ≤ k ≤ n and (n is even or k is odd).

where Q_{n}^{(k)} means the number of non-crossing partitions of a set of n elements into k blocks.

From these one easily gets the following recursion for the moments:

m_{2n}^{(λ)} = (1 + λ)m_{2n−1}^{(λ)} for n = 1, 2, 3, … and
m_{2n+1}^{(λ)} = (1 + λ)m_{2n}^{(λ)} − m̃_{n}^{(λ)} for n = 0, 1, 2, … with
m_{0}^{(λ)} = 1,

where m̃_{n}^{(λ)} means the nth moment of the free Poisson law of parameter λ^{2} (see [5], that is

m̃_{n}^{(λ)} = ∑_{i=1}^{n} Q_{n}^{(i)}λ^{2i}.

For the moment generating series defined by the numbers m_{n}^{(λ)} one gets

M_{λ}(x) = ∑_{n=0}^{∞} m_{n}^{(λ)}x^{n} = ∑_{k=0}^{∞} m_{2k}^{(λ)}x^{2k} + ∑_{k=0}^{∞} m_{2k+1}^{(λ)}x^{2k+1}.

(The moment generating series of the free Poisson law or the classical Poisson law of parameter λ clearly majorate this power series. As those series are absolute convergent for sufficiently small values of x, the same holds for M_{λ}(x).)

Applying the above recursions, changing to the Cauchy transform

G_{λ}(z) = \frac{1}{z}M_{λ} (\frac{1}{z})

and using the known fact that the Cauchy transform of the free Poisson law of parameter λ^{2} is

G̃_{λ^{2}}(z) = \frac{z + (1 − λ^{2}) − \sqrt{(z − 1 − λ^{2})^{2} − 4λ^{2}}}{2z}

(see e.g. [3] or [7]) one gets

G_{λ}(z) = \frac{1}{2} [\frac{1 − λ}{z} − 1 + \sqrt{\frac{z + (1 + λ)}{z − (1 + λ)} (1 − \frac{(1 − λ)^{2}}{z^{2}} )}] .

Applying the Stieltjes inversion formula, after some easy calculation one gets μ_{λ} as stated above.□

Remark 3.4. Note that if λ = 1, μ_{λ} coincides with the probability distribution μ given in proposition 3.1.

Calculating the orthogonal polynomials for μ_{λ} one gets

P_{0} (x) = 1,
P_{1} (x) = x − λ,
xP_{n} (x) = P_{n+1} (x) + (−1)^{n} (λ − 1) P_{n} (x) + λP_{n−1} (x)  (n ≥ 1).

This can be shown by verifying the equality

G_{λ} (z) = \frac{1}{z − λ − F (z)},

where F (z) is defined by the formula

F (z) = \frac{λ}{z + (λ − 1) − \frac{λ}{z − (λ − 1) − F (z)}} .

(Computation was carried out by MAPLE.)

The probability measure μ_{λ} given in proposition 3.3. can be considered as the ”symmetric analogue” of the free Poisson law of mean λ. We have seen that the ”symmetric analogue” of the Wigner law and that of the Gaussian law do not exist (as probability distributions). Finally we have to mention that we could not derive the ”symmetric analogue” of the Poisson law of mean λ (for which the nth moment would be a polynomial of λ in which the coefficient of λ^{i} is the number of all symmetric partitions of a set of n elements into i blocks), neither could we prove that it does not exist.

References

[1] N. I. Akhiezer, Klassitsekaya Problema Momentov, Gasudarstvennoe Izdatelstvo Fiziko-matematitseskoy Literaturi, Moscow, 1961.

[2] G. E. Andrews, The Theory of Partitions, Addison-Wesley Publishing Co., 1976.

[3] F. Hiai, D. Petz, The semi-circle law, free random variables and entropy, preprint.

[4] G. Kreweras, Sur les partitions non-croisées d’un cycle, Discrete Math. 1 (1972), 333-350.

[5] F. Oravecz, D. Petz, On the eigenvalue distribution of some symmetric random matrices, Acta Sci. Math. 63 (1997), 383-395.

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

[7] D. Voiculescu, K. Dykema and A. Nica, Free Random Variables, CRM Monograph Series, vol.1, American Mathematical Society, Providence, RI, 1992.

Ferenc Oravecz Rényi Alfréd Institute of Mathematics, Hungarian Academy of Sciences Reáltanoda u. 13-15 H-1053, Budapest, Hungary

e-mail: oravecz@math-inst.hu

Supported by OTKA T016924

2000 Mathematics Subject Classification: 60E10, 05A18