- FindStat

edit this statistic or download as text // json

Identifier

St001767: Integer partitions ⟶ ℤ

Values

[1] => 0

[2] => 1

[1,1] => 1

[3] => 1

[2,1] => 0

[1,1,1] => 1

[4] => 2

[3,1] => 1

[2,2] => 1

[2,1,1] => 1

[1,1,1,1] => 2

[5] => 2

[4,1] => 1

[3,2] => 1

[3,1,1] => 1

[2,2,1] => 1

[2,1,1,1] => 1

[1,1,1,1,1] => 2

[6] => 3

[5,1] => 1

[4,2] => 1

[4,1,1] => 1

[3,3] => 1

[3,2,1] => 1

[3,1,1,1] => 1

[2,2,2] => 1

[2,2,1,1] => 1

[2,1,1,1,1] => 1

[1,1,1,1,1,1] => 3

[7] => 3

[6,1] => 1

[5,2] => 1

[5,1,1] => 2

[4,3] => 1

[4,2,1] => 1

[4,1,1,1] => 1

[3,3,1] => 1

[3,2,2] => 1

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

[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] => 3

[8] => 4

[7,1] => 1

[6,2] => 2

[6,1,1] => 2

[5,3] => 2

[5,2,1] => 1

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

[4,4] => 2

[4,3,1] => 1

[4,2,2] => 1

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

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

[3,3,2] => 1

[3,3,1,1] => 1

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

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

[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] => 1

[1,1,1,1,1,1,1,1] => 4

[9] => 4

[8,1] => 1

[7,2] => 2

[7,1,1] => 2

[6,3] => 2

[6,2,1] => 1

[6,1,1,1] => 2

[5,4] => 2

[5,3,1] => 1

[5,2,2] => 1

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

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

[4,4,1] => 1

[4,3,2] => 1

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

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

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

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

[3,3,3] => 1

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

[3,3,1,1,1] => 1

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

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

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

[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] => 1

[1,1,1,1,1,1,1,1,1] => 4

[10] => 5

[9,1] => 1

[8,2] => 2

[8,1,1] => 2

[7,3] => 2

>>> Load all 1200 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 largest minimal number of arrows pointing to a cell in the Ferrers diagram in any assignment.
Assign to each cell of the Ferrers diagram an arrow pointing north, east, south or west. Then compute for each cell the number of arrows pointing towards it, and take the minimum of those. This statistic is the maximal minimum that can be obtained by assigning arrows in any way.

References

[1] JetfiRex More precise bound for the maximin number of arrows pointing to a square when square grid is filled with arrows MathOverflow:414328

Code

def statistic(la):
    prog = MixedIntegerLinearProgram(maximization=True)
    arrow = prog.new_variable(binary=True, indices=[(i, j, v)
                                                    for v in range(4)
                                                    for i in range(len(la))
                                                    for j in range(la[i])])
    pointed_at = prog.new_variable(integer=True, indices=[(i, j)
                                                          for i in range(len(la))
                                                          for j in range(la[i])])
    min_value = prog.new_variable(integer=True)
    prog.set_objective(min_value[0])    
    # 0 right
    # 1 left
    # 2 down
    # 3 up
    for i in range(len(la)):
        for j in range(la[i]):
            # every cell contains exactly an arrow:
            prog.add_constraint(prog.sum(arrow[(i, j, v)] for v in range(4)) == 1)
            # pointed_at contains the number of arrows pointing to (i, j)
            i_max = max(i1+1 for i1 in range(len(la)) if la[i1] > j)
            prog.add_constraint(pointed_at[i, j] ==
                                sum(arrow[(i, j1, 0)] for j1 in range(j))
                                + sum(arrow[(i, j1, 1)] for j1 in range(j+1, la[i]))
                                + sum(arrow[(i1, j, 2)] for i1 in range(i))
                                + sum(arrow[(i1, j, 3)] for i1 in range(i+1, i_max)))
            # min_value contains the minimal value of all cells
            prog.add_constraint(min_value[0] <= pointed_at[i, j])
    return ZZ(prog.solve())

Created

Jan 24, 2022 at 15:52 by Martin Rubey

Updated

Jan 24, 2022 at 15:52 by Martin Rubey