Аспекти на комбинаториката

Комбинаториката разглежда задачи за разполагане и преброяване на математически обекти и използва идеи от геометрията, алгебрата и анализа. Разнообразието на приложението на тази дисциплина е удивително - теория на кодирането, криптография, сложност на алгоритми, теория на вероятностите. С това тя е неотменима част от образованието на специалисти в области като математика, информатика, физика, биологически науки, химия, икономика.

Книгата се основава на курсове по комбинаторика в Нов български университет и Факултета по математика и информатика на Софийски университет Свети Климент Охридски, както и на лекции, изнесени при подготовката на националните отбори за Международните олимпиади по математика. Тя е насочена към студенти по математика и информатика, но може да представлява интерес за всички, занимаващи се с проблеми от дискретната математика. Голяма част от материала е достъпен и за ученици от горния гимназиален курс.

Проф. Иван Ланджев е преподавател в департамент Информатика на Нов български университет и изследовател в Института по математика и информатика на БАН. Той е кандидат на математическите науки (1990) и доктор на математическите науки (2000). Специализирал е в Техническия университет - Мюнхен и в Университета на Салфорд като стипендиант на DAAD, Alexander von Humboldt Stiftung и The Royal Society. Бил е гост-професор в Мичиганския технически университет, Техническия университет - Мюнхен, Университета на Байройт, Университета на Гент, Университета на Чжъцзян. Научните му интереси са в областта на теорията на кодирането, криптографията, теорията на дизайните, крайните геометрии и теорията на графите. Автор е на над 150 научни и научнопопулярни статии.

Доц. Ася Русева е преподавател в катедра Геометрия на Факултета по математика и информатика на СУ Св. Кл. Охридски. Защитава научните степени доктор (2005) и доктор на науките (2020) с трудове по приложението на крайните геометрии в теорията на кодирането. Научните ѝ интереси са в областта на основите на геометрията, крайните геометрии, комбинаториката и теорията на кодирането. Автор е на над 50 научни публикации в престижни международни списания и сборници.

Нов български университет
София 1618
кв. Овча купел, ул. Монтевидео №21
vruseva@nbu.bg

Предговор
Предварителни сведения

• Множества, функции, релации
• Елементарни принципи в комбинаториката
• Задачи

Биномни коефициенти

• Дефиниции и основни свойства
• Комбинаторни тъждества
• Мултиномни коефициенти
• Обобщение на биномните коефициенти
• Аритметични свойства на биномните коефициенти
• Задачи

Формули за обръщане

• Формула за включване и изключване
• Формули за обръщане
• Функция на Мьобиус
• Частично наредени множества
• Задачи

Рекурентни редици

• Няколко класически примера
• Хомогенни линейни рекурентни уравнения
• Нехомогенни линейни рекурентни уравнения
• Производящи функции
• Задачи

Специални числа

• Числа на Фибоначи
• Числа на Каталан
• Числа на Стирлинг
• Задачи

Разбивания

• Елементарни резултати за разбивания
• Разбивания и производящи функции
• Задачи

Графи - начални сведения

• Основни дефиниции
• Пътища и свързаност
• Операции с графи
• Разстояние в графи
• Дървета
• Обобщения на дефиницията за граф
• Задачи

Пътища в графи

• Ойлерови графи
• Хамилтонови цикли
• Задачи

Планарни графи

• Влагане на граф в повърхнина
• Формула на Ойлер
• Теорема на Куратовски
• Теорема на Вагнер
• Непланарни графи
• Задачи

Оцветяване на графи

• Оцветяване на върховете на графи
• Оцветяване на ребрата на графи
• Задача за четирите цвята
• Задачи

Екстремална теория на графите

• Теорема на Туран
• Екстремални задачи за цикли в графи
• Наситени графи
• Задачи

Теория на Рамзи

• Класически теореми на Рамзи
• Теорема на Рамзи за произволни графи
• Теорема на Ван дер Варден
• Задачи

Системи различни представители

• Теорема на Хол
• Оценка за броя на системите различни представители
• Системи различни представители с допълнителни свойства
• Минимаксни теореми
• Латински квадрати
• Задачи

Екстремална теория на множествата

• Вериги и антивериги
• Множества с пресичане
• Теорема на Хилтън-Милнър
• Теорема на Крускал-Катона
• Задачи

Крайни геометрии

• Основни дефиниции
• Овали и хиперовали
• Максимални арки
• Шапки