*****************************************************************************
*       www.FindStat.org - The Combinatorial Statistic Finder               *
*                                                                           *
*       Copyright (C) 2019 The FindStatCrew <info@findstat.org>             *
*                                                                           *
*    This information is distributed in the hope that it will be useful,    *
*    but WITHOUT ANY WARRANTY; without even the implied warranty of         *
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                   *
*****************************************************************************

-----------------------------------------------------------------------------
Statistic identifier: St001934

-----------------------------------------------------------------------------
Collection: Integer partitions

-----------------------------------------------------------------------------
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)]


-----------------------------------------------------------------------------
Statistic 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

-----------------------------------------------------------------------------
Created: Dec 28, 2023 at 17:31 by Martin Rubey

-----------------------------------------------------------------------------
Last Updated: Aug 05, 2024 at 22:54 by Martin Rubey