- FindStat

edit this statistic or download as text // json

Identifier

St001051: Set partitions ⟶ ℤ

Values

{{1}} => 1

{{1,2}} => 1

{{1},{2}} => 2

{{1,2,3}} => 1

{{1,2},{3}} => 2

{{1,3},{2}} => 1

{{1},{2,3}} => 2

{{1},{2},{3}} => 3

{{1,2,3,4}} => 1

{{1,2,3},{4}} => 2

{{1,2,4},{3}} => 1

{{1,2},{3,4}} => 2

{{1,2},{3},{4}} => 3

{{1,3,4},{2}} => 1

{{1,3},{2,4}} => 2

{{1,3},{2},{4}} => 2

{{1,4},{2,3}} => 1

{{1},{2,3,4}} => 2

{{1},{2,3},{4}} => 3

{{1,4},{2},{3}} => 1

{{1},{2,4},{3}} => 3

{{1},{2},{3,4}} => 2

{{1},{2},{3},{4}} => 4

{{1,2,3,4,5}} => 1

{{1,2,3,4},{5}} => 2

{{1,2,3,5},{4}} => 1

{{1,2,3},{4,5}} => 2

{{1,2,3},{4},{5}} => 3

{{1,2,4,5},{3}} => 1

{{1,2,4},{3,5}} => 2

{{1,2,4},{3},{5}} => 2

{{1,2,5},{3,4}} => 1

{{1,2},{3,4,5}} => 2

{{1,2},{3,4},{5}} => 3

{{1,2,5},{3},{4}} => 1

{{1,2},{3,5},{4}} => 3

{{1,2},{3},{4,5}} => 2

{{1,2},{3},{4},{5}} => 4

{{1,3,4,5},{2}} => 1

{{1,3,4},{2,5}} => 2

{{1,3,4},{2},{5}} => 2

{{1,3,5},{2,4}} => 1

{{1,3},{2,4,5}} => 2

{{1,3},{2,4},{5}} => 3

{{1,3,5},{2},{4}} => 1

{{1,3},{2,5},{4}} => 3

{{1,3},{2},{4,5}} => 2

{{1,3},{2},{4},{5}} => 3

{{1,4,5},{2,3}} => 1

{{1,4},{2,3,5}} => 2

{{1,4},{2,3},{5}} => 2

{{1,5},{2,3,4}} => 1

{{1},{2,3,4,5}} => 2

{{1},{2,3,4},{5}} => 3

{{1,5},{2,3},{4}} => 1

{{1},{2,3,5},{4}} => 3

{{1},{2,3},{4,5}} => 2

{{1},{2,3},{4},{5}} => 4

{{1,4,5},{2},{3}} => 1

{{1,4},{2,5},{3}} => 2

{{1,4},{2},{3,5}} => 2

{{1,4},{2},{3},{5}} => 2

{{1,5},{2,4},{3}} => 1

{{1},{2,4,5},{3}} => 2

{{1},{2,4},{3,5}} => 3

{{1},{2,4},{3},{5}} => 4

{{1,5},{2},{3,4}} => 1

{{1},{2,5},{3,4}} => 3

{{1},{2},{3,4,5}} => 2

{{1},{2},{3,4},{5}} => 3

{{1,5},{2},{3},{4}} => 1

{{1},{2,5},{3},{4}} => 4

{{1},{2},{3,5},{4}} => 2

{{1},{2},{3},{4,5}} => 3

{{1},{2},{3},{4},{5}} => 5

{{1,2,3,4,5,6}} => 1

{{1,2,3,4,5},{6}} => 2

{{1,2,3,4,6},{5}} => 1

{{1,2,3,4},{5,6}} => 2

{{1,2,3,4},{5},{6}} => 3

{{1,2,3,5,6},{4}} => 1

{{1,2,3,5},{4,6}} => 2

{{1,2,3,5},{4},{6}} => 2

{{1,2,3,6},{4,5}} => 1

{{1,2,3},{4,5,6}} => 2

{{1,2,3},{4,5},{6}} => 3

{{1,2,3,6},{4},{5}} => 1

{{1,2,3},{4,6},{5}} => 3

{{1,2,3},{4},{5,6}} => 2

{{1,2,3},{4},{5},{6}} => 4

{{1,2,4,5,6},{3}} => 1

{{1,2,4,5},{3,6}} => 2

{{1,2,4,5},{3},{6}} => 2

{{1,2,4,6},{3,5}} => 1

{{1,2,4},{3,5,6}} => 2

{{1,2,4},{3,5},{6}} => 3

{{1,2,4,6},{3},{5}} => 1

{{1,2,4},{3,6},{5}} => 3

{{1,2,4},{3},{5,6}} => 2

{{1,2,4},{3},{5},{6}} => 3

{{1,2,5,6},{3,4}} => 1

>>> Load all 1503 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 depth of the label 1 in the decreasing labelled unordered tree associated with the set partition.
The bijection between set partitions of $\{1,\dots,n\}$ into $k$ blocks and trees with $n+1-k$ leaves is described in Theorem 1 of [1].

References

[1] Erdős, Péter L., Székely, L. A. Applications of antilexicographic order. I. An enumerative theory of trees MathSciNet:1023945

Code

def statistic(p):
    return depth_of_1(set_partition_to_tree(p))

def depth_of_1(T):
    if T.label() == 1:
        return 0
    if T.node_number() == 1:
        return infinity
    else:
        return 1 + min(depth_of_1(C) for C in T)

def set_partition_to_tree(p):
    # the children of the smallest label are the largest remaining
    # element and its partner
    trees = [LabelledRootedTree([LabelledRootedTree([], label=e) for e in b]) for b in p]
    max_label = p.size()+1-len(p) # last labelled node
    while len(trees) > 1:
        max_label += 1
        # find tree with smallest child and all children smaller than max_label
        A = sorted([T for T in trees if max(C.label() for C in T) < max_label],
                   key = lambda T: min(C.label() for C in T))[0]
        trees.remove(A)
        # give it's root node the new label
        A = LabelledRootedTree(A, label=max_label)
        # find tree with child having label max_label
        B = (T for T in trees
             if any(C.label() == max_label for C in T)).next()
        trees.remove(B)

        # replace the child of B carrying max_label with A
        C = LabelledRootedTree([A] + [T for T in B if T.label() != max_label])

        trees.append(C)

    return trees[0]

Created

Nov 18, 2017 at 18:23 by Martin Rubey

Updated

Apr 03, 2018 at 21:07 by Martin Rubey