edit this statistic or download as text // json
Identifier
Values
=>
Cc0002;cc-rep
[]=>0 [1]=>1 [2]=>1 [1,1]=>1 [3]=>1 [2,1]=>2 [1,1,1]=>1 [4]=>1 [3,1]=>2 [2,2]=>2 [2,1,1]=>2 [1,1,1,1]=>1 [5]=>1 [4,1]=>2 [3,2]=>2 [3,1,1]=>2 [2,2,1]=>2 [2,1,1,1]=>2 [1,1,1,1,1]=>1 [6]=>1 [5,1]=>2 [4,2]=>2 [4,1,1]=>2 [3,3]=>2 [3,2,1]=>3 [3,1,1,1]=>2 [2,2,2]=>2 [2,2,1,1]=>2 [2,1,1,1,1]=>2 [1,1,1,1,1,1]=>1 [7]=>1 [6,1]=>2 [5,2]=>2 [5,1,1]=>2 [4,3]=>2 [4,2,1]=>3 [4,1,1,1]=>2 [3,3,1]=>3 [3,2,2]=>3 [3,2,1,1]=>3 [3,1,1,1,1]=>2 [2,2,2,1]=>2 [2,2,1,1,1]=>2 [2,1,1,1,1,1]=>2 [1,1,1,1,1,1,1]=>1 [8]=>1 [7,1]=>2 [6,2]=>2 [6,1,1]=>2 [5,3]=>2 [5,2,1]=>3 [5,1,1,1]=>2 [4,4]=>2 [4,3,1]=>3 [4,2,2]=>3 [4,2,1,1]=>3 [4,1,1,1,1]=>2 [3,3,2]=>3 [3,3,1,1]=>3 [3,2,2,1]=>3 [3,2,1,1,1]=>3 [3,1,1,1,1,1]=>2 [2,2,2,2]=>2 [2,2,2,1,1]=>2 [2,2,1,1,1,1]=>2 [2,1,1,1,1,1,1]=>2 [1,1,1,1,1,1,1,1]=>1 [9]=>1 [8,1]=>2 [7,2]=>2 [7,1,1]=>2 [6,3]=>2 [6,2,1]=>3 [6,1,1,1]=>2 [5,4]=>2 [5,3,1]=>3 [5,2,2]=>3 [5,2,1,1]=>3 [5,1,1,1,1]=>2 [4,4,1]=>3 [4,3,2]=>3 [4,3,1,1]=>3 [4,2,2,1]=>3 [4,2,1,1,1]=>3 [4,1,1,1,1,1]=>2 [3,3,3]=>3 [3,3,2,1]=>3 [3,3,1,1,1]=>3 [3,2,2,2]=>3 [3,2,2,1,1]=>3 [3,2,1,1,1,1]=>3 [3,1,1,1,1,1,1]=>2 [2,2,2,2,1]=>2 [2,2,2,1,1,1]=>2 [2,2,1,1,1,1,1]=>2 [2,1,1,1,1,1,1,1]=>2 [1,1,1,1,1,1,1,1,1]=>1 [10]=>1 [9,1]=>2 [8,2]=>2 [8,1,1]=>2 [7,3]=>2 [7,2,1]=>3 [7,1,1,1]=>2 [6,4]=>2 [6,3,1]=>3 [6,2,2]=>3 [6,2,1,1]=>3 [6,1,1,1,1]=>2 [5,5]=>2 [5,4,1]=>3 [5,3,2]=>3 [5,3,1,1]=>3 [5,2,2,1]=>3 [5,2,1,1,1]=>3 [5,1,1,1,1,1]=>2 [4,4,2]=>3 [4,4,1,1]=>3 [4,3,3]=>3 [4,3,2,1]=>4 [4,3,1,1,1]=>3 [4,2,2,2]=>3 [4,2,2,1,1]=>3 [4,2,1,1,1,1]=>3 [4,1,1,1,1,1,1]=>2 [3,3,3,1]=>3 [3,3,2,2]=>3 [3,3,2,1,1]=>3 [3,3,1,1,1,1]=>3 [3,2,2,2,1]=>3 [3,2,2,1,1,1]=>3 [3,2,1,1,1,1,1]=>3 [3,1,1,1,1,1,1,1]=>2 [2,2,2,2,2]=>2 [2,2,2,2,1,1]=>2 [2,2,2,1,1,1,1]=>2 [2,2,1,1,1,1,1,1]=>2 [2,1,1,1,1,1,1,1,1]=>2 [1,1,1,1,1,1,1,1,1,1]=>1 [6,5]=>2 [5,5,1]=>3 [5,4,2]=>3 [5,4,1,1]=>3 [5,3,3]=>3 [5,3,2,1]=>4 [5,3,1,1,1]=>3 [5,2,2,2]=>3 [5,2,2,1,1]=>3 [4,4,3]=>3 [4,4,2,1]=>4 [4,4,1,1,1]=>3 [4,3,3,1]=>4 [4,3,2,2]=>4 [4,3,2,1,1]=>4 [4,2,2,2,1]=>3 [3,3,3,2]=>3 [3,3,3,1,1]=>3 [3,3,2,2,1]=>3 [3,2,2,2,2]=>3 [2,2,2,2,2,1]=>2 [6,6]=>2 [6,4,2]=>3 [5,5,2]=>3 [5,4,3]=>3 [5,4,2,1]=>4 [5,4,1,1,1]=>3 [5,3,3,1]=>4 [5,3,2,2]=>4 [5,3,2,1,1]=>4 [5,2,2,2,1]=>3 [4,4,4]=>3 [4,4,3,1]=>4 [4,4,2,2]=>4 [4,4,2,1,1]=>4 [4,3,3,2]=>4 [4,3,3,1,1]=>4 [4,3,2,2,1]=>4 [3,3,3,3]=>3 [3,3,3,2,1]=>3 [3,3,2,2,2]=>3 [3,3,2,2,1,1]=>3 [2,2,2,2,2,2]=>2 [5,5,3]=>3 [5,4,4]=>3 [5,4,3,1]=>4 [5,4,2,2]=>4 [5,4,2,1,1]=>4 [5,3,3,2]=>4 [5,3,3,1,1]=>4 [5,3,2,2,1]=>4 [4,4,4,1]=>4 [4,4,3,2]=>4 [4,4,3,1,1]=>4 [4,4,2,2,1]=>4 [4,3,3,3]=>4 [4,3,3,2,1]=>4 [3,3,3,3,1]=>3 [3,3,3,2,2]=>3 [5,5,4]=>3 [5,4,3,2]=>4 [5,4,3,1,1]=>4 [5,4,2,2,1]=>4 [5,3,3,2,1]=>4 [4,4,4,2]=>4 [4,4,3,3]=>4 [4,4,3,2,1]=>4 [3,3,3,3,2]=>3 [5,5,5]=>3 [5,4,3,2,1]=>5 [4,4,4,3]=>4 [3,3,3,3,3]=>3 [7,5,3,1]=>4 [4,4,4,4]=>4 [7,5,4,3,1]=>5 [6,5,4,3,2,1]=>6 [11,7,5,1]=>4 [9,7,5,3,1]=>5 [7,6,5,4,3,2,1]=>7 [9,7,5,5,3,1]=>6 [11,9,7,5,3,1]=>6 [11,8,7,5,4,1]=>6 [8,7,6,5,4,3,2,1]=>8 [11,9,7,6,5,3,1]=>7 [13,11,9,7,5,3,1]=>7 [13,11,9,7,7,5,3,1]=>8 [17,13,11,9,7,5,1]=>7 [15,13,11,9,7,5,3,1]=>8 [29,23,19,17,13,11,7,1]=>8
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 side length of the largest staircase partition fitting into a partition.
For an integer partition $(\lambda_1\geq \lambda_2\geq\dots)$ this is the largest integer $k$ such that $\lambda_i > k-i$ for $i\in\{1,\dots,k\}$.
In other words, this is the length of a longest (strict) north-east chain of cells in the Ferrers diagram of the partition, using the English convention. Equivalently, this is the maximal number of non-attacking rooks that can be placed on the Ferrers diagram.
This is also the maximal number of occurrences of a colour in a proper colouring of a Ferrers diagram.
A colouring of a Ferrers diagram is proper if no two cells in a row or in a column have the same colour. The minimal number of colours needed is the maximum of the length and the first part of the partition, because we can restrict a latin square to the shape. We can associate to each colouring the integer partition recording how often each colour is used, see [1]. This statistic records the largest part occurring in any of these partitions.
References
[1] Chow, T. Coloring a Ferrers diagram MathOverflow:203962
[2] wikipedia:Rook_polynomial
Code
def statistic(la):
    return min(p + i for i, p in enumerate(la + [0]))

def Ferrers_graph(mu):
    """Return the graph with vertices being the cells of the Ferrers
    diagram, two vertices are connected if the cells are in the same
    row or column.

    """
    V = mu.cells()
    G = Graph([V, lambda a,b: a[0] == b[0] or a[1] == b[1]], loops=False, multiedges=False)
    return G

@cached_function
def all_colouring_partitions(mu):
    if len(mu) > mu[0]:
        return all_colouring_partitions(mu.conjugate())
    
    from sage.graphs.graph_coloring import all_graph_colorings
    res = dict()
    for c in all_graph_colorings(Ferrers_graph(mu), max(mu[0], len(mu))):
        la = Partition(sorted((len(v) for v in c.values()), reverse=True))
        res[la] = res.get(la, 0) + 1
    return res

def statistic_alternative(mu):
    mu = Partition(mu)
    return max(la[0] for la in all_colouring_partitions(mu))
Created
Apr 19, 2017 at 10:21 by Martin Rubey
Updated
Dec 22, 2020 at 13:56 by Martin Rubey