edit this statistic or download as text // json
Identifier
Values
=>
Cc0002;cc-rep
[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       
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] MR3095005
WARNING - could not verify link <urlopen error [SSL: CERTIFICATE_VERIFY_FAILED] certificate verify failed: self-signed certificate in certificate chain (_ssl.c:992)>
[2] WARNING - could not verify link <urlopen error [SSL: CERTIFICATE_VERIFY_FAILED] certificate verify failed: self-signed certificate in certificate chain (_ssl.c:992)>
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
Jan 01, 2024 at 21:49 by Martin Rubey