Your data matches 71 different statistics following compositions of up to 3 maps.
(click to perform a complete search on your data)
Matching statistic: St000822
Mapping
Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St000822: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
 => ([],1)
 => ([],1)
 => 1
[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
Description
The Hadwiger number of the graph. Also known as clique contraction number, this is the size of the largest complete minor.
Matching statistic: St001580
Mapping
Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St001580: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
 => ([],1)
 => ([],1)
 => 1
[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
Description
The acyclic chromatic number of a graph. This is the smallest size of a vertex partition $\{V_1,\dots,V_k\}$ such that each $V_i$ is an independent set and for all $i,j$ the subgraph inducted by $V_i\cup V_j$ does not contain a cycle.
Matching statistic: St001670
Mapping
Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St001670: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
 => ([],1)
 => ([],1)
 => 1
[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
Description
The connected partition number of a graph. This is the maximal number of blocks of a set partition $P$ of the set of vertices of a graph such that contracting each block of $P$ to a single vertex yields a clique. Also called the pseudoachromatic number of a graph. This is the largest $n$ such that there exists a (not necessarily proper) $n$-coloring of the graph so that every two distinct colors are adjacent.
Matching statistic: St001963
Mapping
Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St001963: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
 => ([],1)
 => ([],1)
 => 1
[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2
Description
The tree-depth of a graph. The tree-depth $\operatorname{td}(G)$ of a graph $G$ whose connected components are $G_1,\ldots,G_p$ is recursively defined as $$\operatorname{td}(G)=\begin{cases} 1, & \text{if }|G|=1\\ 1 + \min_{v\in V} \operatorname{td}(G-v), & \text{if } p=1 \text{ and } |G| > 1\\ \max_{i=1}^p \operatorname{td}(G_i), & \text{otherwise} \end{cases}$$ Nešetřil and Ossona de Mendez [2] proved that the tree-depth of a connected graph is equal to its minimum elimination tree height and its centered chromatic number (fewest colors needed for a vertex coloring where every connected induced subgraph has a color that appears exactly once). Tree-depth is strictly greater than [[St000536|pathwidth]]. A [[St001120|longest path]] in $G$ has at least $\operatorname{td}(G)$ vertices [3].
Matching statistic: St000272
Mapping
Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St000272: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
 => ([],1)
 => ([],1)
 => 0 = 1 - 1
[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 0 = 1 - 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 0 = 1 - 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1 = 2 - 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1 = 2 - 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1 = 2 - 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1 = 2 - 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1 = 2 - 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
Description
The treewidth of a graph. A graph has treewidth zero if and only if it has no edges. A connected graph has treewidth at most one if and only if it is a tree. A connected graph has treewidth at most two if and only if it is a series-parallel graph.
Matching statistic: St000362
Mapping
Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St000362: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
 => ([],1)
 => ([],1)
 => 0 = 1 - 1
[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 0 = 1 - 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 0 = 1 - 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1 = 2 - 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1 = 2 - 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1 = 2 - 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1 = 2 - 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1 = 2 - 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
Description
The size of a minimal vertex cover of a graph. A '''vertex cover''' of a graph $G$ is a subset $S$ of the vertices of $G$ such that each edge of $G$ contains at least one vertex of $S$. Finding a minimal vertex cover is an NP-hard optimization problem.
Matching statistic: St000536
Mapping
Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St000536: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
 => ([],1)
 => ([],1)
 => 0 = 1 - 1
[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 0 = 1 - 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 0 = 1 - 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1 = 2 - 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1 = 2 - 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0 = 1 - 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1 = 2 - 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1 = 2 - 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0 = 1 - 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1 = 2 - 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1 = 2 - 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0 = 1 - 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1 = 2 - 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1 = 2 - 1
Description
The pathwidth of a graph.
Matching statistic: St001176
Mapping
Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00110: Posets —Greene-Kleitman invariant⟶ Integer partitions
St001176: Integer partitions ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
 => ([],1)
 => [1]
 => 0 = 1 - 1
[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => [2]
 => 0 = 1 - 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => [2]
 => 0 = 1 - 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0 = 1 - 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0 = 1 - 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => [2,1]
 => 1 = 2 - 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0 = 1 - 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => [2,1]
 => 1 = 2 - 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0 = 1 - 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1 = 2 - 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1 = 2 - 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1 = 2 - 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1 = 2 - 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1 = 2 - 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1 = 2 - 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1 = 2 - 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
Description
The size of a partition minus its first part. This is the number of boxes in its diagram that are not in the first row.
Matching statistic: St001214
Mapping
Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00110: Posets —Greene-Kleitman invariant⟶ Integer partitions
St001214: Integer partitions ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
 => ([],1)
 => [1]
 => 0 = 1 - 1
[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => [2]
 => 0 = 1 - 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => [2]
 => 0 = 1 - 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0 = 1 - 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0 = 1 - 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => [2,1]
 => 1 = 2 - 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0 = 1 - 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => [2,1]
 => 1 = 2 - 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0 = 1 - 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1 = 2 - 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1 = 2 - 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1 = 2 - 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1 = 2 - 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1 = 2 - 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0 = 1 - 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1 = 2 - 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1 = 2 - 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0 = 1 - 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1 = 2 - 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1 = 2 - 1
Description
The aft of an integer partition. The aft is the size of the partition minus the length of the first row or column, whichever is larger. See also [[St000784]].
Matching statistic: St000624
(load all 18 compositions to match this statistic)
Mapping
St000624: Permutations ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => ? = 1 - 1
[1,2] => 0 = 1 - 1
[2,1] => 0 = 1 - 1
[1,2,3] => 0 = 1 - 1
[1,3,2] => 1 = 2 - 1
[2,1,3] => 0 = 1 - 1
[2,3,1] => 1 = 2 - 1
[3,1,2] => 0 = 1 - 1
[3,2,1] => 0 = 1 - 1
[1,2,3,4] => 0 = 1 - 1
[1,2,4,3] => 1 = 2 - 1
[1,3,2,4] => 1 = 2 - 1
[1,3,4,2] => 1 = 2 - 1
[1,4,2,3] => 1 = 2 - 1
[1,4,3,2] => 1 = 2 - 1
[2,1,3,4] => 0 = 1 - 1
[2,1,4,3] => 1 = 2 - 1
[2,3,1,4] => 1 = 2 - 1
[2,3,4,1] => 1 = 2 - 1
[2,4,1,3] => 1 = 2 - 1
[2,4,3,1] => 1 = 2 - 1
[3,1,2,4] => 0 = 1 - 1
[3,1,4,2] => 1 = 2 - 1
[3,2,1,4] => 0 = 1 - 1
[3,2,4,1] => 1 = 2 - 1
[3,4,1,2] => 1 = 2 - 1
[3,4,2,1] => 1 = 2 - 1
[4,1,2,3] => 0 = 1 - 1
[4,1,3,2] => 1 = 2 - 1
[4,2,1,3] => 0 = 1 - 1
[4,2,3,1] => 1 = 2 - 1
[4,3,1,2] => 0 = 1 - 1
[4,3,2,1] => 0 = 1 - 1
[1,2,3,4,5] => 0 = 1 - 1
[1,2,3,5,4] => 1 = 2 - 1
[1,2,4,3,5] => 1 = 2 - 1
[1,2,4,5,3] => 1 = 2 - 1
[1,2,5,3,4] => 2 = 3 - 1
[1,2,5,4,3] => 2 = 3 - 1
[1,3,2,4,5] => 1 = 2 - 1
[1,3,2,5,4] => 2 = 3 - 1
[1,3,4,2,5] => 1 = 2 - 1
[1,3,4,5,2] => 1 = 2 - 1
[1,3,5,2,4] => 2 = 3 - 1
[1,3,5,4,2] => 2 = 3 - 1
[1,4,2,3,5] => 1 = 2 - 1
[1,4,2,5,3] => 2 = 3 - 1
[1,4,3,2,5] => 1 = 2 - 1
[1,4,3,5,2] => 2 = 3 - 1
[1,4,5,2,3] => 2 = 3 - 1
[1,4,5,3,2] => 2 = 3 - 1
Description
The normalized sum of the minimal distances to a greater element. Set $\pi_0 = \pi_{n+1} = n+1$, then this statistic is $$ \sum_{i=1}^n \min_d(\pi_{i-1-d}>\pi_i\text{ or }\pi_{i+1+d}>\pi_i) $$ A closely related statistic appears in [1]. The generating function for the sequence of maximal values attained on $\mathfrak S_r$, $r\geq 0$ apparently satisfies the functional equation $$ (x-1)^2 (x+1)^3 f(x^2) - (x-1)^2 (x+1) f(x) + x^3 = 0. $$
The following 61 statistics, ordered by result quality, also match your data. Click on any of them to see the details.
St001907The number of Bastidas - Hohlweg - Saliola excedances of a signed permutation. St000264The girth of a graph, which is not a tree. St001330The hat guessing number of a graph. St001060The distinguishing index of a graph. St000454The largest eigenvalue of a graph if it is integral. St000771The largest multiplicity of a distance Laplacian eigenvalue in a connected graph. St000455The second largest eigenvalue of a graph if it is integral. St000260The radius of a connected graph. St000456The monochromatic index of a connected graph. St000993The multiplicity of the largest part of an integer partition. St001568The smallest positive integer that does not appear twice in the partition. St001597The Frobenius rank of a skew partition. St001630The global dimension of the incidence algebra of the lattice over the rational numbers. St001878The projective dimension of the simple modules corresponding to the minimum of L in the incidence algebra of the lattice L. St000318The number of addable cells of the Ferrers diagram of an integer partition. St001124The multiplicity of the standard representation in the Kronecker square corresponding to a partition. St000772The multiplicity of the largest distance Laplacian eigenvalue in a connected graph. St001864The number of excedances of a signed permutation. St001960The number of descents of a permutation minus one if its first entry is not one. St000298The order dimension or Dushnik-Miller dimension of a poset. St000632The jump number of the poset. St000640The rank of the largest boolean interval in a poset. St001896The number of right descents of a signed permutations. St000307The number of rowmotion orbits of a poset. St001624The breadth of a lattice. St001621The number of atoms of a lattice. St001487The number of inner corners of a skew partition. St001200The number of simple modules in $eAe$ with projective dimension at most 2 in the corresponding Nakayama algebra $A$ with minimal faithful projective-injective module $eA$. St001632The number of indecomposable injective modules $I$ with $dim Ext^1(I,A)=1$ for the incidence algebra A of a poset. St001820The size of the image of the pop stack sorting operator. St000777The number of distinct eigenvalues of the distance Laplacian of a connected graph. St001645The pebbling number of a connected graph. St000259The diameter of a connected graph. St000302The determinant of the distance matrix of a connected graph. St000466The Gutman (or modified Schultz) index of a connected graph. St000467The hyper-Wiener index of a connected graph. St001875The number of simple modules with projective dimension at most 1. St000633The size of the automorphism group of a poset. St000910The number of maximal chains of minimal length in a poset. St000914The sum of the values of the Möbius function of a poset. St001105The number of greedy linear extensions of a poset. St001106The number of supergreedy linear extensions of a poset. St001890The maximum magnitude of the Möbius function of a poset. St001876The number of 2-regular simple modules in the incidence algebra of the lattice. St001823The Stasinski-Voll length of a signed permutation. St001946The number of descents in a parking function. St001569The maximal modular displacement of a permutation. St001773The number of minimal elements in Bruhat order not less than the signed permutation. St001905The number of preferred parking spots in a parking function less than the index of the car. St001935The number of ascents in a parking function. St001582The grades of the simple modules corresponding to the points in the poset of the symmetric group under the Bruhat order. St001860The number of factors of the Stanley symmetric function associated with a signed permutation. St001603The number of colourings of a polygon such that the multiplicities of a colour are given by a partition. St001574The minimal number of edges to add or remove to make a graph regular. St001576The minimal number of edges to add or remove to make a graph vertex transitive. St001742The difference of the maximal and the minimal degree in a graph. St000036The evaluation at 1 of the Kazhdan-Lusztig polynomial with parameters given by the identity and the permutation. St000408The number of occurrences of the pattern 4231 in a permutation. St000440The number of occurrences of the pattern 4132 or of the pattern 4231 in a permutation. St001570The minimal number of edges to add to make a graph Hamiltonian. St001491The number of indecomposable projective-injective modules in the algebra corresponding to a subset.