Забор (математика)

Частично упорядоченный набор с попеременно связанными элементами

Схема Хассе шестиэлементного забора.

В математике забор , также называемый зигзагообразным посетом , представляет собой частично упорядоченное множество (посет) , в котором отношения порядка образуют путь с чередующимися ориентациями:

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

или

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

Забор может быть конечным или представлять собой бесконечную чередующуюся последовательность, простирающуюся в обоих направлениях. Части инцидентности графов путей образуют примеры ограждений.

Линейное продолжение забора называется знакопеременной перестановкой ; Задача Андре о подсчете числа различных линейных расширений изучается с XIX века. ^[1] Решениями этой задачи подсчета, так называемыми зигзагообразными числами Эйлера или числами вверх/вниз, являются:

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

(последовательность A001250 в OEIS ).

Число антицепей в заборе — это число Фибоначчи ; Дистрибутивная решетка с таким количеством элементов, созданная из ограждения с помощью теоремы о представлении Биркгофа , имеет в качестве графика куб Фибоначчи . ^[2]

Частично упорядоченное множество является последовательно-параллельным тогда и только тогда, когда в нем нет четырех элементов, образующих ограждение. ^[3]

Некоторые авторы также исследовали количество сохраняющих порядок карт от заборов до самих себя или до заборов других размеров. ^[4]

ЧУ -множество вверх-вниз Q ( a , b ) является обобщением зигзагообразного ЧУУ, в котором есть направленность вниз для каждого восходящего элемента и всего b элементов. ^[5] Например, Q (2,9) имеет элементы и соотношения

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

В этих обозначениях забор — это частично упорядоченное множество вида Q (1, n ) .

Рекомендации

1. Андре (1881).
2. Ганснер (1982) называет тот факт, что эта решетка имеет число элементов Фибоначчи, «хорошо известным фактом», а Стэнли (1986) просит описать его в упражнении. См. также Höft & Höft (1985), Beck (1990) и Salvi & Salvi (2008).
3. Вальдес, Тарьян и Лоулер (1982).
4. Карри и Висентин (1991); Даффус и др. (1992); Рутковский (1992а); Рутковский (1992b); Фарли (1995).
5. Ганснер (1982).

• Андре, Дезире (1881), «Сюр-ль-альтернативные перестановки», J. Math. Приложение Pures. , (Сер. 3), 7 : 167–184..
• Бек, Иштван (1990), «Частичные порядки и числа Фибоначчи», Fibonacci Quarterly , 28 (2): 172–174, MR  1051291.
• Карри, доктор юридических наук; Висентин, Т.И. (1991), «Количество сохраняющих порядок карт заборов и корон», Приказ , 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.
• Ганснер, Эмден Р. (1982), «О решетке идеалов порядка частично упорядоченного множества вверх-вниз», Discrete Mathematics , 39 (2): 113–122, doi : 10.1016/0012-365X(82)90134-0 , МР  0675856.
• Хёфт, Хартмут; Хёфт, Маргрет (1985), «Последовательность Фибоначчи дистрибутивных решеток», Fibonacci Quarterly , 23 (3): 232–237, MR  0806293.
• Келли, Дэвид; Соперник, Иван (1974), «Короны, заборы и разборные решетки», Canadian Journal of Mathematics , 26 (5): 1257–1271, doi : 10.4153/cjm-1974-120-2 , MR  0417003.
• Рутковский, Александр (1992a), «Число строго возрастающих отображений заборов», Порядок , 9 (1): 31–42, doi : 10.1007/BF00419037, MR  1194850, S2CID  120965362.
• Рутковский, Александр (1992b), «Формула для числа сохраняющих порядок самоотображений забора», Order , 9 (2): 127–137, doi : 10.1007/BF00814405, MR  1199291, S2CID  121879635.
• Сальви, Родольфо; Сальви, Норма Загалья (2008), «Перемежающиеся унимодальные последовательности чисел Уитни», Ars Combinatoria , 87 : 105–117, MR  2414008.
• Стэнли, Ричард П. (1986), Перечислительная комбинаторика , Wadsworth, Inc.Упражнение 3.23а, стр. 157.
• Вальдес, Хакобо; Тарьян, Роберт Э .; Лоулер, Юджин Л. (1982), «Распознавание серий параллельных орграфов», SIAM Journal on Computing , 11 (2): 298–313, doi : 10.1137/0211023.

Внешние ссылки

• Вайсштейн, Эрик В. «Забор Посет». Математический мир .