HOME

TheInfoList



OR:

In
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: :aceh or :a>bdfi \cdots A fence may be finite, or it may be formed by an infinite alternating sequence extending in both directions. The incidence posets of path graphs form examples of fences. A linear extension 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 antichains 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 maps 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>ce>fh>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