フェンス（数学）

6 要素フェンスのハッセ図。

数学において、フェンスはジグザグ posetとも​​呼ばれ、順序関係が交互の方向を持つパスを形成する 半順序集合(poset) です。

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

または

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

フェンスは有限である場合もあれば、両方向に延びる無限の交互配列によって形成される場合もあります。パスグラフの接続ポセットはフェンスの例です。

柵の線形拡張は交代順列と呼ばれます。異なる線形拡張の数を数えるアンドレの問題は19世紀から研究されてきました。 ^{[ 1 ]}この数え上げ問題の解は、いわゆるオイラージグザグ数またはアップ/ダウン数であり、次のとおりです。

${\displaystyle 1,1,2,4,10,32,122,544,2770,15872,101042.}$

( OEISのシーケンスA001250 )。

フェンス内の反鎖の数はフィボナッチ数である。バーコフの表現定理によってフェンスから生成された、この数の要素を持つ分配格子のグラフはフィボナッチキューブとなる。^{[ 2 ]}

半順序集合が直並列集合となるのは、4つの要素が柵を形成していない場合のみである。^{[ 3 ]}

いくつかの著者は、フェンスからフェンス自体、または他のサイズのフェンスへの順序保存マップの数を調査しました。 ^{[ 4 ]}

上向き半集合 Q ( a , b )はジグザグ半集合の一般化であり、上向きの1つの要素に対してa個の下向きの向きがあり、合計b個の要素がある 。^{[ 5 ]}例えば、Q (2,9)は、

${\displaystyle a>b>c<d>e>f<g>h>i.}$

この表記法では、フェンスはQ (1, n )の形式の半順序集合です。

参考文献

1. アンドレ（1881） .
2. Gansner (1982) はこの格子がフィボナッチ数の元を持つという事実を「周知の事実」と呼んでいるが、 Stanley (1986) は演習問題でその記述を求めている。Höft & Höft (1985)、 Beck (1990)、 Salvi & Salvi (2008)も参照のこと。
3. バルデス、タージャン、ローラー (1982)。
4. カリーとヴィセンティン (1991) ;ダフスら。 (1992) ;ルトコウスキー (1992a) ;ルトコウスキー (1992b) ;ファーリー (1995)。
5. ガンスナー（1982） .

• アンドレ、デジレ (1881)、「Sur les permutations alternées」、J. Math. Pures Appl. 、 （シリーズ 3）、7 : 167–184。
• ベック、イシュトヴァン（1990）「部分順序とフィボナッチ数」、フィボナッチ・クォータリー、28（2）：172-174、doi：10.1080/00150517.1990.12429508、MR  1051291。
• Currie, JD; Visentin, TI (1991)、「柵と樹冠の順序保存写像の数」、Order、8 (2): 133– 142、doi : 10.1007/BF00383399、hdl : 10680/1724、MR  1137906、S2CID  122356472。
• ダフス、ドワイト；レードル、ヴォイチェフ；サンズ、ビル；ウッドロウ、ロバート（1992）「順序保存写像の列挙」、Order、9（1）：15– 29、doi：10.1007/BF00419036、MR  1194849、S2CID  84180809。
• ファーリー、ジョナサン・デイヴィッド（1995）、「フェンスとクラウン間の順序保存写像の数」、Order、12（1）：5– 44、doi：10.1007/BF01108588、MR  1336535、S2CID  120372679。
• ガンスナー、エムデン・R.（1982）「上下ポセットの順序イデアルの格子について」、離散数学、39（2）：113-122、doi：10.1016/0012-365X（82）90134-0、MR  0675856。
• Höft, Hartmut; Höft, Margret (1985)、「分配格子のフィボナッチ数列」、Fibonacci Quarterly、23 (3): 232– 237、doi : 10.1080/00150517.1985.12429817、MR  0806293。
• ケリー、デイビッド；ライバル、アイヴァン（1974）「クラウン、フェンス、そして解体可能な格子」、カナダ数学ジャーナル、26（5）：1257–1271、doi：10.4153/cjm-1974-120-2、MR  0417003。
• Rutkowski, Aleksander (1992a)、「フェンスの厳密に増加するマッピングの数」、Order、9 (1): 31– 42、doi : 10.1007/BF00419037、MR  1194850、S2CID  120965362。
• Rutkowski, Aleksander (1992b)、「フェンスの順序保存自己写像の数の公式」、Order、9 (2): 127– 137、doi : 10.1007/BF00814405、MR  1199291、S2CID  121879635。
• Salvi, Rodolfo; Salvi, Norma Zagaglia (2008)、「ホイットニー数の交互単峰性シーケンス」、Ars Combinatoria、87 : 105–117、MR  2414008。
• スタンレー、リチャード P. (1986)、「列挙的組合せ論」、ワズワース社。演習3.23a、157ページ。
• バルデス、ヤコボ;タージャン、ロバート E.;ローラー、ユージン L. (1982)、「直列並列有向グラフの認識」、SIAM Journal on Computing、11 (2): 298– 313、doi : 10.1137/0211023。

外部リンク

• ワイスタイン、エリック W. 「フェンスポセット」。MathWorld 。