Fence (mathematics)

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a fence, also called a zigzag poset, is a <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered set</a> (poset) in which the order <a href="/facts/Relation_(mathematics)/HjblDaMy">relations</a> form a path with alternating orientations:

a
 
 c
 <
 d
 >
 e
 <
 f
 >
 h
 c<d>e<f>h<i\cdots }

or

a
 >
 b
 <
 c
 >
 d
 <
 e
 >
 f
 <
 h
 >
 i
 ⋯
 
 
 {\displaystyle a>b<c>d<e>f<h>i\cdots }

A fence may be <a href="/facts/Finite_set/za1newlP">finite</a>, or it may be formed by an infinite alternating sequence extending in both directions. The <a href="/facts/Incidence_poset/HqHFp5Uo">incidence posets</a> of <a href="/facts/Path_graph/4Y2f35eM">path graphs</a> form examples of fences.
A <a href="/facts/Linear_extension/jKKPR2pn">linear extension</a> of a fence is called an <a href="/facts/Alternating_permutation/Fl7tSe9z">alternating permutation</a>; <a href="/facts/Andr%25C3%25A9%2527s_problem/Fl7tSe9z">André's problem</a> 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.
      
    
    {\displaystyle 1,1,2,4,10,32,122,544,2770,15872,101042.}

(sequence A001250 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>).
The number of <a href="/facts/Antichain/rPuqkKJt">antichains</a> in a fence is a <a href="/facts/Fibonacci_number/mqxpAUQD">Fibonacci number</a>; the <a href="/facts/Distributive_lattice/97DFz1cu">distributive lattice</a> with this many elements, generated from a fence via <a href="/facts/Birkhoff%2527s_representation_theorem/Mg51p9wz">Birkhoff's representation theorem</a>, has as its graph the <a href="/facts/Fibonacci_cube/2dgHmmlm">Fibonacci cube</a>.
A partially ordered set is <a href="/facts/Series-parallel_partial_order/X8VP9aRR">series-parallel</a> if and only if it does not have four elements forming a fence.
Several authors have also investigated the number of <a href="/facts/Order-preserving_map/MjQK0YL2">order-preserving maps</a> from fences to themselves, or to fences of other sizes.
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. For instance, Q(2,9) has the elements and relations

a
 >
 b
 >
 c
 <
 d
 >
 e
 >
 f
 <
 g
 >
 h
 >
 i
 .
 
 
 {\displaystyle 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).

<ul><li>André, Désiré (1881), "Sur les permutations alternées", J. Math. Pures Appl., (Ser. 3), 7: 167–184.</li>
<li>Beck, István (1990), "Partial orders and the Fibonacci numbers", Fibonacci Quarterly, 28 (2): 172–174, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1051291">1051291</a>.</li>
<li>Currie, J. D.; Visentin, T. I. (1991), "The number of order-preserving maps of fences and crowns", <a href="/facts/Order_(journal)/7kF1kG7K">Order</a>, 8 (2): 133–142, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF00383399">10.1007/BF00383399</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/10680%2F1724">10680/1724</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1137906">1137906</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:122356472">122356472</a>.</li>
<li><a href="/facts/Dwight_Duffus/HScwYNC0">Duffus, Dwight</a>; Rödl, Vojtěch; Sands, Bill; Woodrow, Robert (1992), "Enumeration of order preserving maps", <a href="/facts/Order_(journal)/7kF1kG7K">Order</a>, 9 (1): 15–29, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF00419036">10.1007/BF00419036</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1194849">1194849</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:84180809">84180809</a>.</li>
<li>Farley, Jonathan David (1995), "The number of order-preserving maps between fences and crowns", <a href="/facts/Order_(journal)/7kF1kG7K">Order</a>, 12 (1): 5–44, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01108588">10.1007/BF01108588</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1336535">1336535</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:120372679">120372679</a>.</li>
<li>Gansner, Emden R. (1982), "On the lattice of order ideals of an up-down poset", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 39 (2): 113–122, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2882%2990134-0">10.1016/0012-365X(82)90134-0</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0675856">0675856</a>.</li>
<li>Höft, Hartmut; Höft, Margret (1985), "A Fibonacci sequence of distributive lattices", Fibonacci Quarterly, 23 (3): 232–237, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0806293">0806293</a>.</li>
<li>Kelly, David; <a href="/facts/Ivan_Rival/adGRLxnU">Rival, Ivan</a> (1974), "Crowns, fences, and dismantlable lattices", Canadian Journal of Mathematics, 26 (5): 1257–1271, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4153%2Fcjm-1974-120-2">10.4153/cjm-1974-120-2</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0417003">0417003</a>.</li>
<li>Rutkowski, Aleksander (1992a), "The number of strictly increasing mappings of fences", <a href="/facts/Order_(journal)/7kF1kG7K">Order</a>, 9 (1): 31–42, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF00419037">10.1007/BF00419037</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1194850">1194850</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:120965362">120965362</a>.</li>
<li>Rutkowski, Aleksander (1992b), "The formula for the number of order-preserving self-mappings of a fence", <a href="/facts/Order_(journal)/7kF1kG7K">Order</a>, 9 (2): 127–137, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF00814405">10.1007/BF00814405</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1199291">1199291</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:121879635">121879635</a>.</li>
<li>Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), "Alternating unimodal sequences of Whitney numbers", Ars Combinatoria, 87: 105–117, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2414008">2414008</a>.</li>
<li><a href="/facts/Richard_P._Stanley/8bQ4QrLM">Stanley, Richard P.</a> (1986), Enumerative Combinatorics, Wadsworth, Inc. Exercise 3.23a, page 157.</li>
<li>Valdes, Jacobo; <a href="/facts/Robert_Tarjan/kn1pMCN0">Tarjan, Robert E.</a>; <a href="/facts/Eugene_Lawler/pcQgHbej">Lawler, Eugene L.</a> (1982), "The Recognition of Series Parallel Digraphs", <a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a>, 11 (2): 298–313, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0211023">10.1137/0211023</a>.</li></ul>

Fence (mathematics) open-in-new

Fence (mathematics)