Главная > Документ


(Комбинаторика, 5.12.03) Семинар 13.

Мебиус-функция(x,y) частично упорядоченного множества (P, ) определяется по правилу

где x,yP. Чтобы эта рекуррентность была корректной, обычно предполагают, что (P, ) локально конечно, т.е. что

x,yP | {zP :xzy }|=|[x,y]|<;

множество [x,y] называется интервалом или сегментом.

Теоретико-числовая функция Мебиуса определяется как

Задачи

1. Вычислить мебиус-функции следующих частично упорядоченных множеств.

а) (2S,) (булеан)– множество всех подмножеств S, упорядоченное по включению;

b) (D(n), | )– множество всех натуральных делителей числа n, упорядоченных по делимости;

с) (B(Sn), ) (беллиан)– множество всех внутриблочно и поблочно неупорядоченных разбиений (белловских разбиений) множества S={a1,…,an}, упорядоченных по объединению блоков: для 1, 2(B(Sn), ) 1 2 тогда и только тогда, когда всякий блок из 1 содержится в неком блоке из 2;

d) (Vn(q), )– множество всех подпространств n-мерного пространства Vn над конечным полем с q элементами, частично упорядоченное по включению.

Ответ. Если x, y(2S,) и xy, то (x,y)=(–1)|xy |. Для (D(n), | ), если x| y| n, то (x,y)=*(y/x)–классическая теоретико-числовая функция Мебиуса. Для (B(Sn), ), если (B(Sn), ) имеет ровно k блоков, то (,1)=(–1)k–1(k–1)!.

Для (Vn(q), ), если xy Vn(q) ,то (x,y)=(–1)d(y)–d(x), где d(x)–размерность x.

2. Пусть дзета-функция (x,y) частично упорядоченного множества (P, ) определяется по правилу

Доказать, что в смысле сверточного умножения

,

0, если xy,

мебиус-функция является обратной к дзета-функции.

3. Пусть P– локально конечное частично упорядоченное множество, K– поле характеристики нуль. Пусть AK(P)={f: P2K: xyf(x,y)=0}, снабженное операциями поточечного сложения, т.е. (f+g)(x,y)=f(x,y)+g(x,y), умножения на скаляр и свертки. Доказать, что AK(P)–ассоциативная K-алгебра; функция Кронекера  служит в ней двухсторонним нейтральным элементом. AK(P) называется алгебройинцидентности.

Напоминание. Алгеброй над полем K (K-алгеброй) называется множество P с операциями сложения, умножения и умножения на элементы поля K, обладающими свойствами:

  1. относительно сложения и умножения на элементы поля P есть векторное пространство;

  2. относительно сложения и умножения P есть кольцо;

  3. (a)b=a( b)= (ab) для любых K, a,bP.

4. Доказать, что элемент f AK(P) тогда и только тогда, когда является единицей, когда f(x,y)0 для всех xP. У единицы f есть однозначно определенный двухсторонний обратный элемент f–1.

Указание. Определить левый обратный элемент индуктивно.

, .

5. Доказать. Пусть f , g, hAK(P) и пусть h обратимо. Тогда

g=f*hf=g*h–1,

g=h*ff= h–1*g.

6. Доказать принцип обращения Мебиуса: пусть (P, )– локально конечное частично упорядоченное множество с 0, (x,y)– его мебиус-функция и f: PR. Тогда, если

, то .

7. Доказать, что

8. Показать, если (P, )– конечная решетка с 0 и 1, то для ab(P, ) справедливы соотношения

9. Пусть P есть цепь N. Найти (i,j) для i,jN. Показать, что формула обращения Мебиуса принимает вид

10. Доказать. Пусть P и Q – локально конечные частично упорядоченные множества, и PQ–их прямое произведение. Если (x,y) (x,y) в PQ, то

.

11. Пусть AK(P)– алгебра инцидентности локально конечного частично упорядоченного множества P. Показать, что AK(P) коммутативна тогда и только тогда, когда Pнекоторая антицепь.

12. Доказать тождества

,

с помощью принципа включения-исключения.

13. Доказать, что число способов, которым можно выбрать k точек из m точек, стоящих по окружности так, чтобы среди них не было двух последовательных, равно .

14. «Задача о паросочетаниях». За круглым столом нужно рассадить n супружеских пар. Сколькими способами это можно сделать, если требуется, чтобы мужчины и женщины чередовались и чтобы ни один муж не сидел рядом со своей женой.

Указание. Ищем число перестановок s={s(1),…,s(n)} таких, что js(j),s(j1), j=, и 1s(1),s(n). Воспользоваться задачей 13. Ответ: .

15. «Задача мажордома». К обеду за круглым столом приглашены n пар враждующих рыцарей (n2). Требуется рассадить их так, чтобы никакие два врага не сидели рядом. Показать, что это можно сделать способами.



Скачать документ

Похожие документы:

  1. § 1 основные понятия и теоремы пункт 1 деление с остатком

    Документ
    ... множество N \ {1}={2,3,4,...} с отношением делимости есть частичноупорядоченноемножество ... · 3 3 - 1 3 - 1 · 5 2 - 1 5 - 1 = 2418. Пример 3. ФункцияМебиуса. ФункцияМебиуса ( a ) - это мультипликативная функция, определяемая следующим образом: если ...
  2. § 1 основные понятия и теоремы пункт 1 деление с остатком

    Документ
    ... множество N \ {1}={2,3,4,...} с отношением делимости есть частичноупорядоченноемножество ... · 3 3 - 1 3 - 1 · 5 2 - 1 5 - 1 = 2418. Пример 3. ФункцияМебиуса. ФункцияМебиуса ( a ) - это мультипликативная функция, определяемая следующим образом: если ...
  3. Ул 1-го мая 58/23 хмельник винницкая обл 287320 украина

    Книга
    ... , либо творческая функции совпадают с соответствующими функциями данного типа ... сфере с 7 вклеенными пленками Мебиуса (математические детали см., например ... быть классифицированы при помощи (частично - упорядоченного) множества - "спектра состояний СЭС", ...
  4. Основная образовательная программа (99)

    Основная образовательная программа
    ... и исключений. Частичноупорядоченныемножества, их функцииМебиуса и теорема об обращении Мебиуса. Производящие функции. Возвратные последовательности ... Теорема Рамсея. Гиперкуб. Булевы функции. Частичноупорядоченныемножества. Цепи, антицепи. Теорема ...
  5. Основная образовательная программа (231)

    Основная образовательная программа
    ... и исключений. Частичноупорядоченныемножества, их функцииМебиуса и теорема об обращении Мебиуса. Производящие функции. Возвратные последовательности ... Теорема Рамсея. Гиперкуб. Булевы функции. Частичноупорядоченныемножества. Цепи, антицепи. Теорема ...

Другие похожие документы..