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

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

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

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

или

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

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

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

$1,1,2,4,10,32,122,544,2770,15872,101042.$

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

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

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

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

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

$a>b>c<d>e>f<g>h>i.$

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

Ссылки

• Андре, Дезире (1881), «Об знакопеременных перестановках», J. Math. Чистое приложение. , (Сер. 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.23a, стр. 157.
• Вальдес, Хакобо; Тарьян, Роберт Э .; Лоулер, Юджин Л. (1982), «Распознавание рядов параллельных орграфов», SIAM Journal on Computing , 11 (2): 298–313, doi : 10.1137/0211023 .

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

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