cp's OEIS Frontend

The table shows the number of partitions of [n] = {1, 2, 3, ..., n} with genus g.

The set of noncrossing partitions is exactly the set of genus zero partitions. The numbers corresponding to this case are the Catalan numbers.

This is essentially table 2.1 in Martha Yip's thesis (p. 12).

From Robert Coquereaux, Feb 16 2024: (Start)

The two-dimensional array is called triangle of genus-dependent Bell numbers B(n, g); if n >= 1, n even, nonzero values are obtained for 0 <= g <= floor((n-1)/2); if n >= 1, odd, nonzero values are obtained for 0 <= g < (n-1)/2.

The two-dimensional array B(n, g) can be obtained from a three-dimensional array S2(n, k, g), by summation over the number k of blocks. The numbers S2(n, k, g) are genus-dependent Stirling numbers of the second kind. They give the number of genus g partitions of the n-set which are partitions into k nonempty subsets (blocks). The numbers S2(n, k, g) are discussed in A370420.

(End)

From Robert Coquereaux, Feb 12 2024: (Start)

Call B(n, g) the number of genus g partitions of a set with n elements (genus-dependent Bell number). Then a(n) = B(n, 2) with B(6, 2) = 1.

The entries of the triangle T(n, k) giving the number of genus 2 partitions of a set with n elements with k parts are known from R. Cori and G. Hetyei A297178.

Defining a(n) to be the sum over k of T(n,k) one shows that a(n) obeys the recurrence

a(n) = a(n-1) * (2*(-9 + 2*n) (-84 + n (88 + n*(-39 + 5*n)))) / ((-6 + n)*(-216 + n*(181 + n*(-54 + 5 n)))) with a(1) = a(2) = a(3) = a(4) = a(5) = 0 and a(6) = 1.

This determines a(n) for all n. One can solve the above recurrence and find an explicit formula, given below, for a(n) as a function of n. (End)

The formula given below was conjectured by Martha Yip and proved by Robert Cori and Gábor Hetyei.

More generally one may consider genus-dependent Stirling numbers S(n, k, g) that count the partitions of genus g and k parts of the n-set.

Then T(n, k) = S(n, k, 1). See Robert Coquereaux and Jean-Bernard Zuber.

Genus-dependent Stirling numbers of the second kind S2(n,k,g), 1 <= n, 1 <= k <= n, 0 <= g <= floor((n-1)/2). This is an infinite three-dimensional array. Its first 15 rows (n:1..15) are given by the table (see Links) taken from the article by Robert Coquereaux and Jean-Bernard Zuber (where a transpose of this table is given), see p. 32. These 15 rows determine 589 entries of the sequence (Data).

Example: the numbers S2(5,k,0), k=1..5, are {1,10,20,10,1} and appear on line 5, column 1; the numbers S2(5,k,1), k=1..5, are {0,5,5,0,0} and appear on line 5, column 2. Values of S2(n,k,g) for g > floor((n-1)/2) are equal to 0 and are not displayed.

Summing S2(n,k,g) over k gives genus-dependent Bell numbers B(n,g), A370235. Summing S2(n,k,g) over g gives S2(n,k), the Stirling numbers of the second kind A008277. Summing S2(n,k,g) over k and g gives the Bell numbers B(n), A000110. Example: S2(5,k,0) = 1, 10, 20, 10, 1 and S2(5,k,1) = 0, 5, 5, 0, 0 for k = 1..5; therefore S2(5,k) = 1, 15, 25, 10, 1, B(5,0) = 42, B(5,1) = 10, and B(5) = 52.

Call B(n, g) the number of genus g partitions of a set with n elements (genus-dependent Bell number). Then a(n) = B(n, 3) with B(8, 3) = 1.

a(8) = 1 through a(15) = 565256120 were explicitly determined by listing of partitions of an n-set and selecting those of genus 3.

The coefficients of the sixth-degree polynomial appearing in the numerator of the conjectured formula were determined by using experimental values for a(8) up to a(14); the term a(15) given by the formula agrees with the experimental value.

Using the conjectured formula for a(n) gives the following terms for n=16..20 : 4593034160, 35025118700, 253374008888, 1753071498620, 11675101781850. The E.g.f. given in the Formula section is obtained from the conjectured formula for a(n).