Fence (mathematics)

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a fence, also called a zigzag poset, is a

partially ordered set In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...

(poset) in which the order relations form a path with alternating orientations: :

a

ceh or : $a>b d f i \cdots$ A fence may be
finite Finite may refer to: * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked for person and/or tense or aspect * "Finite", a song by Sara Gr ...
, or it may be formed by an infinite alternating sequence extending in both directions. The incidence posets of
path graph In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
s form examples of fences. A
linear extension In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extensi ...
of a fence is called an alternating permutation; André's problem of counting the number of different linear extensions has been studied since the 19th century. The solutions to this counting problem, the so-called Euler zigzag numbers or up/down numbers, are: : $1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042.$ :. The number of
antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
s in a fence is a
Fibonacci number In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
; the
distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
with this many elements, generated from a fence via
Birkhoff's representation theorem :''This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation).'' In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice ...
, has as its graph the Fibonacci cube. A partially ordered set is series-parallel if and only if it does not have four elements forming a fence. Several authors have also investigated the number of
order-preserving map In mathematics, a monotonic function (or monotone function) is a function (mathematics), function between List of order structures in mathematics, ordered sets that preserves or reverses the given order relation, order. This concept first ar ...
s from fences to themselves, or to fences of other sizes. An up-down poset is a generalization of a zigzag poset in which there are downward orientations for every upward one and total elements.. For instance, has the elements and relations : $a>b>c e>f h>i.$ In this notation, a fence is a partially ordered set of the form .

References
* . * . * . * . * . * . * . * . * . * . * . * Exercise 3.23a, page 157. * .

External links
* {{mathworld, title=Fence Poset, urlname=FencePoset Order theory Enumerative combinatorics