Kombinatorika

Lekcijas

1. lekcija (13. februārī).
2. lekcija (20. februārī).
3. lekcija (27. februārī).
4. lekcija (13. martā).
5. lekcija (20. martā).
6. lekcija (27. martā).
7. lekcija (3. aprīlī).
9. lekcija (24. aprīlī).
11. lekcija (15. maijā).
13. lekcija (29. maijā).

Mājas darbi

1. mājas darbs (nodošanas termiņš 2003. gada 13. marts).
2. mājas darbs (nodošanas termiņš 2003. gada 3. aprīlis).
3. mājas darbs (nodošanas termiņš 2003. gada 24. aprīlis).
4. mājas darbs (nodošanas termiņš 2003. gada 26. jūnijs).
Rezultāti.

Ja mājas darbs nav nodots laikā, tajā savāktie punkti tiek dalīti ar divi.
Mājas darbu teksti pieejami PostScript formātā. Freeware PostScript failu pārlūks GhostScript/GhostView pieejams šeit.

Kursa plāns

1. Kas ir kombinatorika? Pārskaitošā kombinatorika. Skaitīšanas rezultāts.
2. Kombinatorisks un nekombinatorisks pierādījums. Veidotājfunkcijas.
3. Kopas un multikopas. Izlases. Variācijas, permutācijas.
4. Kombinācijas. Binomiālie koeficienti.
5. Skaitļa sadalījumi un kombinācijas ar atkārtojumiem.
6. Multikopas permutācijas. Multinomiālie koeficienti.
7. Substitūcijas. Transpozīcijas. Sadalījums transpozīcijās.
8. Cikli. Sadalījums ciklos.
9. Pirmā veida Stirlinga skaitļi.
10. Inversijas. Kritumi. Eilera polinoms. Eilera skaitļi.
11. Substitūciju attēlošana koka veidā.
12. q-multinomiālie koeficienti.
13. Skaitļa saskaldījumi.
14. Kopas saskaldījumi. Otrā veida Stirlinga skaitļi.
15. Sieta metode.
16. Latīņu kvadrāti.
17. Blokshēmas.
18. Transversāļi. Varbūtisko automātu dekompozīcija. Permanenti.
19. Grafu skaitīšana. Ramseja teorēma.
20. Poijā teorēma.

Konsultācijas un eksāmeni

Noapaļots 4 labāko mājas darbu un konspekta atzīmju vidējais aritmētiskais dod automātisko atzīmi. Ja tā neapmierina, jāliek eksāmens. Eksāmenā atrisināts uzdevums uzlabo atzīmi par 0,5, neatrisināts - samazina par 0,5. Var risināt 2, 4 vai 6 uzdevumus, pēc studenta izvēles.

Konsultāciju un eksāmenu laiki:

11.06.2003.    16.30    konsultācija    Antonijas 8-8
12.06.2003.    9.00      eksāmens        12.aud.

18.06.2003.    16.30    konsultācija    Antonijas 8-8
19.06.2003.    9.00      eksāmens        12.aud.

25.06.2003.    16.30    konsultācija    Antonijas 8-8
26.06.2003.    9.00      eksāmens        12.aud.

Literatūra

Pamatliteratūra

1. Р. Стенли. Перечислительная комбинаторика. Москва, Мир, 1990. (Angliski: Richard P. Stanley. Enumerative Combinatorics. Wadsworth, 1986.)
2. Indulis Strazdiņš. Diskrētā matemātika. Rīga, Zvaigzne ABC, 2001. (3. nodaļa: Kombinatorika un grafu teorija.)
3. Ф. А. Новиков. Дискретная математика. Санкт-Петербург, Питер, 2001. (Глава 5: Комбинаторика.)
4. В. Н. Сачков. Комбинаторные методы дискретной математики. Москва, Наука, 1977.
5. М. Холл. Комбинаторика. Москва, Мир, 1970. (Angliski: Marshall Hall, Jr. Combinatorial Theory. Waltham (Massachusetts), Blaisdell Publishing, 1967.)

Papildliteratūra

6. A. Andžāns, P. Zariņš. Matemātiskās indukcijas metode un varbūtību teorijas elementi. Rīga, Zvaigzne, 1983. (3. nodaļa: Kombinatorika.)
7. Agnis Andžāns, Jānis Čakste, Tomass Larfelds, Līga Ramāna, Mārīte Seile. Vidējās vērtības metode. Rīga, Mācību grāmata, 1996.
8. A. Gailītis, A. Andžāns. Kārtošanas un meklēšanas uzdevumi. Aizkraukle, Krauklītis, 1995.
9. Я. Гульден, Д. Джексон. Перечислительная комбинаторика. Москва, Наука, 1990. (Angliski: I. P. Goulden and D. M. Jackson. Combinatorial Enumeration. New York, Wiley-Inrescience, 1983.)
10. А. Кофман. Введение в прикладную комбинаторику. Москва, Наука, 1975.
11. Дж. Риордан. Введение в комбинаторный анализ. Москва, Издательство иностранной литературы, 1963. (Angliski: John Riordan. An Introduction to Combinatorial Analysis. New York, John Wiley & Sons, 1958.)
12. Г. Эндрюс. Теория разбиений. Москва, Наука, 1982. (Angliski: George E. Andrews. The Theory of Partitions. London, Addison-Wesley, 1976.)
13. Прикладная комбинаторная математика, под редакцией Э. Беккенбаха. Москва, Мир, 1968. (Angliski: Applied Combinatorial Mathematics, Edwin E. Beckenbach, editor. New York, John Wiley and Sons, 1964.)
14. М. Н. Аршинов, Л. Е. Садовский. Коды и математика. Библиотечка Квант, выпуск 30. Москва, Наука, 1983.
15. Р. Басакер, Т. Саати. Конечные графы и сети. Москва, Наука, 1974. (Angliski: Robert G. Busacker & Thomas L. Saaty. Finite Graphs and Networks: An Introduction with Applications. New York, McGraw-Hill.)
16. Р. Грэхем. Начала теории Рамсея. Москва, Мир, 1984. (Angliski: Ronald L. Graham. Rudiments of Ramsey Theory. Providence (Rhode Island), American Mathematical Society, 1981.)
17. О. А. Иванов. Избранные главы элементарной математики. Санкт-Петербург, Издательство С.-Петербургского университета, 1995.
18. А. Н. Колмогоров, И. Г. Журбенко, А. В. Прохоров. Введение в теорию вероятностей. Библиотечка Квант, выпуск 23. Москва, Наука, 1982.
19. В. А. Садовничий, А. А. Григорьян, С. В. Конягин. Задачи студенческих математических олимпиад. Москва, Издательство Московского университета, 1987.
20. В. А. Успенский. Треугольник Паскаля. Москва, Наука, 1979.
21. Д. О. Шклярский, Н. Н. Ченцов, И. М. Яглом. Геометрические оценки и задачи из комбинаторной геометрии. Москва, Наука, 1974.
22. М. К. Чирков. Основы общей теории конечных автоматов. Ленинград, Издательство Ленинградского университета, 1975.
23. А. М. Яглом и И. М. Яглом. Неэлементарные задачи в элементарном изложении. Москва, Государственное издательство технико-теоретической литературы, 1954.

Saites

Visas šīs lapas ir angļu valodā:

Kombinatorika (definīcija)
Kombinatorika (definīcija)
Kombinatorikas mājaslapa
Kombinatorikas uzdevumu krātuve
Ramseja spēle

Ja zināt vēl kādas kombinatorikas lapas, īpaši latviešu valodā, lūdzu, atsūtiet man par to ziņu (juris punkts smotrovs et sets punkts lv).