SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

Open Access Research

Closed expressions for averages of set partition statistics

Bobbie Chern1, Persi Diaconis2, Daniel M Kane3 and Robert C Rhoades4*

Author Affiliations

1 Department of Electrical Engineering, Stanford University, Stanford, CA 94305, USA

2 Department of Mathematics and Statistics, Sequoia Hall, 390 Serra Mall, Stanford University, Stanford, CA 94305, USA

3 Department of Mathematics, Bldg 380, Stanford University, Stanford, CA 94305, USA

4 Center for Communications Research, 805 Bunn Dr., Princeton, NJ 08540, USA

For all author emails, please log on.

Research in the Mathematical Sciences 2014, 1:2  doi:10.1186/2197-9847-1-2


The electronic version of this article is the complete one and can be found online at:


Received:17 January 2014
Accepted:7 February 2014
Published:17 June 2014

© 2014 Chern et al.; licensee Springer.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly credited.

Abstract

In studying the enumerative theory of super characters of the group of upper triangular matrices over a finite field, we found that the moments (mean, variance, and higher moments) of novel statistics on set partitions of [n]={1,2,⋯,n} have simple closed expressions as linear combinations of shifted bell numbers. It is shown here that families of other statistics have similar moments. The coefficients in the linear combinations are polynomials in n. This allows exact enumeration of the moments for small n to determine exact formulae for all n.

Background

The set partitions of [ n]={1,2,⋯,n} (denoted Π(n)) are a classical object of combinatorics. In studying the character theory of upper triangular matrices (see section ‘Set partitions, enumerative group theory, and super characters’ for background) we were led to some unusual statistics on set partitions. For a set partition λ of n, consider the dimension exponent (Table 1).

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M1">View MathML</a>

where λ has blocks, Mi and mi are the largest and smallest elements of the ith block. How does d(λ) vary with λ? As shown below, its mean and second moment are determined in terms of the Bell numbers Bn

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M2">View MathML</a>

Table 1. A table of the dimension exponent f (n ,0, d )

The right hand sides of these formulae are linear combinations of Bell numbers with polynomial coefficients. Dividing by Bn and using asymptotics for Bell numbers (see section ‘Asymptotic analysis’) in terms of αn, the positive real solution of ueu=n+1 (so αn= log(n)− log log(n)+⋯) gives

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M3">View MathML</a>

This paper gives a large family of statistics that admit similar formulae for all moments. These include classical statistics such as the number of blocks and number of blocks of size i. It also includes many novel statistics such as d(λ) and ck(λ), the number of k crossings. The number of two crossings appears as the intertwining exponent of super characters.

Careful definitions and statements of our main results are in section ‘Statement of the main results’. Section ‘Set partitions, enumerative group theory, and super characters’ reviews the enumerative and probabilistic theory of set partitions, finite groups, and super characters. Section ‘Computational results’ gives computational results; determining the coefficients in shifted Bell expressions involves summing over all set partitions for small n. For some statistics, a fast new algorithm speeds things up. Proofs of the main theorems are in sections ‘Proofs of recursions, asymptotics, and Theorem 3’ and ‘Proofs of Theorems 1 and 2’. Section ‘More data’ gives a collection of examples - moments of order up to six for d(λ) and further numerical data. In a companion paper [1], the asymptotic limiting normality of d(λ), c2(λ), and some other statistics is shown.

Statement of the main results

Let Π(n) be the set partitions of [n]={1,2,⋯,n} (so |Π(n)|=Bn, the nth Bell number). A variety of codings are described in section ‘Set partitions, enumerative group theory, and super characters’. In this section, λΠ(n) is described as λ=B1|B2|⋯|B with BiBj=, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M4">View MathML</a>. Write iλj if i and j are in the same block of λ. It is notationally convenient to think of each block as being ordered. Let First (λ) be the set of elements of [n] which appear first in their block and Last(λ) be the set of elements of [n] which occur last in their block. Finally, let Arc(λ) be the set of distinct pairs of integers (i,j) which occur in the same block of λ such that j is the smallest element of the block greater than i. As usual, λ may be pictured as a graph with vertex set [n] and edge set Arc(λ).

For example, the partition λ=1356|27|4, represented in Figure 1, has First(λ)={1,2,4}, Last(λ)={6,7,4}, and Arc(λ)={(1,3),(3,5),(5,6),(2,7)}.

thumbnailFigure 1. An example partition λ =1356|27|4.

A statistic on λ is defined by counting the number of occurrences of patterns. This requires some notation.

Definition1

(i) A pattern <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M5">View MathML</a> of length k is defined by a set partition P of [k] and subsets <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M6">View MathML</a>, and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M7">View MathML</a>. Let <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M8">View MathML</a>.

(ii) An occurrence of a pattern <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M9">View MathML</a> of length k in λΠ(n) is s=(x1,⋯,xk) with xi∈[ n] such that

1. x1<x2<⋯<xk.

2. xiλxj if and only if iPj.

3. xiFirst(λ) if <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M10">View MathML</a>.

4. xiLast(λ) if <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M11">View MathML</a>.

5. (xi,xj)∈Arc(λ) if <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M12">View MathML</a>.

6. xjxi=1 if <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M13">View MathML</a>.

Write <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M14">View MathML</a> if s is an occurrence of <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M15">View MathML</a> in λ.

(iii) A simple statistic is defined by a pattern <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M16">View MathML</a> of length k and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M17">View MathML</a>. If λΠ(n) and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M18">View MathML</a>, write <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M19">View MathML</a>. Let

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M20">View MathML</a>

Let the degree of a simple statistic <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M21">View MathML</a> be the sum of the length of <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M22">View MathML</a> and the degree of Q.

(iv) A statistic is a finite<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M23">View MathML</a>-linear combination of simple statistics. The degree of a statistic is defined to be the minimum over such representations of the maximum degree of any appearing simple statistic.

Remark1

In the notation above, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M24">View MathML</a> is the set of firsts elements, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M25">View MathML</a> is the set of lasts, A is the arc set of the pattern, and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M26">View MathML</a> is the set of consecutive elements.

Examples

1. Number of blocks in λ:

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M27">View MathML</a>

Here, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M28">View MathML</a> is a pattern of length 1, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M29">View MathML</a>, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M30">View MathML</a>, and Q(y,m)=1. Similarly, the nth moment of (λ) can be computed using

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M31">View MathML</a>

where <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M32">View MathML</a> is the pattern of length k corresponding to P, the partition of [k] into blocks of size 1, with <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M33">View MathML</a>, and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M34">View MathML</a>.

2. Number of blocks of size i: define a pattern <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M35">View MathML</a> of length i by: (1) all elements of [i] are equivalent, (2) <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M36">View MathML</a>, (3) <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M37">View MathML</a>, (4) <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M38','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M38">View MathML</a>, and (5) <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M39">View MathML</a>. Then,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M40">View MathML</a>

(1)

is the number of i blocks in λ (if i=1, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M41">View MathML</a>). Similarly, the moments of the number of blocks of size i is a statistic. See Theorem 1.

3. k crossings: a k crossing [2] of a λΠ(n) is a sequence of arcs (it,jt)1≤tkArc(λ) with

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M42','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M42">View MathML</a>

The statistic crk(λ) which counts the number of k crossings of λ can be represented by a pattern <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M43','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M43">View MathML</a> of length 2k with (1) iPk+i for i=1,⋯,k, (2) <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M44','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M44">View MathML</a>, (3) <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M45','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M45">View MathML</a>, and (4) <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M46','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M46">View MathML</a>.

Partitions with cr2(λ)=0 are in bijection with Dyck paths and so are counted by the Catalan numbers <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M47','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M47">View MathML</a> (see Stanley’s second volume on enumerative combinatorics [3]). Partitions without crossings have proved themselves to be very interesting.

Crossing seems to have been introduced by Krewaras [4]. See Simion’s [5] for an extensive survey and Chen et al. [2] and Marberg [6] for more recent appearances of this statistic. The statistic cr2(λ) appears as the intersection exponent in section ‘Super character theory’.

4. Dimension exponent: the dimension exponent described in the introduction is a linear combination of the number of blocks (a simple statistic of degree 1), the last elements of the blocks (a simple statistic of degree 2), and the first elements of the blocks (a simple statistic of degree 2). Precisely, define <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M48','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M48">View MathML</a> where <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M49','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M49">View MathML</a> is the pattern of length 1, with <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M50">View MathML</a>, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M51','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M51">View MathML</a>, and Q(y,m)=y. Similarly, let <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M52','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M52">View MathML</a> where <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M53','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M53">View MathML</a> is the pattern of length 1, with <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M54','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M54">View MathML</a>, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M55','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M55">View MathML</a>, and Q(y,m)=y. Then,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M56','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M56">View MathML</a>

5. Levels: the number of levels in λ, denoted flevels(λ), (see page 383 of [7] or Shattuck [8]) is the number of i such that i and i+1 appear in the same block of λ. We have

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M57','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M57">View MathML</a>

where <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M58','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M58">View MathML</a> is a pattern of length 2 with <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M59','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M59">View MathML</a>, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M60','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M60">View MathML</a>, and Q=1.

6. The maximum block size of a partition is not a statistic in this notation.

The set of all statistics on <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M61','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M61">View MathML</a> is a filtered algebra.

Theorem1.

Let be the set of all set partition statistics thought of as functions <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M63','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M63">View MathML</a>. Then is closed under the operations of pointwise scaling, addition and multiplication. In particular, if <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M65">View MathML</a> and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M66','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M66">View MathML</a>, then there exist partition statistics ga,g+,g so that for all set partitions λ,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M67">View MathML</a>

Furthermore, deg(ga)≤ deg(f1), deg(g+)≤ max(deg(f1), deg(f2)), and deg(g)≤ deg(f1)+ deg(f2). In particular, is a filtered<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M69','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M69">View MathML</a>-algebra under these operations.

Remark2.

Properties of this algebra remain to be discovered.

Definition2.

A shifted Bell polynomial is any function <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M70','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M70">View MathML</a> that is zero or can be expressed in the form

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M71','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M71">View MathML</a>

where <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M72','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M72">View MathML</a> and each <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M73','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M73">View MathML</a> such that QI(x)≠0 and QK(x)≠0. i.e., it is a finite sum of polynomials multiplied by shifted Bell numbers. Call K the upper shift degree of R and I the lower shift degree of R.

Remark3.

The representation of a shifted Bell polynomial is unique. This can be understood by considering the asymptotics of each individual term as n.

Our first main theorem shows that the aggregate of a statistic is a shifted Bell polynomial.

Theorem2.

For any statistic, f of degree N, there exists a shifted Bell polynomial R such that for all n≥1

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M74','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M74">View MathML</a>

Moreover,

1. the upper shift index of R is at most N and the lower shift index is bounded below by −k, where k is the length of the pattern associated f.

2. the degree of the polynomial coefficient of Bn+Nj in R is bounded by j for jN and by j−1 for j>N.

The following collects the shifted Bell polynomials for the aggregates of the statistics given previously.

Examples

1. Number of blocks in λ:

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M75','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M75">View MathML</a>

This is elementary and is established in Proposition 1

2. Number of blocks of size i:

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M76">View MathML</a>

This is also elementary and is established in Proposition 1.

3. Two crossings: Kasraoui [9] established

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M77','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M77">View MathML</a>

4. Dimension exponent:

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M78','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M78">View MathML</a>

This is given in Theorem 1.

5. Levels: Shattuck [8] showed that

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M79','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M79">View MathML</a>

It is amusing that this implies that B3nB3n+1≡1 (mod 2) and B3n+2≡0 (mod 2) for all n≥0.

Remark4.

Chapter 8 of Mansour’s book [7] and the research papers [9-11] contain many other examples of statistics which have shifted Bell polynomial aggregates. We believe that each of these statistics is covered by our class of statistics.

Set partitions, enumerative group theory, and super characters

This section presents background and a literature review of set partitions, probabilistic and enumerative group theory, and super character theory for the upper triangular group over a finite field. Some sharpenings of our general theory are given.

Set partitions

Let Π(n,k) denote the set partitions of n labeled objects with k blocks and Π(n)=∪kΠ(n,k); so |Π(n,k)|=S(n,k) is the Stirling number of the second kind and |Π(n)|=Bn is the nth Bell number. The enumerative theory and applications of these basic objects is developed in the studies of Graham et al. [12], Knuth [13], Mansour [7], and Stanley [14]. There are many familiar equivalent codings.

● Equivalence relations on n objects

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M80">View MathML</a>

● Binary, strictly upper triangular zero-one matrices with no two ones in the same row or column (equivalently, rook placements on a triangular Ferris board (Riordan [15]).

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M81','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M81">View MathML</a>

● Arcs on n points

● Restricted growth sequences a1,a2,…,an; a1=0,aj+1≤1+ max(a1,…,aj) for 1≤j<n (Knuth [13], p. 416)

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M82','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M82">View MathML</a>

● Semi-labeled trees on n+1 vertices

● Vacillating tableau: a sequence of partitions λ0,λ1,⋯,λ2n with λ0=λ2n= and λ2i+1 is obtained from λ2i by doing nothing or deleting a square and λ2i is obtained from λ2i−1 by doing nothing or adding a square (see [2]).

The enumerative theory of set partitions begins with Bell polynomials. Let <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M85','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M85">View MathML</a> with Xi(λ) the number of blocks in λ of size i; so set <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M86">View MathML</a> and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M87','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M87">View MathML</a> A classical version of the exponential formula gives

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M88','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M88">View MathML</a>

(2)

These elegant formulae have been used by physicists and chemists to understand fragmentation processes ([16] for extensive references). They also underlie the theory of polynomials of binomial type [17,18], that is, families Pn(x) of polynomials satisfying

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M89','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M89">View MathML</a>

These unify many combinatorial identities, going back to Faa de Bruno’s formula for the Taylor series of the composition of two power series.

There is a healthy algebraic theory of set partitions. The partition algebra of [19] is based on a natural product on Π(n) which first arose in diagonalizing the transfer matrix for the Potts model of statistical physics. The set of all set partitions <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M90','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M90">View MathML</a> has a Hopf algebra structure which is a general object of study in [20].

Crossings and nestings of set partitions is an emerging topic, see [2,21,22] and their references. Given λΠ(n) two arcs (i1,j1) and (i2,j2) are said to cross if i1<i2<j1<j2 and nest if i1<i2<j2<j1. Let cr(λ) and ne(λ) be the number of crossings and nestings. One striking result: the crossings and nestings are equi-distributed ([21] Corollary 1.5), they show

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M91','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M91">View MathML</a>

As explained in section ‘Super character theory’, crossings arise in a group theoretic context and are covered by our main theorem. Nestings are also a statistic.

This crossing and nesting literature develops a parallel theory for crossings and nestings of perfect matchings (set partitions with all blocks of size 2). Preliminary works suggest that our main theorem carry over to matchings with Bn reduced to (2n)!/2nn!.

Turn next to the probabilistic side: what does a ‘typical’ set partition ‘look like’? For example, under the uniform distribution on Π(n)

● What is the expected number of blocks?

● How many singletons (or blocks of size i) are there?

● What is the size of the largest block?

The Bell polynomials can be used to get moments. For example:

Proposition1.

(i) Let (λ) be the number of blocks. Then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M92">View MathML</a>

(ii) Let X1(λ) be the number of singleton blocks, then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M93">View MathML</a>

In accordance with our general theorem, the right hand sides of (i) and (ii) are shifted Bell polynomials. To make contact with the results shown previously, there is a direct proof of these classical formulae.

Proof.

Specializing the variables in the generating function (2) gives a two variable generating functions for :

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M94','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M94">View MathML</a>

Differentiating with respect to y and setting y=1 shows that m(;n) is the coefficient of <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M95','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M95">View MathML</a> in <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M96','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M96">View MathML</a>. Noting that

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M97','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M97">View MathML</a>

yields m()=Bn+1Bn. Repeated differentiation gives the higher moments.

For X1, specializing variables gives

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M98','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M98">View MathML</a>

Differentiation with respect to y and settings y=1 readily yields the claimed results.

The moment method may be used to derive limit theorems. An easier, more systematic method is due to Fristedt [23]. He interprets the factorization of the generating function B(t) in (2) as a conditional independence result and uses ‘dePoissonization’ to get results for finite n. Let Xi(λ) be the number of blocks of size i. Roughly, his results say that <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M99">View MathML</a> are asymptotically independent and of size (log(n))i/i!. More precisely, let αn satisfy <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M100','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M100">View MathML</a> (so αn= log(n)− log log(n)+o(1)). Let <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M101">View MathML</a> then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M102','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M102">View MathML</a>

where <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M103','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M103">View MathML</a> Fristedt also has a description of the joint distribution of the largest blocks.

Remark5.

It is typical to expand the asymptotics in terms of un where <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M104','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M104">View MathML</a>. In this notation, un and αn differ by O(1/n).

The number of blocks (λ) is asymptotically normal when standardized by its mean <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M105','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M105">View MathML</a> and variance <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M106','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M106">View MathML</a>. These are precisely given by Proposition 1. Refining this, Hwang [24] shows

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M107','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M107">View MathML</a>

Stam [25] has introduced a clever algorithm for random uniform sampling of set partitions in Π(n). He uses this to show that if W(i) is the size of the block containing i, 1≤ik, then for k finite and n large W(i) are asymptotically independent and normal with mean and variance asymptotic to αn. In [1], we use Stam’s algorithm to prove the asymptotic normality of d(λ) and cr2(λ).

Any of the codings previously mentioned lead to distribution questions. The upper triangular representation leads to the study of the dimension and crossing statistics, the arc representation suggests crossings, nestings, and even the number of arcs, i.e. n(λ). Restricted growth sequences suggest the number of zeros, the number of leading zeros, largest entry. See Mansour [7] for this and much more. Semi-labeled trees suggest the number of leaves, length of the longest path from root to leaf, and various measures of tree shape (e.g., max degree). Further probabilistic aspects of uniform set partitions can be found in [16,26].

Probabilistic group theory

One way to study a finite group G is to ask what ‘typical’ elements ‘look like’. This program was actively begun by Erdös and Turan [27-33] who focused on the symmetric group Sn. Pick a permutation σ of n at random and ask the following:

● How many cycles in σ? (about logn)

● What is the length of the longest cycle? (about 0.61n)

● How many fixed points in σ? (about 1)

● What is the order of σ? (roughly <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M108','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M108">View MathML</a>)

In these and many other cases, the questions are answered with much more precise limit theorems. A variety of other classes of groups have been studied. For finite groups of Lie type, see [34] for a survey and [35] for wide-ranging applications. For p groups, see [36].

One can also ask questions about ‘typical’ representations. For example, fix a conjugacy class C (e.g., transpositions in the symmetric group), what is the distribution of χρ(C) as ρ ranges over irreducible representations [34,37,38]. Here, two probability distributions are natural, the uniform distribution on ρ and the Plancherel measure (<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M109','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M109">View MathML</a> with dρ the dimension of ρ). Indeed, the behavior of the ‘shape’ of a random partition of n under the Plancherel measure for Sn is one of the most celebrated results in modern combinatorics. See Stanley’s study [39] for a survey with references to the work of Kerov and Vershik [40], Logan and Shepp [41], Baik et al. [42], and many others.

The previous discussion focuses on finite groups. The questions make sense for compact groups. For example, pick a random matrix from Haar measure on the unitary group Un and ask: what is the distribution of its eigenvalues? This leads to the very active subject of random matrix theory. We point to the wonderful monographs of Anderson et al. [43], and Forrester [44] which have extensive surveys.

Super character theory

Let Gn(q) be the group of n×n matrices which are upper triangular with ones on the diagonal over the field <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M110','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M110">View MathML</a>. The group Gn(q) is the Sylow p subgroup of <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M111','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M111">View MathML</a> for q=pa. Describing the irreducible characters of Gn(q) is a well-known wild problem. However, certain unions of conjugacy classes, called superclasses, and certain characters, called supercharacters, have an elegant theory. In fact, the theory is rich enough to provide enough understanding of the Fourier analysis on the group to solve certain problems, see the work of Arias-Castro et al. [45]. These superclasses and supercharacters were developed by André [46-48] and Yan [49]. Supercharacter theory is a growing subject. See [6,50-54] and their references.

For the groups Gn(q), the supercharacters are determined by a set partition of [ n] and a map from the set partition to the group <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M112','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M112">View MathML</a>. In the analysis of these characters, there are two important statistics, each of which only depends on the set partition. The dimension exponent is denoted d(λ), and the intertwining exponent is denoted i(λ).

Indeed, if χλ and χμ are two supercharacters, then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M113','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M113">View MathML</a>

While d(λ) and i(λ) were originally defined in terms of the upper triangular representation (for example, d(λ) is the sum of the horizontal distance from the ‘ones’ to the super diagonal), their definitions can be given in terms of blocks or arcs:

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M114','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M114">View MathML</a>

(3)

and

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M115','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M115">View MathML</a>

(4)

Remark6.

Notice that i(λ)=cr2(λ) is the number of two crossings which were introduced in the previous sections.

Our main theorem shows that there are explicit formulae for every moment of these statistics. The following represents a sharpening using special properties of the dimension exponent.

Theorem3.

For each k∈{0,1,2,⋯ }, there exists a closed form expression

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M116','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M116">View MathML</a>

where each Pk,2kj is a polynomial with rational coefficients. Moreover, the degree of Pk,2kj is

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M117','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M117">View MathML</a>

For example,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M118','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M118">View MathML</a>

Remark7.

See section ‘More data’ for the moments with k≤6, and see [55] for the moments with k≤22. The first moment may be deduced easily from results of Bergeron and Thiem [56]. Note that they seem to have an index which differs by one from ours.

Remark8.

Theorem 3 is stronger than what is obtained directly from Theorem 2. For example, the lower shift index is 0, while the best that can be obtained from Theorem 2 is a lower shift index of −k. This theorem is proved by working directly with the generating function for a generalized statistic on ‘marked set partitions’. These set partitions are introduced in section ‘Computational results’.

Asymptotics for the Bell numbers yield the following asymptotics for the moments. The following result gives some asymptotic information about these moments.

Theorem4.

Let αn= log(n)− log log(n)+o(1)be the positive real solution of ueu=n+1. Then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M119','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M119">View MathML</a>

Let <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M120','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M120">View MathML</a> be the symmetrized moments of the dimension exponent. Then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M121','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M121">View MathML</a>

Remark9.

Asymptotics for Sk(d;n) with k=1,2,3,4,5,6 and with further accuracy are in section ‘More data’.

Analogous to these results for the dimension exponent are the following results for the intertwining exponent.

Theorem5.

For each k∈{0,1,2,⋯ } there exists a closed form expression

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M122','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M122">View MathML</a>

where each Qk,2kj is a polynomial with rational coefficients. Moreover, the degree of Qk,2kj is bounded by j.

For example,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M123','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M123">View MathML</a>

Remark10.

The expression for M(i;n)=M(cr2;n) was established first by Kasraoui (Theorem 2.3 of [9]).

Remark11.

Theorem 5 is deduced directly from Theorem 2. The shifted Bell polynomials for M(ik;n) for k≤5 are given in section ‘More data’, and see [55] for the aggregates with k≤12.

Remark12.

Amusingly, the formula for M(i;n) implies that the sequence <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M124','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M124">View MathML</a> taken modulo 4 is periodic of length 12 beginning with {1,1,2,1,3,0,3,1,0,3,3,2}. Similarly, the formula for M(i2;n) shows that the sequence is periodic modulo 9 (respectively 16) with period 39 (respectively 48). For more about such periodicity, see the papers of Lunnon et al. [57] and Montgomery et al. [58].

In analogy with Theorem 4, there is the following asymptotic result.

Theorem6.

With αn as above,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M125','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M125">View MathML</a>

Let <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M126','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M126">View MathML</a>. Then,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M127','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M127">View MathML</a>

Theorems 3 and 5 show that there will be closed formulae for all of the moments of these statistics. Moreover, these theorems give bounds for the number of terms in the summand and the degree of each of the polynomials. Therefore, to compute the formulae, it is enough to compute enough values for M(dk;n) or M(ik;n) and then to do linear algebra to solve for the coefficients of the polynomials. For example, M(d;n) needs P1,2(n) which has degree at most 0, P1,1(n) which has degree at most 1, and P1,0(n) which has degree at most 0. Hence, there are four unknowns, and so only M(d;n) for n=1,2,3,4 are needed to derive the formula for the expected value of the dimension exponent.

Computational results

Enumerating set partitions and calculating these statistics would take time O(Bn) (see Knuth’s volume [13] for discussion of how to generate all set partitions of fixed size, the book of Wilf and Nijenhuis [59], or the website [60] of Ruskey). This section introduces a recursion for computing the number of set partitions of n with a given dimension or intertwining exponent in time O(n4). The recursion follows by introducing a notion of ‘marked’ set partitions. This generalization seems useful in general when computing statistics which depend on the internal structure of a set partition.

The results may then be used with Theorems 3 and 5 to find exact formulae for the moments. Proofs are given in section ‘Proofs of recursions, asymptotics, and Theorem 3’.

For a set partition λ, mark each block either open or closed. Call such a partition a marked set partition. For each marked set partition λ of [ n], let o(λ) be the number of open blocks of λ and (λ) be the total number of blocks of λ. (Marked set partitions may be thought of as what is obtained when considering a set partition of a potentially larger set and restricting it to [n]. The open blocks are those that will become larger upon adding more elements of this larger set, while the closed blocks are those that will not.) With this notation, define the dimension of λ with blocks B1,B2,⋯ by

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M128','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M128">View MathML</a>

(5)

It is clear that if o(λ)=0, then λ may be thought of as a usual ‘unmarked’ set partition and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M129','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M129">View MathML</a> is the dimension exponent of λ. Define

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M130','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M130">View MathML</a>

(6)

Theorem7.

For n>0

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M131','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M131">View MathML</a>

with initial condition f(0;A,B)=0 for all (A,B)≠(0,0) and f(0;0,0)=1.

Therefore, to find the number of partitions of [ n] with dimension exponent equal to k, it suffices to compute f(n,0,k) for k and n. Figure 2 gives the histograms of the dimension exponent when n=20 and n=100. With increasing n, these distributions tend to normal with mean and variance given in Theorem 4. This approximation is already apparent for n=20.

thumbnailFigure 2. Histograms of the dimension exponent counts for n =20 and n =100.

It is not necessary to compute the entire distribution of the dimension index to compute the moment formulae for the dimension exponent. Namely, it is better to implement the following recursion for the moments.

Corollary1.

Define <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M132','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M132">View MathML</a>. Then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M133','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M133">View MathML</a>

To compute M(dk;n), then for each m<n, this recursion allows us to keep only k values rather than computing all O(m·m2) values of f(m,A,B). To find the linear relation of Theorem 3, only O(k·k2) values of Mk(d;n,A) are needed.

In analogy, there is a recursion for the intertwining exponent.

Let f(i)(n,A,B) be the number of marked partitions of [ n] with intertwining weight equal to B and with A open sets where the intertwining weight is equal to the number of interlaced pairs ij and k where k is in a closed set plus the number of triples i,k,j such that ij and k is in an open set.

Theorem8.

With the notation above, the following recursion holds

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M134','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M134">View MathML</a>

This recursion allows the distribution to be computed rapidly. Figure 3 gives the histograms of the intertwining exponent when n=20 and n=100. Again, for increasing n, the distribution tends to normal with mean and variance from Theorem 6. The skewness is apparent for n=20.

thumbnailFigure 3. Histograms of the intertwining exponent counts for n =20 and n =100.

Proofs of recursions, asymptotics, and Theorem 3

This section gives the proofs of the recursive formulae discussed in Theorems 7 and 8 Additionally, this section gives a proof of Theorem 3 using the three-variable generating function for f(n,A,B). Finally, it gives an asymptotic expansion for Bn+k/Bn with k fixed and n. This asymptotic is used to deduce Theorems 4 and 6.

Recursive formulae

This subsection gives the proof of the recursions for f(n,A,B) and f(i)(n,A,B) given in Theorems 7 and 8 The recursion is used in the next subsection to study the generating function for the dimension exponent.

Proof of Theorem 7 The four terms of the recursion come from considering the following cases: (1) n is added to a marked partition of [ n−1] as a singleton open set, (2) n is added to a marked partition of [ n−1] as a singleton closed set, (3) n is added to an open set of a marked partition of [ n−1] and that set remains open, and (4) n is added to an open set of a marked partition of [ n−1] and that set is closed.

Proof of Theorem 8 The argument is similar to that of Theorem 7. The same four cases arise. However, when adding n to an open set, the statistic may increase by any value j and it does so in exactly one way.

The generating function for f(n,A,B)

This section studies the generating function for f(n,A,B) and deduces Theorem 3. Let

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M135','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M135">View MathML</a>

(7)

be the three-variable generating function. Theorem 7 implies that

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M136','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M136">View MathML</a>

(8)

where FY denotes <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M137','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M137">View MathML</a>.

Then, F(X,0,Z) is the generating function for the distribution of d(λ), i.e.,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M138','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M138">View MathML</a>

Thus, the generating function for the kth moment is

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M139','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M139">View MathML</a>

Consider

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M140','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M140">View MathML</a>

(9)

So <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M141','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M141">View MathML</a>.

Lemma1

In the notation above,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M142','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M142">View MathML</a>

Proof.

From (8),

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M143','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M143">View MathML</a>

Hence, solving for Fn gives

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M144','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M144">View MathML</a>

(10)

Throughout the remainder Y=eα−1. Abusing notation, let

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M145','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M145">View MathML</a>

The following lemma gives an expression for Gk(X,α) in terms of a differential operators. Define the operators

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M146','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M146">View MathML</a>

Lemma2.

Clearly, G0(X,Y)=1. Moreover,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M147','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M147">View MathML</a>

Proof.

(10) is equivalent to

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M148','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M148">View MathML</a>

Now

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M149','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M149">View MathML</a>

where a eα has been commuted through. Then,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M150','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M150">View MathML</a>

(11)

Since Gk(0,α)=0 for k>0,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M151','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M151">View MathML</a>

(12)

From this

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M152','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M152">View MathML</a>

for some constants

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M153','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M153">View MathML</a>

The next lemma evaluates the terms in the summation of Lemma 2, thus yielding a generating function for Gk(X,Y) which resembles that for the Bell numbers.

Lemma3.

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M154','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M154">View MathML</a>

Proof.

It is easy to see by induction on that T1 is a polynomial in eX+α. Thus,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M155','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M155">View MathML</a>

Hence

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M156','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M156">View MathML</a>

From this, it is easy to see that

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M157','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M157">View MathML</a>

And the result follows.

Lemmas 2 and 3 readily yield the following expression for the moments of the dimension exponent as a shifted Bell polynomial.

Lemma4.

For each k≥0 and n≥0

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M158','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M158">View MathML</a>

Theorem 3 needs some further constraints on the degrees of terms in this polynomial. The following lemma yields the claimed bounds for the degrees.

Lemma5.

In the notation above, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M159','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M159">View MathML</a> unless all of the following hold:

1. cb.

2. c<b unless a=0.

3. b≤2k.

4. 3cbk.

5. 3cbk−2 if a≠0.

Proof.

Let Ha,b,c(X,α)=SaTbXc1. Using Equation 12, write <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M160','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M160">View MathML</a> in terms of the <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M161','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M161">View MathML</a> for <k. To do this requires understanding

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M162','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M162">View MathML</a>

As a first claim: if a=0, then the above is simply <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M163','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M163">View MathML</a>. This is seen easily from the fact that R commutes with T. For a≠0, it is easy to see that this is a linear combination of the <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M164','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M164">View MathML</a> over cc, and of <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M165','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M165">View MathML</a> over bb.

The desired properties can now be proved by induction on k. It is clear that they all hold for k=0. For larger k, assume that they hold for all k, and use Equation 12 to prove them for k.

By the inductive hypothesis, the TGk are linear combinations of Ha,b,c with c<b. Thus, (TTS−1S)TGk is a linear combination of Ha,b,c’s with b>c. Thus, by Equation 12, Gk is a linear combination of Ha,b,c’s with cb and a=0 or with c<b. This proves properties 1 and 2.

By the inductive hypothesis, the Gk are linear combinations of Ha,b,c with b≤2(k). Thus, TTS−1STGk is a linear combination of Ha,b,c’s with b≤2k+1−≤2k. Thus, by Equation 12, Gk is a linear combination of Ha,b,c’s with b≤2k. This proves property 3.

Finally, consider the contribution to Gk coming from each of the Gk terms. For =1, Gk is a linear combination of Ha,b,c’s with 3cbk−3 if a≠0, 3cbk−1 if a=0. Thus, TGk is a linear combination of Ha,b,c’s with 3cbk−3 if a≠0, and 3cbk−2 otherwise. Thus, (TTS−1S)TGk is a linear combination of Ha,b,c’s with 3cbk−3 if a=0, and 3cbk−2 otherwise. Thus, the contribution from these terms to Gk is a linear combination of Ha,b,c’s with 3cbk and 3cbk−2 if a≠0. For the terms with >1, Gk is a linear combination of Ha,b,c’s with 3cbk−2 and 3cbk−4 when a≠0. Thus, TGk is a linear combination of Ha,b,c’s with 3cbk−3, as is (TTS−1S)TGk. Thus, the contribution of these terms to Gk is a linear combination of Ha,b,c’s with 3cbk and 3cbk−3 if a≠0. This proves properties 4 and 5.

This completes the induction and proves the Lemma.

From this Lemma, it is easy to see that

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M166','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M166">View MathML</a>

for some polynomials Pk,(n) with deg(Pk,)≤ min(2k,k/2+/2).

Asymptotic analysis

This section presents some asymptotic analysis of the Bell numbers and ratios of Bell numbers. These results yield Theorems 4 and 6. Similar analysis can be found in [13].

Proposition2.

Let αn be the solution to

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M167','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M167">View MathML</a>

and let

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M168','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M168">View MathML</a>

Then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M169','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M169">View MathML</a>

More precisely, for T≥0

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M170','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M170">View MathML</a>

where Rm,k are rational functions. In particular

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M171','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M171">View MathML</a>

Proof.

The proof is very similar to the traditional saddle point method for approximating Bn. The idea is to evaluate at the saddle point for Bn rather than for Bn+k. We follow the proof in Chapter 6 of [61].

By Cauchy’s formula,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M172','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M172">View MathML</a>

where C encircles the origin once in the positive direction. Deform the path to a vertical line ui to u+i by taking a large segment of this line and a large semi-circle going around the origin. As the radius, say R, is taken to infinity the factor znk−1=O(Rnk−1) and exp(ez) is bounded in the half-plane.

Choose u=αn and then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M173','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M173">View MathML</a>

where

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M174','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M174">View MathML</a>

The real part has maxima around y=2πm for each integer m, but using <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M175','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M175">View MathML</a> for π<y<αn and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M176','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M176">View MathML</a> for y>αn as in [61] gives

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M177','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M177">View MathML</a>

Next, note that

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M178','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M178">View MathML</a>

where <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M179','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M179">View MathML</a> and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M180','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M180">View MathML</a> were used. Hence,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M181','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M181">View MathML</a>

Making the change of variables and extending the sum of interval of integration gives

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M182','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M182">View MathML</a>

Hence, Taylor expanding around y=0 and using

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M183','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M183">View MathML</a>

gives the desired result.

For more details, see [61].

Proposition 2 yields

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M184','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M184">View MathML</a>

(13)

Direct application of this result gives the results in Theorems 4 and 6.

Proofs of Theorems 1 and 2

This section gives the proofs of Theorems 2 and 1. Theorem 2 implies Theorem 5. A pair of lemmas which will be useful in the proof of Theorem 2:

Lemma6.

For Bn, the Bell numbers, define

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M185','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M185">View MathML</a>

where r,d,k,s are non-negative integers. Then, gr,d,k,s(n) is a shifted Bell polynomial of lower shift index −k and upper shift index r+sk.

Proof.

It clearly suffices to prove that gr,0,k,s(n) is a shifted Bell polynomial. Since gr,0,0,s(nk)=gr,0,k,s(n), it suffices to prove that gr,s(n):=gr,0,0,s(n) is a shifted Bell polynomial.

For this, consider the exponential generating function

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M186','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M186">View MathML</a>

This is easily seen to be equal to <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M187','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M187">View MathML</a> times a polynomial in ex of degree s+r.

Since g0,s(n)=Bn+s, the generating function <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M188','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M188">View MathML</a> equals <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M189','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M189">View MathML</a> times a polynomial of exact degree s. From this, for all s,r the space of all polynomials in ex of degree at most s+r times <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M190','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M190">View MathML</a> is spanned by the set of generating functions <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M191','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M191">View MathML</a> as m runs over all integers 0,1,…,s+r. Since the generating function for gr,s(n) lies in this span,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M192','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M192">View MathML</a>

for some rational numbers βs,r,m. It follows that for all n,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M193','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M193">View MathML</a>

For a sequence, r={r0,r1,⋯,rk}, of rational numbers and a polynomial <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M194','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M194">View MathML</a> define

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M195','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M195">View MathML</a>

(14)

where x0=0,xk+1=n+1.

Lemma7.

Fix k, let <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M196','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M196">View MathML</a> and r={r0,r1,⋯,rk} be a sequence of rational numbers. As defined above, M(k,Q,r,n,x) is a rational linear combination of terms of the form

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M197','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M197">View MathML</a>

where <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M198','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M198">View MathML</a> are polynomials.

Proof.

The proof is by induction on k. If k=0 then definitionally, M(k,Q,r,n,x)=Q(n)(x+r0)n, providing a base case for our result. Assume that the lemma holds for k one smaller. For this, fix the values of x1,…,xk−1 in the sum and consider the resulting sum over xk. Then

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M199','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M199">View MathML</a>

Consider the inner sum over xk:

If rk−1=rk, then the product of the last two terms is always <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M200','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M200">View MathML</a>, and thus the sum is some polynomial in x1,…,xk−1,n times <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M201','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M201">View MathML</a>. The remaining sum over x1,…,xk−1 is exactly of the form M(k−1,Q,r,n−1,x), for some polynomial Q, and thus, by the inductive hypothesis, of the correct form.

If rk−1rk, the sum is over pairs of non-negative integers a=xkxk−1−1 and b=nxk−1 summing to nxk−1−2 of some polynomial, Q in a and n and the other xi times (x+rk−1)a(x+rk)b. Letting y=(x+rk−1) and z=(x+rk), this is a sum of Q(xi,n,a)yazb. Let d be the a degree of Q. Multiplying this sum by (yz)d+1, yields, by standard results, a polynomial in y and z of degree nxk−1−2+(d+1) in which all terms have either y exponent or z exponent at least nxk−1−1. Thus, this inner sum over xk when multiplied by the non-zero constant (rk−1rk)d+1 yields the sum of a polynomial in x,n,x1,…,xk−1 times <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M202','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M202">View MathML</a> plus another such polynomial times <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M203','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M203">View MathML</a>. Thus, M(k,Q,r,n,x) can be written as a linear combination of terms of the form G(x)M(k−1,Q,r,n,x). The inductive hypothesis is now enough to complete the proof.

Turn next to the proof of Theorem 2. Proof of Theorem 2

It suffices to prove this Theorem for simple statistics. Thus, it suffices to prove that for any pattern P and polynomial Q that

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M204','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M204">View MathML</a>

is given by a shifted Bell polynomial in n. As a first step, interchange the order of summation over s and λ above. Hence,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M205','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M205">View MathML</a>

To deal with the sum over λ above, first consider only the blocks of λ that contain some element of s. Equivalently, let λ be obtained from λ by replacing all of the blocks of λ that are disjoint from s by their union. To clarify this notation, let Π(n) denote the set of all set partitions of [ n] with at most one marked block. For λΠ(n), say that sPλ if s in an occurrence of P in λ as a regular set partition so that additionally the non-marked blocks of λ are exactly the blocks of λ that contain some element of s. For λΠ(n) and λΠ(n), say that λ is a refinement of λ if the unmarked blocks in λ are all parts in λ, or equivalently, if λ can be obtained from λ by further partitioning the marked block. Denote λ being a refinement of λ as λλ. Thus, in the previous computation of M(fP,Q;n), letting λ be the marked partition obtained by replacing the blocks in λ disjoint from s by their union:

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M206','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M206">View MathML</a>

Note that the λ in the final sum above correspond exactly to the set partitions of the marked block of λ. For λΠ(n), let |λ| be the size of the marked block of λ. Thus,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M207','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M207">View MathML</a>

Remark13.

This is valid even when the marked block is empty.

Dealing directly with the Bell numbers above will prove challenging, so instead compute the generating function

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M208','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M208">View MathML</a>

After computing this, extract the coefficients of M(P,Q,n,x) and multiply them by the appropriate Bell numbers.

To compute M(P,Q,n,x), begin by computing the value of the inner sum in terms of s=(x1<x2<…<xk) that preserves the consecutivity relations of P (namely those in C(P)). Denote the equivalence classes in P by 1,2,…,. Let zi be a representative of this ith equivalence class. Then, an element λΠ(n) so that sPλ can be thought of as a set partition of [ n] into labeled equivalence classes 0,1,…,, where the 0th class is the marked block, and the ith class is the block containing <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M209','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M209">View MathML</a>. Thus, think of the set of such λ as the set of maps g:[ n]→{0,1,…,} so that:

1. g(xj)=i if j is in the ith equivalence class

2. g(x)≠i if x<xj, jF(P) and j is in the ith equivalence class

3. g(x)≠i if x>xj, jL(P) and j is in the ith equivalence class

4. g(x)≠i if <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M210','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M210">View MathML</a>, (j,j)∈A(P) and j,j are in the ith equivalence class

It is possible that no such g will exist if one of the latter three properties must be violated by some x=xh. If this is the case, this is a property of the pattern P, and not the occurrence s, and thus, M(fP,Q;n)=0 for all n. Otherwise, in order to specify g, assign the given values to g(xi) and each other g(x) may be independently assigned values from the set of possibilities that does not violate any of the other properties. It should be noted that 0 is always in this set, and that furthermore, this set depends only which of the xi our given x is between. Thus, there are some sets S0,S1,…,Sk⊆{0,1,…,}, depending only on s, so that g is determined by picking functions

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M211','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M211">View MathML</a>

Thus, the sum over such λ of <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M212','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M212">View MathML</a> is easily seen to be

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M213','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M213">View MathML</a>

where ri=|Si|−1 (recall |Si|>0, because 0∈Si). For such a sequence, r of rational numbers define

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M214','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M214">View MathML</a>

(15)

where, as in Lemma 7, using the notation x0=0,xk+1=n+1.

Note that the sum is empty if C(P) contains nonconsecutive elements. We will henceforth assume that this is not the case. We call j a follower if either (j−1,j) or (j,j−1) are in C(P). Clearly, the values of all xi are determined only by those xi where i is not a follower. Furthermore, Q is a polynomial in these values and n. If j is the index of the ith non-follower then let yi=xjj+i. Now, sequences of xi satisfying the necessary conditions correspond exactly to those sequences with 1≤y1<y2<⋯<ykfnf where f is the total number of followers. Thus,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M215','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M215">View MathML</a>

where the <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M216','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M216">View MathML</a> are modified versions of the ri to account for the change from {xj} to {yi}. In particular, if xj is the (i+1)st non-follower, then <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M217','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M217">View MathML</a>.

By Lemma 7, <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M218','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M218">View MathML</a> is a linear combination of terms of the form F(n)G(x)(x+ri)nk for polynomials <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M219','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M219">View MathML</a> and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M220','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M220">View MathML</a>.

Thus, M(fP,Q;n) can be written as a linear combination of terms of the form gr,d,,s(n) where is the number of equivalence classes in P and r,d,s are non-negative integers. Therefore, by Lemma 6 M(fP,Q;n) is a shifted Bell polynomial.

The bound for the upper shift index follows from the fact that M(fP,Q;n)=O(nNBn) and by (13) each term nαBn+β is of an asymptotically distinct size. To complete the proof of the result it is sufficient to bound the lower shift index of the Bell polynomial. By (15) it is clear the largest power of x in each term is (nk). Thus, from Lemma 6, the resulting shift Bell polynomials can be written with minimum lower shift index −k. This completes the proof.

Next turn to the proof of Theorem 1. To this end, introduce some notation.

Definition3.

Given three patterns P1,P2,P3, of lengths k1,k2,k3, say that a merge of P1 and P2 onto P3 is a pair of strictly increasing functions m1:[ k1]→[k3], m2:[ k2]→[ k3] so that

1. m1([k1])∪m2([k2])=[ k3]

2.

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M221','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M221">View MathML</a>

if and only if <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M222','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M222">View MathML</a>, and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M223','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M223">View MathML</a> if and only if

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M224','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M224">View MathML</a>

3. iF(P3) if and only if there exists either a jF(P1) so that i=m1(j) or a jF(P2) so that i=m2(j)

4. iL(P3) if and only if there exists either a jL(P1) so that i=m1(j) or a jL(P2) so that i=m2(j)

5. (i,i)∈A(P3) if and only if there exists either a (j,j)∈A(P1) so that i=m1(j) and i=m1(j) or a (j,j)∈A(P2) so that i=m2(j) and i=m2(j)

6. (i,i)∈C(P3) if and only if there exists either a (j,j)∈C(P1) so that i=m1(j) and i=m1(j) or a (j,j)∈C(P2) so that i=m2(j) and i=m2(j)

Such a merge is denoted as m1,m2:P1,P2P3.

Note that the last four properties above imply that given P1 and P2, a merge (including a pattern P3) is uniquely defined by maps m1,m2 and an equivalence relation <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M225','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M225">View MathML</a> satisfying (1) and (2) above.

Lemma8.

Let P1 and P2 be patterns. For any λ there is a one-to-one correspondence:

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M226','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M226">View MathML</a>

(16)

Moreover, under this correspondence

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M227','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M227">View MathML</a>

(17)

Proof.

Begin by demonstrating the bijection defined by Eq. 16. On the one hand, given <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M228','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M228">View MathML</a> given by <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M229','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M229">View MathML</a> and m1,m2:P1,P2P3, define s1 and s2 by the sequences <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M230','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M230">View MathML</a> and <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M231','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M231">View MathML</a>. It is easy to verify that these are occurrences of the patterns P1 and P2 and furthermore that Eq. 17 holds for this mapping.

This mapping has a unique inverse: Given s1 and s2, note that s3 must equal the union s1s2. Furthermore, the maps ma, for a=1,2, must be given by the unique function so that ma(i)=j if and only if the ith smallest element of sa equals the jth smallest element of s3. Note that the union of these images must be all of [k3]. In order for s3 to be an occurrence of P3 the equivalence relation <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M232','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M232">View MathML</a> must be that <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M233','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M233">View MathML</a> if and only if the ith and jth elements of s3 are equivalent under λ. Note that since S1 and S2 were occurrences of P1 and P2, that this must satisfy condition (2) for a merge. The rest of the data associated to P3 (namely F(P3),L(P3), A(P3), and C(P3)) is now uniquely determined by m1,m2,P1,P2 and the fact that P3 is a merge of P1 and P2 under these maps. To show that s3 is an occurrence of P3 first note that by construction the equivalence relations induced by λ and P3 agree. If iF(P3), then there is a jF(Pa) with i=ma(j) for some a,j. Since sa is an occurrence of Pa, this means that the jth smallest element of sa in in First(λ). On the other hand, by the construction of ma, this element is exactly <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M234','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M234">View MathML</a>. This if iF(P3), ziFirst(λ). The remaining properties necessary to verify that S3 is an occurrence of P3 follow similarly. Thus, having shown that the above map has a unique inverse, the proof of the lemma is complete.

Recall, the number of singleton blocks is denoted X1 and it is a simple statistic. To illustrate this lemma return to the example of <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M235','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M235">View MathML</a> discussed prior to the lemma. Let P1=P2 be the pattern of length 1 with A(P1)=ϕ, F(P1)=L(P1)=1. Then there are five possible merges of P1 and P2 into some pattern P3. The first choice of P3 is P1 itself. In which case m1(1)=m2(1)=1. The latter choices of P3 is the pattern of length 2 with F(P3)=L(P3)={1,2},A(P3)=. The equivalence relation on P3 could be either the trivial one or the one that relates 1 and 2 (though in the latter case the pattern P3 will never have any occurrences in any set partition). In either of these cases, there is a merge with m1(1)=1 and m2(1)=2 and a second merge with m1(1)=2 and m2(1)=1. As a result,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M236','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M236">View MathML</a>

Proof of Theorem 1 The fact that statistics are closed under pointwise addition and scaling follows immediately from the definition. Similarly, the desired degree bounds for these operations also follow easily. Thus only closure and degree bounds for multiplication must be proved. Since every statistic may be written as a linear combination of simple statistics of no greater degree, and since statistics are closed under linear combination, it suffices to prove this theorem for a product of two simple statistics. Thus let fi be the simple statistic defined by a pattern Pi of size ki and a polynomial Qi. It must be shown that f1(λ)f2(λ) is given by a statistic of degree at most k1+k2+ deg(Q1)+ deg(Q2).

For any λ

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M237','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M237">View MathML</a>

Simplify this equation using Lemma 8, writing this as a sum over occurrences of only a single pattern in λ.

Applying Lemma 8,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M238','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M238">View MathML</a>

Thus, the product of f1 and f2 is a sum of simple characters. Note that the quantity is a polynomial of s3 which is denoted <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M239','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M239">View MathML</a> Finally, each pattern P3 has size at most k1+k2 and each polynomial <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M240','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M240">View MathML</a> has degree at most deg(Q1)+ deg(Q2). Thus the degree of the product is at most the sum of the degrees.

More data

This section contains some data for the dimension and intertwining exponent statistics. The moment formulae of Theorem 3 for k≤22 and the moment formulae for the intertwining exponent for k≤12 have been computed and are available at [55]. Moreover, the values f(n,0,B) for n≤238 and f(i)(n,0,B) for n≤146 are available. These sequences can also be found on Sloane’s Online Encyclopedia of integer sequences [62].

The remainder of this section contains a small amount of data and observations regarding the distributions f(n,0,B) and f(i)(n,0,B) and regarding the shifted Bell polynomials of Theorems 3 and 5.

Dimension index

A couple of easy observations: it is clear that

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M241','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M241">View MathML</a>

That is the number of set partitions of [n] with dimension exponent 0 is 2n−1. Set partitions of [ n] that have dimension exponent 0 must have n appearing in a singleton set or it must appear in a set with n−1, thus the result is obtained by recursion. Additionally, the number of set partitions of [ n] with dimension exponent equal to 1 is n2n−1, that is

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M242','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M242">View MathML</a>

Curiously, the numbers f(n,0,B) are smooth (roughly they have many small prime factors), for reasonably sized B. This can be established by using the recursion of Theorem 7. For example,

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M243','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M243">View MathML</a>

Note that f(100,0,979) has 111 digits and f(100,0,2079) has about 100 digits.

In the notation of Theorem 3, these are some values of the first few moments of d(λ).

These formulae exhibit a number of properties. Here is a list of some of them.

1. Using the fact that Bn+knkBn, each moment M(dk;n) has a number of terms with asymptotic of size equal to n2kBn, up to powers of log(n) (or αn). Call these terms the leading powers of n. The leading ‘power’ of n contribution is equal to

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M245','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M245">View MathML</a>

where T is the operator given by TBm=Bm+1. For example, the leading order n contributions for the average is

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M246','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M246">View MathML</a>

and the leading order contribution for the second moment is

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M247','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M247">View MathML</a>

Structure of this sort is necessary because of the asymptotic normality of the dimension exponent (see the forthcoming work [1]). The next remark also concerns this sort of structure.

2. The next order n terms of M(dk;n) have size roughly n2k−1Bn and have the shape

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M248','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M248">View MathML</a>

where the constants Cj are

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M249','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M249">View MathML</a>

3. The generating function for the polynomials P0,k(n) seems to be

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M250','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M250">View MathML</a>

We do not have a proof of this observation.

As in the introduction, let <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M251','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M251">View MathML</a> From Proposition 2 and the formulae for M(dk;n) deduced from Theorem 3 and stated in section ‘Dimension index’ and using SAGE, the asymptotic expansion of the first few Sk are as follows:

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M252','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M252">View MathML</a>

Remark14.

These asymptotics support the claim that the dimension exponent is normally distributed with mean asymptotic to <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M253','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M253">View MathML</a> and standard deviation <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M254','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M254">View MathML</a>. This result will be established in the forthcoming work [1].

Intertwining index

Table 2 contains the distribution for of the intertwining exponent for the first few n.

Table 2. A table of the distribution of the intertwining exponentf(i)(n ,0, B )

In the notation of Theorem 5, these are some values of the first few moments of i(λ)=cr2(λ).

We conjecture that Qj(n)=0 for all j<0.

The formulae stated previously for <a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M255','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M255">View MathML</a> with (13) give

<a onClick="popup('http://www.resmathsci.com/content/1/1/2/mathml/M256','MathML',630,470);return false;" target="_blank" href="http://www.resmathsci.com/content/1/1/2/mathml/M256">View MathML</a>

Acknowledgements

The authors thank the careful referee for a detailed report.

References

  1. Chern, B, Diaconis, P, Kane, DM, Rhoades, RC: Asymptotic normality of set partition statistics associated with supercharacters. in press

  2. Chen, WYC, Deng, EYP, Du, RRX, Stanley, RP: Crossings and nestings of matchings and partition. Trans. Amer. Math. Soc. 359(4), 1555–1575 (2007)

  3. Stanley, RP: Enumerative Combinatorics. Volume 2. Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge (1999)

  4. Kreweras, G: Sur les partitions noncroisées d’un cycle. Discrete Math. 1, 333–350 (1972). Publisher Full Text OpenURL

  5. Simion, R: Noncrossing partitions. Discrete Math. 217, 367–409 (2000). Publisher Full Text OpenURL

  6. Marberg, E: Crossings and nestings in colored set partitions. Electron. J. Combin. 20(4), Research Paper 6 (2013)

  7. Mansour, T: Combinatorics of Set Partitions. Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL (2013)

  8. Shattuck, M: Recounting the number of rises, levels, and descents in finite set partitions. Integers. 10, 179–185 (2010)

  9. Kasraoui, A: Average values of some z-parameters in a random set partition. Electron. J. Combinatorics. 18(1), 42 Paper 228 (2011)

  10. Mansour, T, Shattuck, M: Enumerating finite set partitions according to the number of connectors. Online J. Anal. Combinatorics. 6, 17 Article 3 (2011)

  11. Knopfmacher, A, Mansour, T, Wagne, S: Records in set partitions. Electron. J. Combinatorics. 17, 14 Paper 109 (2010)

  12. Graham, RL, Knuth, DE, Patashnik, O: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Publishing Company, Reading, MA (1994)

  13. Knuth, D: The Art of Computer Programming vol. 4a: Combinatorial Algorithms, Part I. Addison-Wesley, Upper Saddle River, New Jersey (2011)

  14. Stanley, RP: Enumerative Combinatorics. Volume 1, 2nd edn. Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge (2012)

  15. Riordan, J: An Introduction to Combinatory Analysis, Wiley, New York (1958)

  16. Pitman, J: Combinatorial Stochastic Processes, Springer, Berlin (2006)

  17. Garsia, A: An expose of the Mullin-Rota theory of polynomials of binomial type. Linear Multilinear Algebra. 1, 47–65 (1973). Publisher Full Text OpenURL

  18. Knuth, D: Convolution polynomials. Math. J. 2, 67–78 (1992)

  19. Halverson, T, Ram, A: Partition algebras. Eur. J. Combin. 26(6), 869–921 (2005). Publisher Full Text OpenURL

  20. Aguiar, M, Mahajan, S: Monoidal functors, species and Hopf Algebras. CRM monograph series, American Mathematical Society, Providence, RI (2010)

  21. Kasraoui, A, Zeng, J: Distribution of crossings, nestings and alignments of two edges in matchings and partitions. Electron. J. Combinatorics. 12(1), Paper 33 (2006)

  22. Kasraoui, A: On the limiting distribution of some numbers of crossings in set partitions. arXiv:1301.6540 [math.CO]

  23. Fristedt, B: The structure of random partitions of large sets. Technical report. (1987)

  24. Hwang, HK: On convergence rates in the central limit theorems for combinatorial structures. Eur. J. Combin.. 19(3), 329–343 (1998). Publisher Full Text OpenURL

  25. Stam, AJ: Generation of random partitions of a set by an urn model. J. Combin. Theory Series A. 35, 231–240 (1983). Publisher Full Text OpenURL

  26. Pitman, J: Some probabilistic aspects of set partitions. Amer. Math. Mon.. 104, 201–209 (1997). Publisher Full Text OpenURL

  27. Erdös, P, Turán, P: On some problems of statistical group theory, I. Z.. Whhr. Verw. Gebiete.. 4, 151–163 (1965)

  28. Erdös, P, Turán, P: On some problems of statistical group theory, II. Acta Math. Acad. Sci. Hun.. 18, 151–163 (1967). Publisher Full Text OpenURL

  29. Erdös, P, Turán, P: On some problems of statistical group theory, III. Acta Math. Acad. Sci. Hun.. 18, 309–320 (1967). Publisher Full Text OpenURL

  30. Erdös, P, Turán, P: On some problems of statistical group theory, IV. Acta Math. Acad. Sci. Hun.. 19, 413–435 (1968). Publisher Full Text OpenURL

  31. Erdös, P, Turán, P: On some problems of statistical group theory. V. Periodica Math. Hung.. 1, 5–13 (1971). Publisher Full Text OpenURL

  32. Erdös, P, Turán, P: On some problems of statistical group theory, VI. J. Ind. Math. Soc.. 34, 175–192 (1970)

  33. Erdös, P, Turán, P: On some problems of statistical group theory, VII. Periodica Math. Hung.. 2, 149–163 (1972). Publisher Full Text OpenURL

  34. Fulman, J: Random matrix theory over finite fields. Bull. Amer. Math. Soc.. 34, 51–85 (2002)

  35. Diaconis, P, Fulman, J, Guralnick, R: On fixed points of random permutations. J. Alg. Comb. 28, 189–218 (2008). Publisher Full Text OpenURL

  36. Newman, MF: Groups of prime-power order. In: Kov’acs LG (ed.) Groups-Canberra 1989. Lecture Notes in Mathematics vol. 1456, Berlin: Springer (1990)

  37. Kerov, S: Asymptotic Representation Theory of the Symmetric Group and Its Applications in Analysis. Translations of Mathematical Monographs vol, 219, RI: American Mathematical Society, Providence (2003)

  38. Turán, P: Remarks on the characters belonging to the irreducible representations of the symmetric group Sn of n letters. Fourier analysis and approximation theory (Proc. Colloq., Budapest, 1976, vol. ii. Colloq. Math. Soc. János Bolyai, vol. 19, Berlin (1978)

  39. Stanley, RP: Increasing and decreasing subsequences and their variants. Proceedings of International Congress of Mathematical Society, Zurich (2006)

  40. Kerov, S, Vershik, A: Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux. Docl. Akad. Nauk.. 233, 1024–1027 (1977)

  41. Logan, B, Shepp, L: A variational problem for random Young tableaux. Adv. Math.. 26, 206–222 (1977). Publisher Full Text OpenURL

  42. Baik, J, Deift, P, Johansson, K: On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12, 1119–1178 (1999). Publisher Full Text OpenURL

  43. Anderson, GW, Guionnet, A, Zeitouni, O: Introduction to Random Matrices, Cambridge Press, Cambridge (2009)

  44. Forrester, P: Log-gases and Random Matrices, Princeton University Press, Princeton (2010)

  45. Arias-Castro, E, Diaconis, P, Stanley, R: A super-class walk on upper-triangular matrices. J. Algebra. 278(2), 739–765 (2004). Publisher Full Text OpenURL

  46. André, C: Basic characters of unitriangular group. J. Algebra. 175, 287–319 (1995). Publisher Full Text OpenURL

  47. André, C: Irreducible characters of finite algebra groups. In: JFQ, Santana AP, Duarte AL (eds.) Matrices and Group Representations. Sér B no. 19, Coimbra: Textos Mat (1998)

  48. André, C: Basic characters of the unitriangular group (for arbitrary primes) (2002)

  49. Yan, N: Representation theory of the finite unipotent linear group. PhD thesis, Pennsylvania State University. Department of Mathematics (2001)

  50. Aguiar, M, André, C, Benedetti, C, Bergeron, N, Chen, Z, Diaconis, P, Hendrickson, A, Hsiao, S, Isaacs, IM, Jedwab, A, Johnson, K, Karaali, G, Lauve, A, Le, T, Lewis, S, Li, H, Magaard, K, Marberg, E, Novelli, J-C, Pang, A, Saliola, F, Tevlin, L, Thibon, JY, Thiem, N, Venkateswaran, V, Vinroot, CR, Yan, N, Zabrocki, M: Supercharacters, symmetric functions in noncommuting variables, and related Hopf algebras. Adv. Math. 229(4), 2310–2337 (2012). Publisher Full Text OpenURL

  51. Aguiar, M, Bergeron, N, Thiem, N: Hopf monoids from class functions on unitriangular matrices. Algebra and Number Theory,. 7-7, 1743–1779 (2013)

  52. Diaconis, P, Isaacs, IM: Supercharacters and superclasses for algebra groups. Trans. Amer. Math. Soc.. 360, 2359–2392 (2008)

  53. Diaconis, P, Thiem, N: Supercharacter formulas for pattern groups. Trans. Amer. Math. Soc.. 361, 3501–3533 (2009). Publisher Full Text OpenURL

  54. Marberg, E: Actions and identities on set partitions. Electron. J. Combinatorics. 19(1), 31 Paper 28 (2013)

  55. Rhoades, RC: http://math.stanford.edu/~rhoades/RESEARCH/papers.html webcite (2013)

  56. Bergeron, N, Thiem, N: A supercharacter table decomposition via power-sum symmetric functions. Int. J. Algebra Comput. (IJAC). 23-4, 763–778 (2013)

  57. Lunnon, WF, Pleasants, PAB, Stephens, NM: Arithmetic properties of Bell numbers to a composite modulus i. Acta Arith.. 35(1), 1–16 (1979)

  58. Montgomery, PL, Nahm, SJr: SSW: The period of the Bell numbers modulo a prime. Math. Comp.. 79(271), 1793–1800 (2010). Publisher Full Text OpenURL

  59. Nijenhuis, A, Wilf, HS: Combinatorial Algorithms. For Computers and Calculators, Computer Science and Applied Mathematics. Academic Press, Inc, New York-London (1978)

  60. Ruskey F: Combinatorial Object Server. http://www.theory.csc.uvic.ca/~cos/ webcite (2013)

  61. Bruijn, de: NG, Asymptotic Methods in Analysis.Dover, New York (1981)

  62. Sloane N: Online Encyclopedia of Integer Sequences. http://oeis.org/ webcite (2013)