Теорія конфігурацій і теорія перерахування

2.1 Теорія конфігурацій і теорія перерахування

Теорія конфігурацій є традиційним і найбільш розробленим розділом комбінаторики. Теорія конфігурацій розглядає завдання вибору й розташування елементів деякого, звичайно кінцевого, множини, відповідно до заданих правил. Перерахувальна комбінаторика основним методом дослідження проголосила метод твірних функцій, використовуючи який було доведено величезне число комбінаторних тотожностей.

Елементарними комбінаторними конфігураціями є сполучення, розміщення, перестановки. Для підрахунку числа цих конфігурацій використовуються правила суми й добутку.

2.1.1 Правило суми

Якщо елемент A можна вибрати m способами, а елемент B можна вибрати k способами, то вибір елемента A або B можна здійснити m + k способами.

Правило суми можна перефразувати теоретико-множинною мовою. Позначимо через | A | число елементів множини A, через  - об'єднання множин A і B, через  - декартовий добуток множин A і B. Тоді для непересічних множин A і B виконується рівність:

.

Узагальненням правила суми є правило добутку.

2.1.2 Правило добутку

Якщо елемент A можна вибрати m способами, а після кожного вибору елемента A елемент B можна вибрати k способами, тоді, упорядковану пару елементів (A, B) можна вибрати m*k способами.

Правило добутку можна поширити на вибір послідовності (x1, x2, ..., x_n) довільної кінцевої довжини n.

Теоретико-множинною мовою правило добутку формулюється так:

.

2.2 Блок-схеми

Комбінаторні конфігурації найбільш загального виду були досліджені в 30- е роки XX сторіччя й були названі блок-схемами (block desіgn). Блок-схеми складаються з наборів елементів, називаних блоками. Вибір елементів і пара елементів у блоки підкоряються певним правилам.

Урівноваженою неповною блок-схемою називається таке розміщення v різних елементів по b блоках, що кожний блок містить точно k різних елементів, кожний елемент з'являється точно в k різних блоках і кожна пара різних елементів a_i , a_j з'являється точно в блоках.

Множина всіх  сполучень із v елементів по k, узятих як блоки, утворить повну блок-схему. Частина цих сполучень, у яких кожна пара a_i , a_j з'являється одне й те саме число раз, є неповною, але врівноваженою блок-схемою. Між п'ятьома параметрами блок-схеми виконуються наступні два співвідношення:

Частинним випадком блок-схем є так звані скінченні площини. Виберемо скінченну множину P. Елементи з P назвемо точками. Деякі підмножини з P назвемо прямими. Нехай відношення інцидентності між точками й прямими задовольняє наступним геометричним аксіомам.

1.  На кожній прямій лежить n точок B.

2.  Через кожну точку проходять n прямих.

3.  Будь-які дві прямі перетинаються в одній точці.

4.  Через будь-які дві точки проходить єдина пряма.

5.  Існують 4 точки неколлінеарні по трьох.

Тоді кінцева множина P точок і множина L прямих утворить кінцеву проективну площину.

Для знаходження кусково-постійних конфігурацій множин треба спочатку на множині усіх множин ввести Р(D) лінійні бінарні відношення  та =. Матимемо частково впорядковану множину . Потім знаходимо ті групи множин, які у заданій конфігурації розташовані поряд і які рівні – це й будуть "куски" постійності у конфігурації множин, а сама така конфігурація називається кусково-постійною.

Висновок

У процесі роботи над цим твором я навчився програмувати засобами IDE C++ Builder з допомогою вбудованого GUI, функцій та класів. Для розв’язання задачі знадобились знання з комбінаторики та теорії множин, які я освіжив також при опрацюванні теоретичної частини курсового проекту. Було досягнуто значних успіхів у поглибленні розуміння підґрунтя математики та кібернетики, був зроблений крок до підготовки ще одного гідного випускника нашого славного вишу.

Список використаних джерел

1.  http://www.embarcadero.com/ru/products/cbuilder\

2.  Александров П. С. Введение в теорию множеств и общую топологию. — М.: "НАУКА", 1977. — 368 с.

3.  Андерсон Джеймс Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: "Вильямс", 2006. — С. 960. — ISBN 0-13-086998-8

4.  Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.

5.  Джаррод Холингворт, Боб Сворт, Марк Кэшмэн, Поль Густавсон Borland C++ Builder 6. Руководство разработчика = Borland C++ Builder 6 Developer’s Guide. — М.: "Вильямс", 2004. — С. 976. — ISBN 0-672-32480-6

6.  Джерод Холлингворс, Дэн Баттерфилд, Боб Свот C++ Builder 5. Руководство разработчика = C++ Builder 5 Developer’s Guide. — М.: "Диалектика", 2001. — С. 884. — ISBN 0-672-31972-1

7.  Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.

8.  Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: "ФИЗМАТЛИТ", 2004. — 572 с. — ISBN 5-9221-0266-4

9.  Р. Стенли Перечислительная комбинаторика = Enumerative Combinatorics. — М.: "Мир", 1990. — С. 440. — ISBN 5-03-001348-2

10.  Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.

11.  Риордан Дж. Введение в комбинаторный анализ. — пер. с англ.. — М.: 1963.Хаусдорф Ф. Теория множеств. — 4-е изд. — М.: УРСС, 2007. — 304 с. — ISBN 978-5-382-00127-2

Додаток (постановка задачі, код програми, приклад)

Постановка задачі

Нехай маємо "n"кульок і три ящики А1,А2,А3. Встановити число способів Рn можна розмістити кульки так щоб у перших двох ящиках була однакова к-сть кульок

Код програми

//---------------------------------------------------------------------------

//Нехай маємо "n"кульок і три ящики А1,А2,А3.Встановити число способів

//Рn можна розмістити кульки так щоб у перших двох ящиках була однакова к-сть кульок

#include <vcl.h>

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

#include "stdio.h"

int n=1, Pn=0;

int f(int n)

{

int r=1;

for(int i=1;i<=n;++i)

{

r=r*i;

}

return r;

}

int A(int n, int k)

{

return f(n)/f(n-k);

}

void __fastcall TForm1::Button1Click(TObject *Sender)

{

int n=Edit1->Text.ToInt(), Pn=A(n,2);

for(int i=0;i<=n/2;++i)

{

Pn+=A(n,i)*A(n-i,i);

}

AnsiString as = "Відповідь: "+IntToStr(Pn);

ShowMessage(as);

}

//---------------------------------------------------------------------------

Приклад