Комбинаториката разглежда задачи за разполагане и преброяване на математически обекти и използва идеи от геометрията, алгебрата и анализа. Разнообразието на приложението на тази дисциплина е удивително – теория на кодирането, криптография, сложност на алгоритми, теория на вероятностите. С това тя е неотменима част от образованието на специалисти в области като математика, информатика, физика, биологически науки, химия, икономика.
Книгата се основава на курсове по комбинаторика в Нов български университет и Факултета по математика и информатика на СУ Св. Климент Охридски, както и на лекции, изнесени при подготовката на националните отбори за Международните олимпиади по математика. Тя е насочена към студенти по математика и информатика, но може да представлява интерес за всички, занимаващи се с проблеми от дискретната математика. Голяма част от материала е достъпен и за ученици от горния гимназиален курс.
Проф. Иван Ланджев е преподавател в департамент Информатика на Нов български университет и изследовател в Института по математика и информатика на БАН. Той е кандидат на математическите науки (1990) и доктор на математическите науки (2000). Специализирал е в Техническия университет – Мюнхен и в Университета на Салфорд като стипендиант на DAAD, Alexander von Humboldt Stiftung и The Royal Society. Бил е гост-професор в Мичиганския технически университет, Техническия университет – Мюнхен, Университета на Байройт, Университета на Гент, Университета на Чжъцзян. Научните му интереси са в областта на теорията на кодирането, криптографията, теорията на дизайните, крайните геометрии и теорията на графите. Автор е на над 150 научни и научнопопулярни статии.
Доц. Ася Русева е преподавател в катедра Геометрия на Факултета по математика и информатика на СУ Св. Кл. Охридски. Защитава научните степени доктор (2005) и доктор на науките (2020) с трудове по приложението на крайните геометрии в теорията на кодирането. Научните ѝ интереси са в областта на основите на геометрията, крайните геометрии, комбинаториката и теорията на кодирането. Автор е на над 50 научни публикации в престижни международни списания и сборници.
СЪДЪРЖАНИЕ:
Предговор
Предварителни сведения
- Множества, функции, релации
- Елементарни принципи в комбинаториката
- Задачи
Биномни коефициенти
- Дефиниции и основни свойства
- Комбинаторни тъждества
- Мултиномни коефициенти
- Обобщение на биномните коефициенти
- Аритметични свойства на биномните коефициенти
- Задачи
Формули за обръщане
- Формула за включване и изключване
- Формули за обръщане
- Функция на Мьобиус
- Частично наредени множества
- Задачи
Рекурентни редици
- Няколко класически примера
- Хомогенни линейни рекурентни уравнения
- Нехомогенни линейни рекурентни уравнения
- Производящи функции
- Задачи
Специални числа
- Числа на Фибоначи
- Числа на Каталан
- Числа на Стирлинг
- Задачи
Разбивания
- Елементарни резултати за разбивания
- Разбивания и производящи функции
- Задачи
Графи – начални сведения
- Основни дефиниции
- Пътища и свързаност
- Операции с графи
- Разстояние в графи
- Дървета
- Обобщения на дефиницията за граф
- Задачи
Пътища в графи
- Ойлерови графи
- Хамилтонови цикли
- Задачи
Планарни графи
- Влагане на граф в повърхнина
- Формула на Ойлер
- Теорема на Куратовски
- Теорема на Вагнер
- Непланарни графи
- Задачи
Оцветяване на графи
- Оцветяване на върховете на графи
- Оцветяване на ребрата на графи
- Задача за четирите цвята
- Задачи
Екстремална теория на графите
- Теорема на Туран
- Екстремални задачи за цикли в графи
- Наситени графи
- Задачи
Теория на Рамзи
- Класически теореми на Рамзи
- Теорема на Рамзи за произволни графи
- Теорема на Ван дер Варден
- Задачи
Системи различни представители
- Теорема на Хол
- Оценка за броя на системите различни представители
- Системи различни представители с допълнителни свойства
- Минимаксни теореми
- Латински квадрати
- Задачи
Екстремална теория на множествата
- Вериги и антивериги
- Множества с пресичане
- Теорема на Хилтън-Милнър
- Теорема на Крускал-Катона
- Задачи
Крайни геометрии
- Основни дефиниции
- Овали и хиперовали
- Максимални арки
- Шапки