- FindStat

edit this statistic or download as text // json

Identifier

St000696: Permutations ⟶ ℤ

Values

[1] => 2

[1,2] => 3

[2,1] => 1

[1,2,3] => 4

[1,3,2] => 2

[2,1,3] => 2

[2,3,1] => 2

[3,1,2] => 2

[3,2,1] => 2

[1,2,3,4] => 5

[1,2,4,3] => 3

[1,3,2,4] => 3

[1,3,4,2] => 3

[1,4,2,3] => 3

[1,4,3,2] => 3

[2,1,3,4] => 3

[2,1,4,3] => 1

[2,3,1,4] => 3

[2,3,4,1] => 3

[2,4,1,3] => 1

[2,4,3,1] => 1

[3,1,2,4] => 3

[3,1,4,2] => 1

[3,2,1,4] => 3

[3,2,4,1] => 1

[3,4,1,2] => 3

[3,4,2,1] => 3

[4,1,2,3] => 3

[4,1,3,2] => 1

[4,2,1,3] => 1

[4,2,3,1] => 3

[4,3,1,2] => 3

[4,3,2,1] => 1

[1,2,3,4,5] => 6

[1,2,3,5,4] => 4

[1,2,4,3,5] => 4

[1,2,4,5,3] => 4

[1,2,5,3,4] => 4

[1,2,5,4,3] => 4

[1,3,2,4,5] => 4

[1,3,2,5,4] => 2

[1,3,4,2,5] => 4

[1,3,4,5,2] => 4

[1,3,5,2,4] => 2

[1,3,5,4,2] => 2

[1,4,2,3,5] => 4

[1,4,2,5,3] => 2

[1,4,3,2,5] => 4

[1,4,3,5,2] => 2

[1,4,5,2,3] => 4

[1,4,5,3,2] => 4

[1,5,2,3,4] => 4

[1,5,2,4,3] => 2

[1,5,3,2,4] => 2

[1,5,3,4,2] => 4

[1,5,4,2,3] => 4

[1,5,4,3,2] => 2

[2,1,3,4,5] => 4

[2,1,3,5,4] => 2

[2,1,4,3,5] => 2

[2,1,4,5,3] => 2

[2,1,5,3,4] => 2

[2,1,5,4,3] => 2

[2,3,1,4,5] => 4

[2,3,1,5,4] => 2

[2,3,4,1,5] => 4

[2,3,4,5,1] => 4

[2,3,5,1,4] => 2

[2,3,5,4,1] => 2

[2,4,1,3,5] => 2

[2,4,1,5,3] => 2

[2,4,3,1,5] => 2

[2,4,3,5,1] => 2

[2,4,5,1,3] => 2

[2,4,5,3,1] => 2

[2,5,1,3,4] => 2

[2,5,1,4,3] => 2

[2,5,3,1,4] => 2

[2,5,3,4,1] => 2

[2,5,4,1,3] => 2

[2,5,4,3,1] => 2

[3,1,2,4,5] => 4

[3,1,2,5,4] => 2

[3,1,4,2,5] => 2

[3,1,4,5,2] => 2

[3,1,5,2,4] => 2

[3,1,5,4,2] => 2

[3,2,1,4,5] => 4

[3,2,1,5,4] => 2

[3,2,4,1,5] => 2

[3,2,4,5,1] => 2

[3,2,5,1,4] => 2

[3,2,5,4,1] => 2

[3,4,1,2,5] => 4

[3,4,1,5,2] => 2

[3,4,2,1,5] => 4

[3,4,2,5,1] => 2

[3,4,5,1,2] => 4

[3,4,5,2,1] => 4

[3,5,1,2,4] => 2

[3,5,1,4,2] => 2

>>> Load all 3019 entries. <<<

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 cycles in the breakpoint graph of a permutation.
The breakpoint graph of a permutation $\pi_1,\dots,\pi_n$ is the directed, bicoloured graph with vertices $0,\dots,n$, a grey edge from $i$ to $i+1$ and a black edge from $\pi_i$ to $\pi_{i-1}$ for $0\leq i\leq n$, all indices taken modulo $n+1$.
This graph decomposes into alternating cycles, which this statistic counts.
The distribution of this statistic on permutations of $n-1$ is, according to [cor.1, 5] and [eq.6, 6], given by
$$ \frac{1}{n(n+1)}((q+n)_{n+1}-(q)_{n+1}), $$
where $(x)_n=x(x-1)\dots(x-n+1)$.

References

[1] Grusea, S., Labarre, A. The distribution of cycles in breakpoint graphs of signed permutations arXiv:1104.3353
[2] Alexeev, N., Zograf, P. Hultman numbers, polygon gluings and matrix integrals arXiv:1111.3061
[3] Doignon, J.-P., Labarre, A. On Hultman numbers MathSciNet:2312248
[4] Alexeev, N., Pologova, A., Alekseyev, M. A. Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs arXiv:1503.05285
[5] Bona, M., Flynn, R. The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley arXiv:0811.0740
[6] Stanley, R. P. Two Enumerative Results on Cycles of Permutations arXiv:0901.2008

Code

def statistic(pi):
    return len(Hultman_class(pi))

def Hultman_class(pi):
    """
    sage: Hultman_class([1,2])
    [1, 1, 1]
    sage: Hultman_class([2,1])
    [3]

    sage: Hultman_class([2,3,1,4])
    [3, 1, 1]

    sage: Hultman_class([4,1,6,2,5,7,3])
    [5, 3]

    sage: [len(set([Hultman_class(pi) for pi in Permutations(r)])) for r in range(10)]
    [1, 1, 2, 3, 4, 6, 8, 12, 16, 22]
    """
    n = len(pi)
    grey  = {i: (i+1) % (n+1) for i in range(n+1)}
    pi_list = [0] + list(pi)
    black = {pi_list[i]: pi_list[(i-1) % (n+1)] for i in range(n+1)}

    blocks = []
    size = 0
    start = 0
    odd = 0
    for i in range(n+1):
        even = grey.pop(odd)
        odd = black.pop(even)
        size += 1
        if start == odd:
            blocks.append(size)
            size = 0
            try:
                start = odd = next(iter(grey))
            except StopIteration:
                return Partition(sorted(blocks, reverse=True))
    raise ValueError

Created

Feb 14, 2017 at 17:21 by Martin Rubey

Updated

Dec 03, 2020 at 20:32 by Martin Rubey