Проблемот кој во оваа статија ќе се обидеме да го решиме е следниот : На колку начина можат да се обојат полињата на шаховска табла 8х8 со 8 различни бои така што во секој ред да се јавува секоја од боите и во ниту една колона не постојат две соседни полиња (едно над друго) кои се обоени со иста боја?
Во многу задачи од областа на комбинаториката се јавува потребата да се најде бројот на елементи во унијата на неколку конечни множества. Во тој случај, доколку се познати бројот на елементи во секое од множествата и бројот на елементи во нивните пресеци, може да се примерни методот на вклучување и исклучување за да се добие одговорот. Да разгледаме најпрво два едноставни примера.
Пример 1. Во една група студенти, има 10 што зборуваат француски, 12 што зборуваат англиски и 7 кои зборуваат и француски и англиски. Треба да одредиме колку студенти зборуваат барем еден странски јазик.
Нека со А го означиме множеството на студенти кои зборуваат француски, а со В множеството на студенти кои зборуваат англиски. Треба да го одредиме бројот на елементите на множеството А∪В. Понатаму ознаката |X| ќе ни го означува бројот на елементи во множеството Х. Во збирот |A|+ |B| два пати се додадени студентите кои зборуваат англиски и француски, па затоа ќе треба еднаш да ги одземеме. Сликовите, во збирот |A|+ |B| два пати се додадени елементите во портокаловата област на сликата која го претставува пресекот на А и В и затоа еднаш ќе треба да ги одземеме бидејќи сакаме само еднаш да ги вклучиме, а не два пати.
Нека со А, В и С ги означиме множествата на природни броеви не поголеми од 1000 кои се деливи со 2, 3 и 5 соодветно. Треба да го одредиме бројот на елемнти во множеството A∪B∪C. Aко го пресметаме збирот |A|+|B|+|C| тогаш во него два пати се пресметани броевите кои се наоѓаат во пресекот на точно две од множествата А, В или С, а три пати броевите кои се наоѓаат во пресекот на сите три множества.
Сликовито, два пати се пресметани броевите во светло портокаловата област (деливи и со 2 и 3 истовремено), два пати броевите во темно црвената област (деливи со 3 и 5 истовремено), два пати броевите во темно жолтата област (деливи со 2 и 5 истовремено) и три пати броевите во темно портокаловата област (деливи со 2, 3 и 5 истовремено). Затоа :
Кога имаме произволен број на конечни множества, важи општа формула.
Во многу задачи од областа на комбинаториката се јавува потребата да се најде бројот на елементи во унијата на неколку конечни множества. Во тој случај, доколку се познати бројот на елементи во секое од множествата и бројот на елементи во нивните пресеци, може да се примерни методот на вклучување и исклучување за да се добие одговорот. Да разгледаме најпрво два едноставни примера.
Пример 1. Во една група студенти, има 10 што зборуваат француски, 12 што зборуваат англиски и 7 кои зборуваат и француски и англиски. Треба да одредиме колку студенти зборуваат барем еден странски јазик.
| A ∪ B | = | A | + | B | – | A ∩ B | = 10 + 12 – 7 = 15
Пример 2. Да се одреди бројот на природни броеви не поголеми од 1000 кои се деливи со барем еден од броевите 2, 3 или 5.Нека со А, В и С ги означиме множествата на природни броеви не поголеми од 1000 кои се деливи со 2, 3 и 5 соодветно. Треба да го одредиме бројот на елемнти во множеството A∪B∪C. Aко го пресметаме збирот |A|+|B|+|C| тогаш во него два пати се пресметани броевите кои се наоѓаат во пресекот на точно две од множествата А, В или С, а три пати броевите кои се наоѓаат во пресекот на сите три множества.
| А ∪ В ∪ C | = | A | + | B | + | C | – | A ∩ B | – | B ∩ C | – | C ∩ A | + | A ∩ B ∩ C |
Со –|A∩B| –|B∩C| –|C∩A| елементите во A∩B∩C три пати ги одземаме и затоа на крајот е потребно ‘да ги вратиме’, односно еднаш да ги додадеме. Множествата A∩B , B∩C , C∩A и A∩B∩C ги содржат броевите деливи со 6, 15, 10 и 30, и бидејќи |A|=500, |B|=333, |C|=200, |A∩B|=166, |B∩C|=66, |C∩A|=100, |A∩B∩C|=33 за бројот на природни броеви не поголеми од 1000 деливи со барем еден од броевите 2, 3 или 5 се добива 734.Кога имаме произволен број на конечни множества, важи општа формула.
Доказ. Нека а е произволен елемент кој се содржи во точно r од n – те множества А1, А2, ..., Аn. (1 ≤ r ≤ n) Тогаш a∈A1∪A2∪…∪An и десната страна од горната формула е еднаква :
Она што всушност правиме е одбираме произволен елемент кој се содржи во некои од n – те множества (во r од нив). Тој елемент во левата страна на равенството е избројан еднаш (бидејќи во унијата на сите множества се јавува еднаш независно од тоа што можеби е елемент на повеќе од нив) и треба да покажеме дека и во десната страна на равенството е избројан исто така еднаш. Пример : ∑|Ai∩Aj| = C(r, 2) бидејќи елементот а го броиме по еднаш само во пресекот на множествата Аi и Aj кога и двете истовремено го содржат, a вкупно такви парови има C(r, 2). C(r, 2) го претставува бројот на комбинации од r елементи, класа 2. C(r, 2) = r! / [ 2!*(r–2)! ]
Да се вратиме сега на нашиот главен проблем. На колку начина можат да се обојат полињата на шаховска табла 8х8 со 8 различни бои така што во секој ред да се јавува секоја од боите и во ниту една колона не постојат две соседни полиња (едно над друго) кои се обоени со иста боја?
Кога не би требале да внимаваме да не се јават две соседни полиња со иста боја во некоја од колоните, тогаш одговорот би бил едноставен – (8!)8 бидејќи секоја од 8 – те редици можеме да ја обоиме на 8! различни начини. Но, како и да е, она што во нашиот проблем сигурно можеме да го направиме е првата редица од таблата да ја обоиме со една од пермутациите на 8 – те бои бидејќи нема над неа друга редица која би нè ограничувала во поставувањето на боите. Но, веќе кај втората редица ќе мораме да внимаваме да не го нарушиме условот на проблемот.
На примерот на сликата е дадено едно од 8! – те можни валидни боења на првата редица. Треба да одредиме на колку начини може да се пополни вториот ред така што условот од задачата биде запазен. Полето означено со 1 не смееме да го обоиме со темно црвена боја, полето 2 не смееме да го обоиме со светло црвена, полето 3 со портокалова, и.т.н. Очигледно, некои од сите можни пермутации ќе треба да отпаднат како невалидни. За точно да утврдиме кои од пермутациите треба да се исфрлат, да ги претставиме 8 – те бои со 8 различни цифри како на сликата.
Ако замислиме дека на секоја од боите во првата редица еднозначно и е доделена цифра, тогаш вториот ред ќе можеме да го обоиме само со оние пермутации во кои 6 не стои на првото место, 2 не стои на второто место, 5 не стои на третото место и.т.н. односно пермутации во кои елементот ај не се наоѓа на позиција ј. Важи општиот заклучок дека секој од 8 – те елементи не смее да се најде на некоја од 8 – те позции и притоа за секој елемент има различна забранета позиција. Односно, секоја боја има единствена забранета позиција во наредната редица на која не смее да се најде и на секоја позиција во наредната редица одговара единствена боја која на неа не смее да стои. Пример. Зелена не може да се најде само на позиција 5 (на ј=5 не може да се најде ај=3), а на сите други може. И на позиција 7 не може да се најде само виолетова боја, а сите други бои можат.
Всушност, проблемот сега го сведовме на броење на пермутации со онапред зададено ограничување. Треба да ги изброиме сите оние пермутации на 8 елементи такви да елементот ај не се наоѓа на позиција ј. Без губење на општоста, ќе претпоставиме дека j∈{1, 2,…, n} и дека a1 a2…an е пермутација на множеството {1, 2,…, n} . Во нашиот случај n=8 , но ние ќе го решиме проблемот за произволно n.
Нека S е множеството на сите пермутации над {1, 2,…, n} . Ѕ има n! елементи бидејќи толкав е бројот на сите пермутации. За секое j∈{1, 2,…, n} нека Aj го означува множеството од оние пермутации над {1, 2,…, n} за кои важи дека aj=j. Да напоменам дека S и Ај се множества на пермутации и ние ќе сакаме да го најдеме бројот |S \ (A1∪A2∪…∪An)|. Согласно примерот на сликата, во А1 би влегле сите оние пермутации во кои темно црвената боја стои на првото место, или во А6 сите оние пермутации во кои сината боја стои на 6 – тото место. Да забележиме дека не мора за другите елементи да не важи условот aj=j, доволно е само за разгледуваниот во конкретното множество да важи. Затоа и ќе треба да го примениме методот на вклучување и исклучување, бидејќи во А1 , на пример, ќе бидат вклучени пермутации кои постојат и во другите Ај множества.
Сега, за произволни j1, j2,…, jk (1 ≤ j1 < j2 < ⋯ < jk ≤ n), односно за k произволни, но различни индекси во опсегот 1 – n, важи : |Aj1 ∩ Aj2 ∩ … ∩ Ajk| = (n – k)!
бидејќи во пермутациите кои припаѓаат на множеството Aj1∩Aj2∩…∩Ajk, елементите aj1, aj2,…, ajk се на своите места j1, j2,…, jk, a останатите n – k елементи се јавуваат во секој можен распоред на остнатите n – k позиции.
На наредната слика е да ден пример за n=4 , две произволни Aj множества A1 и A4 и нивниот пресек.
Според формулата за вклучување и исклучување, имаме:
Карактеристично за множествата Aj е тоа што во пресекот на k од нив секогаш има еднаков број елементи (n – k)! независно од тоа кои k од нив се одбрани. Биномните коефициенти доаѓаат од тоа на колку начини можат да се изберат k множества од n. Пример. Втората сума е еднаква на
C(n,2)(n – 2)! Бидејќи постојат C(n,2) начини да се избере пар множества од вкупно n и во пресекот на секој таков пар се наоѓаат (n – 2)! елементи. Слично се добива и за останатите суми од формулата.
A1∪A2∪…∪An го претставува множеството на невалидни пермутации и кога неговиот број ќе го одземеме од вкупниот број на пермутации, тогаш ќе до добиеме бројот на валидни пермутации. Вака одбраните множества Ај се многу 'згодни' бидејќи на многу едноставен начин може да се пресметаат бројот на елементите во секои од нив, како и во пресеците на произволен број од нив. Уште повеќе, бројот на елементите во пресекот не зависи од изборот на множествата. Нека бројот на невалидни пермутации го означиме со М.
Конечно :
За n=8 се добива бројот 14833.
Откако ќе фиксираме една можна пермутација на боите на вториот ред, истото размислување како и претходно важи за третиот бидејќи првиот ред нема никаква допирна точка со третиот, а валидните боења на третиот зависат само од боењето на вториот ред. Откако ќе го обоиме првиот на еден од 8! – те можни начини, секој од наредните 7 реда можеме да го обоиме на 14 833 можни валидни начини. Конечно за вкупниот број на начини да се обои шаховска табла 8х8 со 8 различни бои така штo секоја боја да се појавува во секоја од редиците и да не постои колона во која има две соседни полиња едно на друго обоени со иста боја се добива :
PDF http://www.mediafire.com/?cvsl9qzrgazoekx
математика пермутации броење комбинаторика combinatorics permutations counting inclusion exclusion principle
Да се вратиме сега на нашиот главен проблем. На колку начина можат да се обојат полињата на шаховска табла 8х8 со 8 различни бои така што во секој ред да се јавува секоја од боите и во ниту една колона не постојат две соседни полиња (едно над друго) кои се обоени со иста боја?
Кога не би требале да внимаваме да не се јават две соседни полиња со иста боја во некоја од колоните, тогаш одговорот би бил едноставен – (8!)8 бидејќи секоја од 8 – те редици можеме да ја обоиме на 8! различни начини. Но, како и да е, она што во нашиот проблем сигурно можеме да го направиме е првата редица од таблата да ја обоиме со една од пермутациите на 8 – те бои бидејќи нема над неа друга редица која би нè ограничувала во поставувањето на боите. Но, веќе кај втората редица ќе мораме да внимаваме да не го нарушиме условот на проблемот.
На примерот на сликата е дадено едно од 8! – те можни валидни боења на првата редица. Треба да одредиме на колку начини може да се пополни вториот ред така што условот од задачата биде запазен. Полето означено со 1 не смееме да го обоиме со темно црвена боја, полето 2 не смееме да го обоиме со светло црвена, полето 3 со портокалова, и.т.н. Очигледно, некои од сите можни пермутации ќе треба да отпаднат како невалидни. За точно да утврдиме кои од пермутациите треба да се исфрлат, да ги претставиме 8 – те бои со 8 различни цифри како на сликата.
Всушност, проблемот сега го сведовме на броење на пермутации со онапред зададено ограничување. Треба да ги изброиме сите оние пермутации на 8 елементи такви да елементот ај не се наоѓа на позиција ј. Без губење на општоста, ќе претпоставиме дека j∈{1, 2,…, n} и дека a1 a2…an е пермутација на множеството {1, 2,…, n} . Во нашиот случај n=8 , но ние ќе го решиме проблемот за произволно n.
Нека S е множеството на сите пермутации над {1, 2,…, n} . Ѕ има n! елементи бидејќи толкав е бројот на сите пермутации. За секое j∈{1, 2,…, n} нека Aj го означува множеството од оние пермутации над {1, 2,…, n} за кои важи дека aj=j. Да напоменам дека S и Ај се множества на пермутации и ние ќе сакаме да го најдеме бројот |S \ (A1∪A2∪…∪An)|. Согласно примерот на сликата, во А1 би влегле сите оние пермутации во кои темно црвената боја стои на првото место, или во А6 сите оние пермутации во кои сината боја стои на 6 – тото место. Да забележиме дека не мора за другите елементи да не важи условот aj=j, доволно е само за разгледуваниот во конкретното множество да важи. Затоа и ќе треба да го примениме методот на вклучување и исклучување, бидејќи во А1 , на пример, ќе бидат вклучени пермутации кои постојат и во другите Ај множества.
Сега, за произволни j1, j2,…, jk (1 ≤ j1 < j2 < ⋯ < jk ≤ n), односно за k произволни, но различни индекси во опсегот 1 – n, важи : |Aj1 ∩ Aj2 ∩ … ∩ Ajk| = (n – k)!
бидејќи во пермутациите кои припаѓаат на множеството Aj1∩Aj2∩…∩Ajk, елементите aj1, aj2,…, ajk се на своите места j1, j2,…, jk, a останатите n – k елементи се јавуваат во секој можен распоред на остнатите n – k позиции.
На наредната слика е да ден пример за n=4 , две произволни Aj множества A1 и A4 и нивниот пресек.
Според формулата за вклучување и исклучување, имаме:
Карактеристично за множествата Aj е тоа што во пресекот на k од нив секогаш има еднаков број елементи (n – k)! независно од тоа кои k од нив се одбрани. Биномните коефициенти доаѓаат од тоа на колку начини можат да се изберат k множества од n. Пример. Втората сума е еднаква на
C(n,2)(n – 2)! Бидејќи постојат C(n,2) начини да се избере пар множества од вкупно n и во пресекот на секој таков пар се наоѓаат (n – 2)! елементи. Слично се добива и за останатите суми од формулата.
A1∪A2∪…∪An го претставува множеството на невалидни пермутации и кога неговиот број ќе го одземеме од вкупниот број на пермутации, тогаш ќе до добиеме бројот на валидни пермутации. Вака одбраните множества Ај се многу 'згодни' бидејќи на многу едноставен начин може да се пресметаат бројот на елементите во секои од нив, како и во пресеците на произволен број од нив. Уште повеќе, бројот на елементите во пресекот не зависи од изборот на множествата. Нека бројот на невалидни пермутации го означиме со М.
Конечно :
За n=8 се добива бројот 14833.
Откако ќе фиксираме една можна пермутација на боите на вториот ред, истото размислување како и претходно важи за третиот бидејќи првиот ред нема никаква допирна точка со третиот, а валидните боења на третиот зависат само од боењето на вториот ред. Откако ќе го обоиме првиот на еден од 8! – те можни начини, секој од наредните 7 реда можеме да го обоиме на 14 833 можни валидни начини. Конечно за вкупниот број на начини да се обои шаховска табла 8х8 со 8 различни бои така штo секоја боја да се појавува во секоја од редиците и да не постои колона во која има две соседни полиња едно на друго обоени со иста боја се добива :
8!(14833)7= 6 369 766 324 804 378 723 931 712 343 520 640
PDF http://www.mediafire.com/?cvsl9qzrgazoekx
математика пермутации броење комбинаторика combinatorics permutations counting inclusion exclusion principle
No comments:
Post a Comment