Your data matches 17 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 9 compositions to match this statistic)
Mapping
Mp00069: Permutations —complement⟶ Permutations
St000624: Permutations ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%
Values
[1] => [1] => ? = 1 - 1
[1,2] => [2,1] => 0 = 1 - 1
[2,1] => [1,2] => 0 = 1 - 1
[1,2,3] => [3,2,1] => 0 = 1 - 1
[1,3,2] => [3,1,2] => 0 = 1 - 1
[2,1,3] => [2,3,1] => 1 = 2 - 1
[2,3,1] => [2,1,3] => 0 = 1 - 1
[3,1,2] => [1,3,2] => 1 = 2 - 1
[3,2,1] => [1,2,3] => 0 = 1 - 1
[1,2,3,4] => [4,3,2,1] => 0 = 1 - 1
[1,2,4,3] => [4,3,1,2] => 0 = 1 - 1
[1,3,2,4] => [4,2,3,1] => 1 = 2 - 1
[1,3,4,2] => [4,2,1,3] => 0 = 1 - 1
[1,4,2,3] => [4,1,3,2] => 1 = 2 - 1
[1,4,3,2] => [4,1,2,3] => 0 = 1 - 1
[2,1,3,4] => [3,4,2,1] => 1 = 2 - 1
[2,1,4,3] => [3,4,1,2] => 1 = 2 - 1
[2,3,1,4] => [3,2,4,1] => 1 = 2 - 1
[2,3,4,1] => [3,2,1,4] => 0 = 1 - 1
[2,4,1,3] => [3,1,4,2] => 1 = 2 - 1
[2,4,3,1] => [3,1,2,4] => 0 = 1 - 1
[3,1,2,4] => [2,4,3,1] => 1 = 2 - 1
[3,1,4,2] => [2,4,1,3] => 1 = 2 - 1
[3,2,1,4] => [2,3,4,1] => 1 = 2 - 1
[3,2,4,1] => [2,3,1,4] => 1 = 2 - 1
[3,4,1,2] => [2,1,4,3] => 1 = 2 - 1
[3,4,2,1] => [2,1,3,4] => 0 = 1 - 1
[4,1,2,3] => [1,4,3,2] => 1 = 2 - 1
[4,1,3,2] => [1,4,2,3] => 1 = 2 - 1
[4,2,1,3] => [1,3,4,2] => 1 = 2 - 1
[4,2,3,1] => [1,3,2,4] => 1 = 2 - 1
[4,3,1,2] => [1,2,4,3] => 1 = 2 - 1
[4,3,2,1] => [1,2,3,4] => 0 = 1 - 1
[1,2,3,4,5] => [5,4,3,2,1] => 0 = 1 - 1
[1,2,3,5,4] => [5,4,3,1,2] => 0 = 1 - 1
[1,2,4,3,5] => [5,4,2,3,1] => 1 = 2 - 1
[1,2,4,5,3] => [5,4,2,1,3] => 0 = 1 - 1
[1,2,5,3,4] => [5,4,1,3,2] => 1 = 2 - 1
[1,2,5,4,3] => [5,4,1,2,3] => 0 = 1 - 1
[1,3,2,4,5] => [5,3,4,2,1] => 1 = 2 - 1
[1,3,2,5,4] => [5,3,4,1,2] => 1 = 2 - 1
[1,3,4,2,5] => [5,3,2,4,1] => 1 = 2 - 1
[1,3,4,5,2] => [5,3,2,1,4] => 0 = 1 - 1
[1,3,5,2,4] => [5,3,1,4,2] => 1 = 2 - 1
[1,3,5,4,2] => [5,3,1,2,4] => 0 = 1 - 1
[1,4,2,3,5] => [5,2,4,3,1] => 1 = 2 - 1
[1,4,2,5,3] => [5,2,4,1,3] => 1 = 2 - 1
[1,4,3,2,5] => [5,2,3,4,1] => 1 = 2 - 1
[1,4,3,5,2] => [5,2,3,1,4] => 1 = 2 - 1
[1,4,5,2,3] => [5,2,1,4,3] => 1 = 2 - 1
[1,4,5,3,2] => [5,2,1,3,4] => 0 = 1 - 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 7 statistics, ordered by result quality, also match your data. Click on any of them to see the details.
St001330The hat guessing number of a graph. St001621The number of atoms of a lattice. St001624The breadth of a lattice. St001878The projective dimension of the simple modules corresponding to the minimum of L in the incidence algebra of the lattice L. St001823The Stasinski-Voll length of a signed permutation. St001960The number of descents of a permutation minus one if its first entry is not one. St001582The grades of the simple modules corresponding to the points in the poset of the symmetric group under the Bruhat order.