In mathematics, a fence, also called a zigzag poset, is a partially ordered set in which the order relations form a path with alternating orientations:
- a < b > c < d > e < f > h < i ...
or
- a > b < c > d < e > f < h > i ...
A fence may be finite, or it may be formed by an infinite alternating sequence extending in both directions.
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.[1] The solutions to this counting problem, the so-called Euler zigzag numbers or up/down numbers, are
The number of antichains in a fence is a Fibonacci number; the distributive lattice with this many elements, generated from a fence via Birkhoff's representation theorem, has as its graph the Fibonacci cube.[2]
Several authors have also investigated the number of order-preserving maps from fences to themselves, or to fences of other sizes.[3]
An up-down poset Q(a,b) is a generalization of a zigzag poset in which there are a downward orientations for every upward one and b total elements.[4] For instance, Q(2,9) has the elements and relations
- a > b > c < d > e > f < g > h > i.
In this notation, a fence is a partially ordered set of the form Q(1,n).
Notes
- ^ André (1881).
- ^ Gansner (1982) calls the fact that this lattice has a Fibonacci number of elements a “well known fact,” while Stanley (1986) asks for a description of it in an exercise. See also Höft & Höft (1985), Beck (1990), and Salvi & Salvi (2008).
- ^ Currie & Visentin (1991); Duffus et al. (1992); Rutkowski (1992a); Rutkowski (1992b); Farley (1995).
- ^ Gansner (1982).
References
- André, D. (1881), "Sur les permutations alternées", J. Math. Pures Appl. (Ser. 3) 7: 167–184.
- Beck, István (1990), "Partial orders and the Fibonacci numbers", Fibonacci Quarterly 28 (2): 172–174, MR1051291.
- Currie, J. D.; Visentin, T. I. (1991), "The number of order-preserving maps of fences and crowns", Order 8 (2): 133–142, doi:, MR1137906.
- Duffus, Dwight; Rödl, Vojtěch; Sands, Bill; Woodrow, Robert (1992), "Enumeration of order preserving maps", Order 9 (1): 15–29, doi:, MR1194849.
- Farley, Jonathan David (1995), "The number of order-preserving maps between fences and crowns", Order 12 (1): 5–44, doi:, MR1336535.
- Gansner, Emden R. (1982), "On the lattice of order ideals of an up-down poset", Discrete Mathematics 39 (2): 113–122, doi:, MR675856.
- Höft, Hartmut; Höft, Margret (1985), "A Fibonacci sequence of distributive lattices", Fibonacci Quarterly 23 (3): 232–237, MR806293.
- Kelly, David; Rival, Ivan (1974), "Crowns, fences, and dismantlable lattices", Canadian Journal of Mathematics. Journal Canadien de Mathématiques 26: 1257–1271, MR0417003.
- Rutkowski, Aleksander (1992a), "The number of strictly increasing mappings of fences", Order 9 (1): 31–42, doi:, MR1194850.
- Rutkowski, Aleksander (1992b), "The formula for the number of order-preserving self-mappings of a fence", Order 9 (2): 127–137, doi:, MR1199291.
- Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), "Alternating unimodal sequences of Whitney numbers", Ars Combinatoria 87: 105–117, MR2414008.
- Stanley, Richard P. (1986), Enumerative Combinatorics, Wadsworth, Inc. Exercise 3.23a, page 157.
External links
- Weisstein, Eric W., "Fence Poset" from MathWorld.
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
