- FindStat

Identifier

St001934: Integer partitions ⟶ ℤ

Values

[1] => 1
[2] => 1
[1,1] => 1
[3] => 2
[2,1] => 1
[1,1,1] => 1
[4] => 5
[3,1] => 2
[2,2] => 1
[2,1,1] => 1
[1,1,1,1] => 1
[5] => 14
[4,1] => 5
[3,2] => 2
[3,1,1] => 2
[2,2,1] => 1
[2,1,1,1] => 1
[1,1,1,1,1] => 1
[6] => 42
[5,1] => 14
[4,2] => 5
[4,1,1] => 5
[3,3] => 4
[3,2,1] => 2
[3,1,1,1] => 2
[2,2,2] => 1
[2,2,1,1] => 1
[2,1,1,1,1] => 1
[1,1,1,1,1,1] => 1
[7] => 132
[6,1] => 42
[5,2] => 14
[5,1,1] => 14
[4,3] => 10
[4,2,1] => 5
[4,1,1,1] => 5
[3,3,1] => 4
[3,2,2] => 2
[3,2,1,1] => 2
[3,1,1,1,1] => 2
[2,2,2,1] => 1
[2,2,1,1,1] => 1
[2,1,1,1,1,1] => 1
[1,1,1,1,1,1,1] => 1

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

$F_{1} = q$

$F_{2} = 2\ q$

$F_{3} = 2\ q + q^{2}$

$F_{4} = 3\ q + q^{2} + q^{5}$

$F_{5} = 3\ q + 2\ q^{2} + q^{5} + q^{14}$

$F_{6} = 4\ q + 2\ q^{2} + q^{4} + 2\ q^{5} + q^{14} + q^{42}$

$F_{7} = 4\ q + 3\ q^{2} + q^{4} + 2\ q^{5} + q^{10} + 2\ q^{14} + q^{42} + q^{132}$

Description

The number of monotone factorisations of genus zero of a permutation of given cycle type.
A monotone factorisation of genus zero of a permutation

$\pi\in\mathfrak S_n$ with

$\ell$ cycles, including fixed points, is a tuple of

$r = n - \ell$ transpositions

$(a_1, b_1),\dots,(a_r, b_r)$
with

$b_1 \leq \dots \leq b_r$ and

$a_i < b_i$ for all

$i$ , whose product, in this order, is

$\pi$ .
For example, the cycle

$(2,3,1)$ has the two factorizations

$(2,3)(1,3)$ and

$(1,2)(2,3)$ .

References

[1] Goulden, I. P., Guay-Paquet, M., Novak, J. Monotone Hurwitz numbers in genus zero MathSciNet:3095005

Code

@cached_function
def statistic(mu):
    pi = Permutations(mu.size()).element_in_conjugacy_classes(mu)
    return len(monotone_factorizations(pi, len(pi)-len(mu)))

def monotone_factorizations(pi, m, b=None):
    if b is None:
        b = len(pi)
    return list(monotone_factorizations_iter(pi, m, b))

def monotone_factorizations_iter(pi, m, b=None):
    n = len(pi)
    if not m:
        if pi.number_of_fixed_points() == n:
            yield []
    else:
        for b1 in range(2, b+1):
            for a1 in range(1, b1):
                pi1 = Permutation([(a1, b1)]) * pi
                for t in monotone_factorizations(pi1, m-1, b1):
                    yield t + [(a1, b1)]

Created

Dec 28, 2023 at 17:31 by Martin Rubey

Updated

Aug 05, 2024 at 22:54 by Martin Rubey