БИЛИМ БУЛАГЫ

Математика: Основы комбинаторики — различия между версиями

(→‎Библиография)
 
(не показано 59 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
__NOTOC__
 
 
<div class="row mat-bg">
 
<div class="row mat-bg">
 
<div class="maintext math-back math-bg large-8 medium-7 columns"> <!-- Page Content -->  
 
<div class="maintext math-back math-bg large-8 medium-7 columns"> <!-- Page Content -->  
 
{{Якорь|Начало}}
 
{{Якорь|Начало}}
  
−
В царице наук – математике, все эти техники объединяются в одну отрасль науки, которую называют '''комбинаторикой'''. '''Комбинаторика''' — ''ветвь математики, изучающая комбинации и перестановки предметов, в переводе от латинского'' '''combinare''' – ''соединять, сочетать''. На протяжении двух с половиной столетий основную роль в изучении природы играл математический анализ. Положение коренным образом изменилось после создания быстродействующих вычислительных машин, компьютеров. С их помощью стало возможным делать переборы, ранее требовавшие сотен и тысяч лет. В эпоху расцвета дискретной математики изменилась и роль древнейшей области дискретной математики – комбинаторики. Комбинаторика как наука стала развиваться в VIII в. параллельно с возникновением теории вероятностей, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов.
+
==История развития комбинаторики==
  
−
Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицу, показывавшую, сколькими способами могут выпасть  костей. Однако при этом не учитывалось, что одна и та же сумма очков может быть получена разными способами. Со временем появились различные игры (нарды, карты, шашки, шахматы и т.д.). В каждой из этих игр приходилось рассматривать различные сочетания фигур, и выигрывал тот, кто их лучше изучил, знал выигрышные комбинации и умел избегать проигрышных.
+
Еще в доисторическую эпоху люди столкнулись  с задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке, отыскивать среди разных расположений наилучшие, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов – во время работы. Украшения на одежде, рисунок  на посуде, перья в оперении стрел также располагались определенным способом. По мере усложнения производственных и общественных отношений все шире приходилось пользоваться общими понятиями о порядке, иерархии, группировании. Развитие ремесел и торговли происходило в том же направлении. Комбинаторные навыки оказались полезными и во время отдыха. Так наряду с состязанием в беге, прыжках, метании диска появились игры, требовавшие, в первую очередь, умения рассчитывать, составлять план и предвидеть действия противника.
 +
 
 +
Среди предметов, положенных в пирамиду, где 35 веков назад был похоронен египетский фараон Тутанхамон, нашли разграфленную доску с тремя горизонталями и фигурки для древней игры «сенет». Позже появились нарды, шашки и шахматы. В каждой из этих игр приходилось рассматривать различные сочетания передвигаемых фигур, и выигрывал тот, кто их лучше изучил и знал выигрывающие комбинации.
 +
 
 +
<div class="show-for-large-up">{{center|[[Файл:История развития комбинаторики.mp4]]}}</div>
 +
<div class="hide-for-large-up">{{center|[[Файл:История развития комбинаторики.mp4]]}}</div>
 +
 
 +
<div class="light" style="float:right;>[[#Начало|В начало]]</div><br clear=all />
 +
 
 +
==Понятие комбинаторика==
 +
 
 +
Комбинато́рика  — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка); в переводе от латинского combinare – соединять, сочетать.  Комбинаторика связана с другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний.      
 
        
 
        
−
Известно, что для оценки вероятности победы в покере или при игре в рулетку надо просчитать, с одной стороны, общее позволяющей вычислить, сколько, например, стрит-флешей можно собрать при колоде в 52 карты. А рассчитать вероятности без комбинаторики практически невозможно.
+
Рассмотрим простой пример. Допустим, у нас есть банки с краской четырех цветов: красной (К), желтой (Ж), зеленой (3) и коричневой (Кор), и нам нужно разложить их по коробкам, по две разные банки в каждую. Мы можем сделать это следующим образом:
−
До начала расчетов необходимо навести порядок. Конечно же, мы не имеем в виду порядок на рабочем месте. Необходимо упорядочить объекты, число комбинаций с которыми мы хотим выяснить. Допустим, у нас есть банки с краской четырех цветов: красной (К), желтой (Ж), зеленой (3) и коричневой (Кор), и нам нужно разложить их по коробкам, по две разные банки в каждой. Мы можем сделать это следующим образом:
 
  
−
<div class="show-for-large-up">{{center|[[Файл:К_ж.png|500px]]}}</div>
+
<div class="show-for-large-up">{{center|[[Файл:Простой_пример.gif]]}}</div>
−
<div class="hide-for-large-up">{{center|[[Файл:К_ж.png|400px]]}}</div>
+
<div class="hide-for-large-up">{{center|[[Файл:Простой_пример.gif]]}}</div>
  
−
то есть шестью различными способами, так как если в одной коробке находятся банки с желтой и красной красками, то она полностью идентична той, где лежат банки с красной и желтой. Но если мы хотим парными цветами раскрасить флаги, то сделать это можно будет так: то есть двенадцатью способами, так как красно-желтый флаг не является идентичным желто-красному.
+
У нас получилось шесть различных способов, так как если в одной коробке находятся банки с желтой и красной красками, то она полностью идентична той, где лежат банки с красной и желтой. Но если мы хотим парными цветами раскрасить флаги, то сделать это можно будет двенадцатью способами, так как красно-желтый флаг не является идентичным желто-красному.
  
−
<div class="show-for-large-up">{{center|[[Файл:Флаг.png|500px]]}}</div>
+
<div class="show-for-large-up">{{center|[[Файл:Простой_пример_1.gif]]}}</div>
−
<div class="hide-for-large-up">{{center|[[Файл:Флаг.png|400px]]}}</div>
+
<div class="hide-for-large-up">{{center|[[Файл:Простой_пример_1.gif]]}}</div>
−
Вся наша жизнь состоит из множества разнообразных программ. Чтобы запустить ту или иную программу нужно ввести соответствующий верный пароль. В качестве кода в зависимости от рода программы могут выступать всевозможные цифры, слова или комбинации слов, поведение или действие. Комбинаторика используется в музыке, в мебельной деятельности, в различных играх (нарды, шашки, шахматы) и т.д. Читайте подробнее: http://ya-znau.ru/znaniya/zn/80, а если Вы хотите порешать задачки, то переходите сюда: http://www.mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html
 
  
−
<div class="show-for-large-up">{{center|[[Файл:Области_применения.png|500px]]}}</div>
+
<div class="light" style="float:right;>[[#Начало|В начало]]</div><br clear=all />
−
<div class="hide-for-large-up">{{center|[[Файл:Области_применения.png|400px]]}}</div>
 
  
−
<div class="show-for-large-up">{{center|[[Файл:Правила_сложения.png|500px]]}}</div>
+
==Основные формулы комбинаторики==
−
<div class="hide-for-large-up">{{center|[[Файл:Правила_сложения.png|400px]]}}</div>
+
 
 +
'''Правила сложения'''
 +
Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m + n способами.
  
 
'''Пример 1.'''
 
'''Пример 1.'''
 
На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?
 
На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?
 +
 
'''Решение:'''
 
'''Решение:'''
−
По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу сложения, можно осуществить 5+4=9 способами.
+
По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу сложения, можно осуществить 5 + 4 = 9 способами.
−
'''Ответ:''' 9 способов.
+
 
 +
'''Ответ''': 9 способов.
  
 
'''Пример 2.'''  
 
'''Пример 2.'''  
 
Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?
 
Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?
−
'''Решение:'''  
+
 
−
'''1 способ:''' перебор вариантов.
+
'''Решение''':
 +
'''1 способ: перебор вариантов.'''
 
Для того, чтобы не пропустить и не повторить ни одно из чисел, будем записывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и, наконец, с цифры 7:
 
Для того, чтобы не пропустить и не повторить ни одно из чисел, будем записывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и, наконец, с цифры 7:
 
14, 17, 41, 47, 71, 74.
 
14, 17, 41, 47, 71, 74.
−
'''Ответ:''' 6 чисел.
 
  
−
'''2 способ:''' дерево возможных вариантов.  
+
'''Ответ''': 6 чисел.
 +
 
 +
'''2 способ: дерево возможных вариантов.'''
 
Для этой задачи построена специальная схема.  
 
Для этой задачи построена специальная схема.  
 
Ставим звездочку. Далее отводим от звездочки 3 отрезка. Так как в условии задачи даны 3 цифры – 1, 4, 7, то на концах отрезков ставим  цифры 1, 4, 7.
 
Ставим звездочку. Далее отводим от звездочки 3 отрезка. Так как в условии задачи даны 3 цифры – 1, 4, 7, то на концах отрезков ставим  цифры 1, 4, 7.
 
Далее от каждой цифры проводим по 2 отрезка. На концах этих отрезков записываем также цифры 1, 4, 7. Получились числа: 14, 17, 41 47, 71, 74. То есть всего получилось 6 чисел. Эта схема действительно похожа на дерево, правда «вверх ногами» и без ствола.
 
Далее от каждой цифры проводим по 2 отрезка. На концах этих отрезков записываем также цифры 1, 4, 7. Получились числа: 14, 17, 41 47, 71, 74. То есть всего получилось 6 чисел. Эта схема действительно похожа на дерево, правда «вверх ногами» и без ствола.
  
−
<div class="show-for-large-up">{{center|[[Файл:47.png|500px]]}}</div>
+
<div class="show-for-large-up">{{center|[[Файл:Пример 2 2 способ.gif]]}}</div>
−
<div class="hide-for-large-up">{{center|[[Файл:47.png|400px]]}}</div>
+
<div class="hide-for-large-up">{{center|[[Файл:Пример 2 2 способ.gif]]}}</div>
  
 +
'''Правила умножения'''
 +
Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать п способами, то выбор пары (А, В) в указанном порядке можно осуществить m ∙ п способами.
  
−
'''Пример 3.'''  
+
''Пример 3.''  
 
Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?
 
Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?
−
'''Решение:'''  
+
 
 +
'''Решение''':
 
Первую цифру двузначного числа можно выбрать тремя способами. Так как после выбора первой цифры останутся две, то вторую цифру можно выбрать из оставшихся цифр уже двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 3∙2, т.е. 6.
 
Первую цифру двузначного числа можно выбрать тремя способами. Так как после выбора первой цифры останутся две, то вторую цифру можно выбрать из оставшихся цифр уже двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 3∙2, т.е. 6.
−
'''Ответ:''' 6 чисел.
 
  
−
<div class="show-for-large-up">{{center|[[Файл:Факториал.png|500px]]}}</div>
+
'''Ответ''': 6 чисел.
−
<div class="hide-for-large-up">{{center|[[Файл:Факториал.png|400px]]}}</div>
+
 
 +
'''Факториал'''.
 +
Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n. Обозначение n!
 +
 
 +
0! = 1
 +
 
 +
1!=1
 +
 
 +
2! = 1∙ 2 = 2
 +
 
 +
3! =  1∙ 2 ∙ 3 = 6
 +
 
 +
4! =  1∙ 2 ∙ 3 ∙ 4 =24
 +
 
 +
5! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120
 +
 
 +
6! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720
 +
 
 +
7! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 = 5 040
 +
 
 +
8! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40 320
 +
 
 +
9! =  1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 = 362 880
 +
 
 +
10! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 ∙ 10 = 3 628 880
 +
 
 +
'''Свойства комбинаторики: перестановки, сочетание, размещение'''
 +
 
 +
<div class="show-for-large-up">{{center|[[Файл:Шахматная_доска_абстрация.jpg]]}}</div>
 +
<div class="hide-for-large-up">{{center|[[Файл:Шахматная_доска_абстрация.jpg]]}}</div>
 +
 
 +
Перестановкой называется конечное множество, в котором установлен порядок элементов. Число всевозможных перестановок из n элементов вычисляется по формуле:  Pn = n!
  
−
<div class="show-for-large-up">{{right|[[Файл:Доска.png|200px]]}}</div>
 
−
<div class="hide-for-large-up">{{right|[[Файл:Доска.png|200px]]}}</div>
 
−
'''Перестановкой''' называется конечное множество, в котором установлен порядок элементов. Число всевозможных перестановок из n элементов вычисляется по формуле:  '''Pn = n!'''
 
 
'''Пример 4.'''   
 
'''Пример 4.'''   
 
Сколькими способами могут быть расставлены восемь участниц финального забега на восьми беговых дорожках?
 
Сколькими способами могут быть расставлены восемь участниц финального забега на восьми беговых дорожках?
 +
 
'''Решение.'''
 
'''Решение.'''
 
P8 = 8! = 40 320
 
P8 = 8! = 40 320
  
−
Размещением   из n элементов конечного множества по k, где   , называют упорядоченное множество, состоящее из k элементов и вычисляется по формуле:  .
+
Размещением   А<sup>k</sup><sub>n</sub>    из n элементов конечного множества по k, где k≤n, называют упорядоченное множество, состоящее из k элементов и вычисляется по формуле:   
−
Пример 5.  
+
 
 +
<div class="show-for-large-up">{{center|[[Файл:Formula_razme.png|100px]]}}</div>
 +
<div class="hide-for-large-up">{{center|[[Файл:Formula_razme.png|100px]]}}</div>
 +
 
 +
'''Пример 5.'''
 +
 
 
Из 12 учащихся нужно отобрать по одному человеку для участия в городских олимпиадах по математике, физике, истории и географии. Каждый из учащихся участвует только в одной олимпиаде. Сколькими способами это можно сделать?
 
Из 12 учащихся нужно отобрать по одному человеку для участия в городских олимпиадах по математике, физике, истории и географии. Каждый из учащихся участвует только в одной олимпиаде. Сколькими способами это можно сделать?
−
Решение.
 
  
−
  <div class="show-for-large-up">{{center|[[Файл:Различие между перестановками.png|500px]]}}</div>
+
'''Решение'''.
−
<div class="hide-for-large-up">{{center|[[Файл:Различие между перестановками.png|400px]]}}</div>
+
 
 +
<div class="show-for-large-up">{{center|[[Файл:Пример № 5.png]]}}</div>
 +
<div class="hide-for-large-up">{{center|[[Файл:Пример № 5.png]]}}</div>
 +
 
 +
Подмножества, составленные из n элементов данного множества и содержащие k элементов в каждом подмножестве, называют сочетаниями из n элементов по k. (Сочетания различаются только элементами, порядок их не важен: ab и ba – это одно и тоже сочетание) и вычисляется по формуле: .
 +
 
 +
<div class="show-for-large-up">{{center|[[Файл:Формула_сочетаний.png]]}}</div>
 +
<div class="hide-for-large-up">{{center|[[Файл:Формула_сочетаний.png]]}}</div>
 +
 
 +
Число размещений, перестановок и сочетаний связаны равенством:  .
 +
 
 +
<div class="show-for-large-up">{{center|[[Файл:Число размещений, перестановок и сочетаний.png]]}}</div>
 +
<div class="hide-for-large-up">{{center|[[Файл:Число размещений, перестановок и сочетаний.png]]}}</div>
 +
 
 +
Различие между перестановками, размещениями, сочетаниями:
 +
В случае перестановок берутся все элементы и изменяется только их местоположение.
 +
В случае размещений берётся только часть элементов и важно расположение элементов друг относительно друга.
 +
В случае сочетаний берётся только часть элементов и не имеет значения расположение элементов друг относительно друга.
 +
 
 +
<div class="light" style="float:right;>[[#Начало|В начало]]</div><br clear=all />
 +
 
 +
==Вероятность. Основные понятия==
 +
Наблюдение явления, опыт, эксперимент, которые можно проводить многократно, в теории вероятностей принято называть испытанием. Результат, исход испытания называется событием. Например, сдача экзамена - это испытание; получение определенной отметки – событие, бросание игрального кубика - это испытание; появление того или иного числа очков на брошенной игральной кости - событие.
 +
 
 +
Вероятность – это  число, характеризующее степень возможности появления события. Каждый из возможных результатов испытания  называется элементарным исходом.
 +
 
 +
Вероятностью P события А называют отношение числа благоприятствующих этому событию исходов к общему числу всех равновозможных несовместных элементарных исходов, образующих полную группу. Вероятность P события А определяется по формуле  Р = m/n , где m – число элементарных исходов, благоприятствующих A; n – число всех возможных элементарных исходов испытания.
 +
 
 +
Задача
 +
На шести одинаковых карточках написаны буквы К, Б, И, К, Е, Ш. Карточки перемешиваются и наугад раскладываются в ряд. Найдите, чему равна вероятность того, что получится слово БИШКЕК.
 +
 
 +
<div class="show-for-large-up">{{center|[[Файл:Задача_Бишкек.gif]]}}</div>
 +
<div class="hide-for-large-up">{{center|[[Файл:Задача_Бишкек.gif]]}}</div>
 +
 
 +
'''Решение'''.
 +
Искомая вероятность вычисляется по классической формуле Р = m/n ,  где  n - общее количество вариантов, а m - количество вариантов, соответствующих данному событию.
 +
В данном случае  n = 6! = 720 (количество перестановок из 6 карточек);
 +
m = 2 (в данном слове буква "К" повторяется дважды, а остальные по одному разу).
 +
Следовательно, Р=2/720=1/360.
 +
 
 +
'''Задача «Волк, козел и капуста»'''
  
−
==Задачи==
 
−
'''«Волк, козел и капуста»'''
 
−
<div class="show-for-large-up">{{right|[[Файл:Задача_волк.png|300px]]}}</div>
 
−
<div class="hide-for-large-up">{{right|[[Файл:Задача_волк.png|400px]]}}</div>
 
 
Крестьянину нужно перевезти через реку волка, козла и капусту. Лодка так мала, что в ней кроме крестьянина может поместиться только или волк, или козел, или капуста. Но если оставить волка с козлом, он его съест, а если оставить козла с капустой, то будет съедена капуста. Как быть крестьянину?
 
Крестьянину нужно перевезти через реку волка, козла и капусту. Лодка так мала, что в ней кроме крестьянина может поместиться только или волк, или козел, или капуста. Но если оставить волка с козлом, он его съест, а если оставить козла с капустой, то будет съедена капуста. Как быть крестьянину?
−
Для решения требуется путем взаимной перестановки элементов расположить их в соответствии с условием задачи в определенном порядке. В случае с крестьянином переправу следует начать с перевозки козла. Затем крестьянин возвращается и берет волка, которого перевозит на другой берег и оставляет там, а козла возвращает назад на предыдущий берег. Оттуда забирает капусту и перевозит ее к волку. А затем возвращается и забирает козла.
 
  
−
'''«Крестики-нолики»'''
+
Для решения требуется расположить путем взаимной перестановки элементов и в соответствии с условием задачи в определенном порядке. Крестьянину следует начать переправу с перевозки козла. Затем он возвращается и берет волка, которого перевозит на другой берег и оставляет там, а козла возвращает назад на предыдущий берег. Оттуда забирает капусту и перевозит ее к волку. А затем возвращается и забирает козла.
−
<div class="show-for-large-up">{{right|[[Файл:Задача_крестики.png|300px]]}}</div>
+
 
−
<div class="hide-for-large-up">{{right|[[Файл:Задача_крестики.png|400px]]}}</div>
+
<div class="show-for-large-up">{{center|[[Файл:Задача_Волк_коза_капутса.gif]]}}</div>
−
Самая известная древняя игра. В квадрате, разделенном на девять клеток, игроки по очереди ставят в свободную клетку свой знак: крестик или нолик, стараясь выстроить три крестика или три нолика подряд. Тот, кто первым сделает это, тот и выигрывает.
+
<div class="hide-for-large-up">{{center|[[Файл:Задача_Волк_коза_капутса.gif]]}}</div>
−
Если не делать ошибок, то игра оканчивается в ничью. Выиграть можно только в том случае, если противник ошибется. Самый правильный ход –занять угловую клетку. И если партнер не ответит на это своим знаком в центре, то он проиграл.
+
 
 +
<div class="light" style="float:right;>[[#Начало|В начало]]</div><br clear=all />
 +
 
 +
==Комбинаторика в программировании==
 +
'''Комбинаторика''' – это настоящий клад для программистов, так как  помогает анализировать различные  алгоритмы, выбор оптимальной стратегии перебора. Комбинаторные формулы требуются для расчётов вероятностей, а те, в свою очередь, для проверки статистических гипотез. Особое внимание уделяют  программисты комбинаторным задачам с пандигитальными числами, для генерирования которых используют программу Generics Combinatorics.
 +
 
 +
Пандигитальными называются числа, составленные из неповторяющихся цифр и не начинающиеся с нуля. Например, 123456789.  
 +
 
 +
Задачи с пандигитальными числами решаются почти так же, как и логические, и даже проще, поскольку все комбинаторные объекты представляют собой обычные числа.
 +
 
 +
Число 123456789 — наименьшее пандигитальное число в десятичной системе счисления. При умножение на 8 результатом будет 987654312 — другое пандигитальное число, близкое к палиндрому исходного, за исключением двух последних цифр, обменявшихся местами. Это число также сохраняет свою пандигитальность при умножении:
 +
 
 +
- на 2  123456789 ∙ 2 = 246913578,
 +
 
 +
- на 4  123456789 ∙ 4 = 493827156,
 +
 
 +
- на 5  123456789 ∙ 5 = 617283945,
 +
 
 +
- на 7 123456789 ∙ 7 = 864197523.
 +
 
 +
В качестве примера другого числа, сохраняющего свою пандигитальность при умножении на ряд коэффициентов, можно назвать 1098765432, перемножаемое таким образом на 2, 4, 5 и 7. Если добавить к числу 123456789 умноженному на 8 число 9, будет получен полный палиндром этого числа. Если множитель и слагаемое увеличить на единицу, результатом аналогичных операций станут числа, состоящие из одних единиц разрядностью от десяти до двух.
 +
 
 +
<div class="show-for-large-up">{{center|[[Файл:Пандигитальные_квадраты.gif]]}}</div>
 +
<div class="hide-for-large-up">{{center|[[Файл:Пандигитальные_квадраты.gif]]}}</div>
  
−
'''«Ним»'''
+
<div class="light" style="float:right;>[[#Начало|В начало]]</div><br clear=all />
−
<div class="show-for-large-up">{{right|[[Файл:Задача_гвоздики.png|300px]]}}</div>
 
−
<div class="hide-for-large-up">{{right|[[Файл:Задача_гвоздики.png|400px]]}}</div>
 
−
Пусть имеется одна или несколько групп предметов. Играющие берут по очереди предметы из групп по правилам, которые заранее устанавливают: какое количество предметов разрешается брать за один раз и из скольких групп. Существует множество вариантов игры, и для большинства известна наилучшая стратегия, ведущая к выигрышу.
 
  
 
==Полезные ссылки==
 
==Полезные ссылки==
−
«Я не знаю ничего более прекрасного в арифметике, чем эти числа, называемые некоторыми планетарными, а другими – магическими», - писал о числах известный французский математик, один из создателей теории чисел Пьер де Ферма. Привлекающие естественной красотой, наполненные внутренней гармонией, доступные, но по-прежнему непостижимые, скрывающие за кажущейся простотой множества тайн. В своей жизни каждый из нас сталкивается с числами. Курс школьной программы, да и дальнейшую жизнь, трудно представить без них. Более подробно читаем  в исследовательская работе  "Магические числа" http://collegy.ucoz.ru/publ/89-1-0-3365
+
Вся наша жизнь состоит из множества разнообразных программ. Чтобы запустить ту или иную программу нужно ввести соответствующий верный пароль. В качестве кода в зависимости от рода программы могут выступать всевозможные цифры, слова или комбинации слов, поведение или действие. Комбинаторика используется в музыке, в мебельной деятельности, в различных играх (нарды, шашки, шахматы) и т.д. Читайте подробнее:  [Электронный ресурс] //  2011-2017 Сила знаний URL:  http://ya-znau.ru/znaniya/zn/80    (Дата посещения: 19.04.2018)
 +
 
 +
Различные комбинаторные задачи с подробным решением можно посмотреть здесь: [Электронный ресурс] //mathprofi.ru, Александр Емелин, 2010-2018  URL: http://www.mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html    (Дата посещения: 19.04.2018)
 +
 
 +
Необходимые теоретические сведения и формулы для решения комбинаторных задач школьного уровня можно посмотреть здесь: [Электронный ресурс] //  Харламов А.В. элементы комбинаторики, 2016г. // URL:  http://elibrary.sgu.ru/uch_lit/1626.pdf (Дата посещения: 21.04.2018)
 +
 
 +
Поиграем? Пусть имеется одна или несколько групп предметов. Играющие берут по очереди предметы из групп по правилам, которые заранее устанавливают: какое количество предметов разрешается брать за один раз и из скольких групп. Существует множество вариантов игры, и для большинства известна наилучшая стратегия, ведущая к выигрышу.:[Электронный ресурс] // ЮЦ «Восстание-6» URL: https://logic-games.spb.ru/nim/ (Дата посещения: 22.04.2018)
 +
 
 +
<div class="light" style="float:right;>[[#Начало|В начало]]</div><br clear=all />
  
 
==Глоссарий==
 
==Глоссарий==
−
'''Комбинаторика''' - ветвь математики, изучающая комбинации и перестановки предметов.
+
'''Дискре́тность''' (от лат. discretus — разделённый, прерывистый) — свойство, противопоставляемое непрерывности, прерывность.
 +
Под '''дискретностью''' понимают: нечто, изменяющееся между несколькими различными стабильными состояниями, например механические часы, которые передвигают минутную стрелку дискретно (скачкообразно) на 1/60 часть окружности; нечто, состоящее из отдельных частей, прерывистость, дробность.
  
−
== Библиография ==
+
'''Палиндро́м''' (от др.-греч. πάλιν — «назад, снова» и др.-греч. δρóμος — «бег, движение»)— число, буквосочетание, слово или текст, одинаково читающееся в обоих направлениях.
−
*Комбинаторика. https://infourok.ru/kombinatorikaeto-interesnonauchniy-proekt-sekciya-matematika-816469.html
+
 
−
*Комбинаторика: основные правила и формулы. http://ya-znau.ru/znaniya/zn/80
+
'''Пандигитальные числа''' – это числа, составленные из неповторяющихся цифр и не начинающиеся с нуля.
−
*Савельев Л.Я. Комбинаторика и вероятность. – Новосибирск, Наука, 1975.
 
−
*Тюрин Ю.Н., Макаров А.А., Высоцкий И.Р., Ященко И.В. Теория вероятностей и статистика. – М.: МЦНМО: АО «Московские учебники», 2004.
 
  
 +
'''Су́тра''' (санскр. सूत्र sūtra IAST, «нить», пали: sutta) — в древнеиндийской литературе лаконичное и отрывочное высказывание, афоризмы, позднее — своды таких высказываний. В сутрах излагались различные отрасли знания, почти все религиозно-философские учения Древней Индии.
  
−
<div class="light" style="float:right;>[[#Начало|В начало]]</div>
+
<div class="light" style="float:right;>[[#Начало|В начало]]</div><br clear=all />
  
 +
== Библиография ==
 +
*Комбинаторика: основные правила и формулы. : [Электронный ресурс] //  2011-2017 Сила знаний URL:  http://ya-znau.ru/znaniya/zn/80  (Дата посещения: 19.04.2018)
 +
*Задачи по комбинаторике. Примеры решений.: [Электронный ресурс] //mathprofi.ru, Александр Емелин, 2010-2018  URL: *http://www.mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html    (Дата посещения: 19.04.2018)
 +
*Сканворды, кроссворды и головоломки: [Электронный ресурс] //  Пискунов Алексей © 2009-2018 http://www.graycell.ru/index.html (Дата посещения: 19.04.2018)
 +
*Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика: М.: ФИМА, МЦНМО, 2006. — 400 с.
 +
*Мир математики: в 40 т. Т.21: Ламберто Гарсия дель Сид. Замечательные числа. Ноль, 666,  и другие бестии./Пер. с исп. –М.: Де Агостини, 2014. – 160 с.
 +
 +
<div class="light" style="float:right;>[[#Начало|В начало]]</div><br clear=all />
 
</div>
 
</div>
  
Строка 114: Строка 233:
 
<div class="shadow radius sbstyle">
 
<div class="shadow radius sbstyle">
 
<div class="row">
 
<div class="row">
−
<div class="large-10 small-10 large-centered small-centered columns rubric" style="background-color:lightgrey;">Это Интересно</div>
+
<div class="large-10 small-10 large-centered small-centered columns rubric" style="background-color:lightgrey;">Комбинаторика вокруг нас</div>
 
</div>
 
</div>
−
1. Среди предметов, положенных в пирамиду, где 35 веков назад был похоронен египетский фараон Тутанхамон, нашли разграфленную доску с тремя горизонталями и фигурки для древней игры «сенет». Позже появились нарды, шашки и шахматы.
+
Математика – всего лишь игра, в которую играют согласно простым правилам и пользуются при этом ничего не значащими обозначениями.
 +
                      Давид Гильберт
 +
 
 +
 
 +
Игра не только  доставляет удовольствие и радость, позволяет полноценно отдыхать, но она же учит, тренирует интеллект. Можно с уверенностью утверждать, что использование достижений математики  служит основой для создания новых занимательных задач и для дальнейшего развития теории игр.
 +
 
 +
'''Кубик Рубика''' – это куб, как бы разрезанный на 27 одинаковых кубиков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубиков, примыкающий к одной грани куба, вокруг ее центра. При этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение. Теоретически из любого состояния кубика можно вернуться в исходное, не более чем за 23 хода.
 +
 
 +
{{center|[[Файл:Лев_Голуб_юный_чемпион_Украины.mp4|start=1]]}}
 +
 
 +
Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 секунды. А в наше время дети собирают за считанные секунды. Давайте убедимся
  
−
2. Первое упоминание о вопросах, близких к комбинаторным, встречаются в китайских рукописях под названием  «Книга перемен».
+
'''Стрелочки'''
  
−
3.Значительный толчок в развитию комбинаторики дали азартные игры, в особенности игра в кости.
+
Необходимо от каждой клетки с числом провести стрелочки длиной в одну клетку так, чтобы их количество равнялось исходному числу, причем клетка с числом не учитывается. Стрелочки должны располагаться вертикально или горизонтально. Стрелочки должны быть во всех пустых клетках.
  
−
4. С помощью комбинаторного метода можно прочитать забытые письменности, освоенного на наблюдениях над текстом, на сопоставлении повторяемости комбинаций.
+
{{center|[[Файл:Стрелочки.gif]]}}
  
−
5. Кубик Рубика – это куб, как бы разрезанный на 27 одинаковых кубиков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубиков, примыкающий к одной грани куба, вокруг ее центра. При этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение. Теоретически из любого состояния кубика можно вернуться в исходное, не более чем за 23 хода.
+
'''Судоку'''
  
−
<div class="show-for-large-up">{{center|[[Файл:Кубик_рубик.png|450px]]}}</div>
+
Необходимо расставить  в свободные клетки числа от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом квадрате, все эти числа  встречались только один  раз.
−
<div class="hide-for-large-up">{{center|[[Файл:Кубик_рубик.png|450px]]}}</div>
 
  
−
</div>
+
{{center|[[Файл:Судоку_.gif]]}}
 +
 
 +
'''Лесенка'''
 +
 
 +
Необходимо найти такой путь от вершины пирамиды к ее основанию, чтобы все числа в нем были разными.
 +
 
 +
{{center|[[Файл:Лесенка.gif]]}}
  
 +
'''Пирамида'''
  
−
<!-- четвертый элемент сайдбара лайфхак -->
+
Необходимо заполнить ячейки числами от 1 до 9 по следующему правилу: число в ячейке должно равняться сумме или разности двух чисел в ячейках ниже, при чем в каждой строке пирамиды числа не должны повторяться.
−
<div class="shadow radius sbstyle" style="margin-top:20px;">
 
−
<div class="row">
 
−
<div class="large-10 small-10 large-centered small-centered columns rubric" style="background-color:lightgrey;">Лайфхак</div>
 
−
</div>
 
  
−
Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 секунды. А в наше время дети собирают за считанные секунды. Давайте убедимся
+
{{center|[[Файл:Пирамида.gif]]}}
  
−
<div class="show-for-large-up">{{center|[[Файл:РЕБЕНОК_ГЕНИЙ_собрал_кубик_Рубика_за_7_секунд.mp4|450px]]}}</div>
+
'''Крестики-нолики'''
−
<div class="hide-for-large-up">{{center|[[Файл:РЕБЕНОК_ГЕНИЙ_собрал_кубик_Рубика_за_7_секунд.mp4|450px]]}}</div>
+
Самая известная древняя игра. В квадрате, разделенном на девять клеток, игроки по очереди ставят в свободную клетку свой знак: крестик или нолик, стараясь выстроить три крестика или три нолика подряд. Тот, кто первым сделает это, тот и выигрывает.
  
−
<div class="show-for-large-up">{{center|[[Файл:11_комбинаторика.png|450px]]}}</div>
+
Если не делать ошибок, то игра оканчивается в ничью. Выиграть можно только в том случае, если противник ошибется. Самый правильный ход –занять угловую клетку. И если партнер не ответит на это своим знаком в центре, то он проиграл.
−
<div class="hide-for-large-up">{{center|[[Файл:11_комбинаторика.png|450px]]}}</div>
 
  
−
<div class="show-for-large-up">{{center|[[Файл:88_комбинаторика.png|450px]]}}</div>
+
{{center|[[Файл:Крестики_нолики.gif]]}}
−
<div class="hide-for-large-up">{{center|[[Файл:88_комбинаторика.png|450px]]}}</div>
 
  
 +
<!-- четвертый элемент сайдбара лайфхак -->
 +
<div class="shadow radius sbstyle" style="margin-top:20px;">
 +
<div class="row">
 +
<div class="large-10 small-10 large-centered small-centered columns rubric" style="background-color:lightgrey;">Области применения комбинаторики</div>
 
</div>
 
</div>
 +
Решать комбинаторные задачи нам приходится постоянно. Например, сколько различных сочетаний  букв нужно учитывать филологу? Сколько разных нарядов может придумать модельер из трех различных тканей? Как составить список покупок, расписание уроков, футбольную команду, собрать кубик Рубика, припарковаться, приготовить блюдо, рассадить учеников в классе, расставить книги по полкам, сервировать стол? Многие детские игры начинаются со считалок, бросания жребия. Гадания на картах, спичках и ромашке также основаны на комбинаторике. И даже поэзия не обходится без комбинаторики! Стихи и музыка, графика и живопись – все это  комбинаторные процессы. Недаром в этих областях искусства «компьютеры» добились впечатляющих успехов. И наконец, все люди – всего лишь комбинация генов в молекулах ДНК!
  
 +
[[Файл:Применение_комбинаторики.mp4]]
 +
</div>
  
 
<!-- четвертый элемент сайдбара лайфхак -->
 
<!-- четвертый элемент сайдбара лайфхак -->
 
<div class="shadow radius sbstyle" style="margin-top:20px;">
 
<div class="shadow radius sbstyle" style="margin-top:20px;">
 
<div class="row">
 
<div class="row">
−
<div class="large-10 small-10 large-centered small-centered columns rubric" style="background-color:lightgrey;">Отгадай ребусы</div>
+
<div class="large-10 small-10 large-centered small-centered columns rubric" style="background-color:lightgrey;">Ребусы</div>
 
</div>
 
</div>
−
Математические фокусы — самые простые в исполнении. Для них не нужен реквизит, длительная подготовка и специальное место для демонстрации. Смысл таких фокусов — в отгадывании чисел, задуманных зрителями, или в каких-нибудь операциях над ними. Все чудеса основаны на математических закономерностях, такие фокусы можно проделывать на уроках математики. Смотрим и учимся математической магии.
+
 
−
1.
+
<ul class=" example-orbit" data-orbit="" data-options="animation:slide; pause_on_hover:true; animation_speed:500; navigation_arrows:true; resume_on_mouseout: true; timer_speed:4500;" >
−
<div class="show-for-large-up">{{center|[[Файл:Ребус1_комбинаторика.png|450px]]}}</div>
+
  <li class="active">
−
<div class="hide-for-large-up">{{center|[[Файл:Ребус1_комбинаторика.png|450px]]}}</div>
+
    [[file:Ребус_№_1_.png]]
−
2.
+
  </li>
−
<div class="show-for-large-up">{{center|[[Файл:Ребус2_комбинаторика.png|450px]]}}</div>
+
<li>
−
<div class="hide-for-large-up">{{center|[[Файл:Ребус2_комбинаторика.png|450px]]}}</div>
+
    [[file:Ребус_№_2.png]]
−
3.
+
  </li>
−
<div class="show-for-large-up">{{center|[[Файл:Ребус3_комбинаторика.png|450px]]}}</div>
+
<li>
−
<div class="hide-for-large-up">{{center|[[Файл:Ребус3_комбинаторика.png|450px]]}}</div>
+
    [[file:Ребус № 3 Комбинаторика.png]]
−
4.
+
  </li>
−
<div class="show-for-large-up">{{center|[[Файл:Ребус4_комбинаторика.png|450px]]}}</div>
+
<li>
−
<div class="hide-for-large-up">{{center|[[Файл:Ребус4_комбинаторика.png|450px]]}}</div>
+
    [[file:Ребус_№_4_.png]]
−
5.
+
  </li>
−
<div class="show-for-large-up">{{center|[[Файл:Ребус5_комбинаторика.png|450px]]}}</div>
+
<li>
−
<div class="hide-for-large-up">{{center|[[Файл:Ребус5_комбинаторика.png|450px]]}}</div>
+
    [[file:Ребус_№_5_.png]]
 +
  </li>
 +
</ul>
 
</div>
 
</div>
  
Строка 183: Строка 321:
 
# Исход
 
# Исход
 
</div>
 
</div>
 +
<div class="sbstyle">
 +
<div class="row">
 +
<div class="large-10 small-10 large-centered small-centered columns rubric" style="margin-top:20px">Пройди тестирование</div>
 +
</div>
 +
 +
</div></div>
 +
{{lang|:KR:Математика: Комбинаториканын негиздери}}
 +
[[Category:Средняя школа]]
 +
[[Category:Математика]]

Текущая версия на 08:48, 22 октября 2018

История развития комбинаторики

Еще в доисторическую эпоху люди столкнулись с задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке, отыскивать среди разных расположений наилучшие, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов – во время работы. Украшения на одежде, рисунок на посуде, перья в оперении стрел также располагались определенным способом. По мере усложнения производственных и общественных отношений все шире приходилось пользоваться общими понятиями о порядке, иерархии, группировании. Развитие ремесел и торговли происходило в том же направлении. Комбинаторные навыки оказались полезными и во время отдыха. Так наряду с состязанием в беге, прыжках, метании диска появились игры, требовавшие, в первую очередь, умения рассчитывать, составлять план и предвидеть действия противника.

Среди предметов, положенных в пирамиду, где 35 веков назад был похоронен египетский фараон Тутанхамон, нашли разграфленную доску с тремя горизонталями и фигурки для древней игры «сенет». Позже появились нарды, шашки и шахматы. В каждой из этих игр приходилось рассматривать различные сочетания передвигаемых фигур, и выигрывал тот, кто их лучше изучил и знал выигрывающие комбинации.

В начало

Понятие комбинаторика

Комбинато́рика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка); в переводе от латинского combinare – соединять, сочетать. Комбинаторика связана с другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний.

Рассмотрим простой пример. Допустим, у нас есть банки с краской четырех цветов: красной (К), желтой (Ж), зеленой (3) и коричневой (Кор), и нам нужно разложить их по коробкам, по две разные банки в каждую. Мы можем сделать это следующим образом:

Простой пример.gif
Простой пример.gif

У нас получилось шесть различных способов, так как если в одной коробке находятся банки с желтой и красной красками, то она полностью идентична той, где лежат банки с красной и желтой. Но если мы хотим парными цветами раскрасить флаги, то сделать это можно будет двенадцатью способами, так как красно-желтый флаг не является идентичным желто-красному.

Простой пример 1.gif
Простой пример 1.gif
В начало

Основные формулы комбинаторики

Правила сложения Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m + n способами.

Пример 1. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?

Решение: По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу сложения, можно осуществить 5 + 4 = 9 способами.

Ответ: 9 способов.

Пример 2. Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?

Решение: 1 способ: перебор вариантов. Для того, чтобы не пропустить и не повторить ни одно из чисел, будем записывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и, наконец, с цифры 7: 14, 17, 41, 47, 71, 74.

Ответ: 6 чисел.

2 способ: дерево возможных вариантов. Для этой задачи построена специальная схема. Ставим звездочку. Далее отводим от звездочки 3 отрезка. Так как в условии задачи даны 3 цифры – 1, 4, 7, то на концах отрезков ставим цифры 1, 4, 7. Далее от каждой цифры проводим по 2 отрезка. На концах этих отрезков записываем также цифры 1, 4, 7. Получились числа: 14, 17, 41 47, 71, 74. То есть всего получилось 6 чисел. Эта схема действительно похожа на дерево, правда «вверх ногами» и без ствола.

Пример 2 2 способ.gif
Пример 2 2 способ.gif

Правила умножения Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать п способами, то выбор пары (А, В) в указанном порядке можно осуществить m ∙ п способами.

Пример 3. Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?

Решение: Первую цифру двузначного числа можно выбрать тремя способами. Так как после выбора первой цифры останутся две, то вторую цифру можно выбрать из оставшихся цифр уже двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 3∙2, т.е. 6.

Ответ: 6 чисел.

Факториал. Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n. Обозначение n!

0! = 1

1!=1

2! = 1∙ 2 = 2

3! = 1∙ 2 ∙ 3 = 6

4! = 1∙ 2 ∙ 3 ∙ 4 =24

5! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120

6! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720

7! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 = 5 040

8! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40 320

9! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 = 362 880

10! = 1∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 ∙ 10 = 3 628 880

Свойства комбинаторики: перестановки, сочетание, размещение

Шахматная доска абстрация.jpg
Шахматная доска абстрация.jpg

Перестановкой называется конечное множество, в котором установлен порядок элементов. Число всевозможных перестановок из n элементов вычисляется по формуле: Pn = n!

Пример 4. Сколькими способами могут быть расставлены восемь участниц финального забега на восьми беговых дорожках?

Решение. P8 = 8! = 40 320

Размещением Аkn из n элементов конечного множества по k, где k≤n, называют упорядоченное множество, состоящее из k элементов и вычисляется по формуле:

Formula razme.png
Formula razme.png

Пример 5.

Из 12 учащихся нужно отобрать по одному человеку для участия в городских олимпиадах по математике, физике, истории и географии. Каждый из учащихся участвует только в одной олимпиаде. Сколькими способами это можно сделать?

Решение.

Пример № 5.png
Пример № 5.png

Подмножества, составленные из n элементов данного множества и содержащие k элементов в каждом подмножестве, называют сочетаниями из n элементов по k. (Сочетания различаются только элементами, порядок их не важен: ab и ba – это одно и тоже сочетание) и вычисляется по формуле: .

Формула сочетаний.png
Формула сочетаний.png

Число размещений, перестановок и сочетаний связаны равенством: .

Число размещений, перестановок и сочетаний.png
Число размещений, перестановок и сочетаний.png

Различие между перестановками, размещениями, сочетаниями: В случае перестановок берутся все элементы и изменяется только их местоположение. В случае размещений берётся только часть элементов и важно расположение элементов друг относительно друга. В случае сочетаний берётся только часть элементов и не имеет значения расположение элементов друг относительно друга.

В начало

Вероятность. Основные понятия

Наблюдение явления, опыт, эксперимент, которые можно проводить многократно, в теории вероятностей принято называть испытанием. Результат, исход испытания называется событием. Например, сдача экзамена - это испытание; получение определенной отметки – событие, бросание игрального кубика - это испытание; появление того или иного числа очков на брошенной игральной кости - событие.

Вероятность – это число, характеризующее степень возможности появления события. Каждый из возможных результатов испытания называется элементарным исходом.

Вероятностью P события А называют отношение числа благоприятствующих этому событию исходов к общему числу всех равновозможных несовместных элементарных исходов, образующих полную группу. Вероятность P события А определяется по формуле Р = m/n , где m – число элементарных исходов, благоприятствующих A; n – число всех возможных элементарных исходов испытания.

Задача На шести одинаковых карточках написаны буквы К, Б, И, К, Е, Ш. Карточки перемешиваются и наугад раскладываются в ряд. Найдите, чему равна вероятность того, что получится слово БИШКЕК.

Задача Бишкек.gif
Задача Бишкек.gif

Решение. Искомая вероятность вычисляется по классической формуле Р = m/n , где n - общее количество вариантов, а m - количество вариантов, соответствующих данному событию. В данном случае n = 6! = 720 (количество перестановок из 6 карточек); m = 2 (в данном слове буква "К" повторяется дважды, а остальные по одному разу). Следовательно, Р=2/720=1/360.

Задача «Волк, козел и капуста»

Крестьянину нужно перевезти через реку волка, козла и капусту. Лодка так мала, что в ней кроме крестьянина может поместиться только или волк, или козел, или капуста. Но если оставить волка с козлом, он его съест, а если оставить козла с капустой, то будет съедена капуста. Как быть крестьянину?

Для решения требуется расположить путем взаимной перестановки элементов и в соответствии с условием задачи в определенном порядке. Крестьянину следует начать переправу с перевозки козла. Затем он возвращается и берет волка, которого перевозит на другой берег и оставляет там, а козла возвращает назад на предыдущий берег. Оттуда забирает капусту и перевозит ее к волку. А затем возвращается и забирает козла.

Задача Волк коза капутса.gif
Задача Волк коза капутса.gif
В начало

Комбинаторика в программировании

Комбинаторика – это настоящий клад для программистов, так как помогает анализировать различные алгоритмы, выбор оптимальной стратегии перебора. Комбинаторные формулы требуются для расчётов вероятностей, а те, в свою очередь, для проверки статистических гипотез. Особое внимание уделяют программисты комбинаторным задачам с пандигитальными числами, для генерирования которых используют программу Generics Combinatorics.

Пандигитальными называются числа, составленные из неповторяющихся цифр и не начинающиеся с нуля. Например, 123456789.

Задачи с пандигитальными числами решаются почти так же, как и логические, и даже проще, поскольку все комбинаторные объекты представляют собой обычные числа.

Число 123456789 — наименьшее пандигитальное число в десятичной системе счисления. При умножение на 8 результатом будет 987654312 — другое пандигитальное число, близкое к палиндрому исходного, за исключением двух последних цифр, обменявшихся местами. Это число также сохраняет свою пандигитальность при умножении:

- на 2 123456789 ∙ 2 = 246913578,

- на 4 123456789 ∙ 4 = 493827156,

- на 5 123456789 ∙ 5 = 617283945,

- на 7 123456789 ∙ 7 = 864197523.

В качестве примера другого числа, сохраняющего свою пандигитальность при умножении на ряд коэффициентов, можно назвать 1098765432, перемножаемое таким образом на 2, 4, 5 и 7. Если добавить к числу 123456789 умноженному на 8 число 9, будет получен полный палиндром этого числа. Если множитель и слагаемое увеличить на единицу, результатом аналогичных операций станут числа, состоящие из одних единиц разрядностью от десяти до двух.

Пандигитальные квадраты.gif
Пандигитальные квадраты.gif
В начало

Полезные ссылки

Вся наша жизнь состоит из множества разнообразных программ. Чтобы запустить ту или иную программу нужно ввести соответствующий верный пароль. В качестве кода в зависимости от рода программы могут выступать всевозможные цифры, слова или комбинации слов, поведение или действие. Комбинаторика используется в музыке, в мебельной деятельности, в различных играх (нарды, шашки, шахматы) и т.д. Читайте подробнее: [Электронный ресурс] // 2011-2017 Сила знаний URL: http://ya-znau.ru/znaniya/zn/80 (Дата посещения: 19.04.2018)

Различные комбинаторные задачи с подробным решением можно посмотреть здесь: [Электронный ресурс] //mathprofi.ru, Александр Емелин, 2010-2018 URL: http://www.mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html (Дата посещения: 19.04.2018)

Необходимые теоретические сведения и формулы для решения комбинаторных задач школьного уровня можно посмотреть здесь: [Электронный ресурс] // Харламов А.В. элементы комбинаторики, 2016г. // URL: http://elibrary.sgu.ru/uch_lit/1626.pdf (Дата посещения: 21.04.2018)

Поиграем? Пусть имеется одна или несколько групп предметов. Играющие берут по очереди предметы из групп по правилам, которые заранее устанавливают: какое количество предметов разрешается брать за один раз и из скольких групп. Существует множество вариантов игры, и для большинства известна наилучшая стратегия, ведущая к выигрышу.:[Электронный ресурс] // ЮЦ «Восстание-6» URL: https://logic-games.spb.ru/nim/ (Дата посещения: 22.04.2018)

В начало

Глоссарий

Дискре́тность (от лат. discretus — разделённый, прерывистый) — свойство, противопоставляемое непрерывности, прерывность. Под дискретностью понимают: нечто, изменяющееся между несколькими различными стабильными состояниями, например механические часы, которые передвигают минутную стрелку дискретно (скачкообразно) на 1/60 часть окружности; нечто, состоящее из отдельных частей, прерывистость, дробность.

Палиндро́м (от др.-греч. πάλιν — «назад, снова» и др.-греч. δρóμος — «бег, движение»)— число, буквосочетание, слово или текст, одинаково читающееся в обоих направлениях.

Пандигитальные числа – это числа, составленные из неповторяющихся цифр и не начинающиеся с нуля.

Су́тра (санскр. सूत्र sūtra IAST, «нить», пали: sutta) — в древнеиндийской литературе лаконичное и отрывочное высказывание, афоризмы, позднее — своды таких высказываний. В сутрах излагались различные отрасли знания, почти все религиозно-философские учения Древней Индии.

В начало

Библиография

  • Комбинаторика: основные правила и формулы. : [Электронный ресурс] // 2011-2017 Сила знаний URL: http://ya-znau.ru/znaniya/zn/80 (Дата посещения: 19.04.2018)
  • Задачи по комбинаторике. Примеры решений.: [Электронный ресурс] //mathprofi.ru, Александр Емелин, 2010-2018 URL: *http://www.mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html (Дата посещения: 19.04.2018)
  • Сканворды, кроссворды и головоломки: [Электронный ресурс] // Пискунов Алексей © 2009-2018 http://www.graycell.ru/index.html (Дата посещения: 19.04.2018)
  • Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика: М.: ФИМА, МЦНМО, 2006. — 400 с.
  • Мир математики: в 40 т. Т.21: Ламберто Гарсия дель Сид. Замечательные числа. Ноль, 666, и другие бестии./Пер. с исп. –М.: Де Агостини, 2014. – 160 с.
В начало

Комбинаторика вокруг нас

Математика – всего лишь игра, в которую играют согласно простым правилам и пользуются при этом ничего не значащими обозначениями. 

                     Давид Гильберт


Игра не только доставляет удовольствие и радость, позволяет полноценно отдыхать, но она же учит, тренирует интеллект. Можно с уверенностью утверждать, что использование достижений математики служит основой для создания новых занимательных задач и для дальнейшего развития теории игр.

Кубик Рубика – это куб, как бы разрезанный на 27 одинаковых кубиков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубиков, примыкающий к одной грани куба, вокруг ее центра. При этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение. Теоретически из любого состояния кубика можно вернуться в исходное, не более чем за 23 хода.

Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 секунды. А в наше время дети собирают за считанные секунды. Давайте убедимся

Стрелочки

Необходимо от каждой клетки с числом провести стрелочки длиной в одну клетку так, чтобы их количество равнялось исходному числу, причем клетка с числом не учитывается. Стрелочки должны располагаться вертикально или горизонтально. Стрелочки должны быть во всех пустых клетках.

Стрелочки.gif

Судоку

Необходимо расставить в свободные клетки числа от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом квадрате, все эти числа встречались только один раз.

Судоку .gif

Лесенка

Необходимо найти такой путь от вершины пирамиды к ее основанию, чтобы все числа в нем были разными.

Лесенка.gif

Пирамида

Необходимо заполнить ячейки числами от 1 до 9 по следующему правилу: число в ячейке должно равняться сумме или разности двух чисел в ячейках ниже, при чем в каждой строке пирамиды числа не должны повторяться.

Пирамида.gif

Крестики-нолики Самая известная древняя игра. В квадрате, разделенном на девять клеток, игроки по очереди ставят в свободную клетку свой знак: крестик или нолик, стараясь выстроить три крестика или три нолика подряд. Тот, кто первым сделает это, тот и выигрывает.

Если не делать ошибок, то игра оканчивается в ничью. Выиграть можно только в том случае, если противник ошибется. Самый правильный ход –занять угловую клетку. И если партнер не ответит на это своим знаком в центре, то он проиграл.

Крестики нолики.gif
Области применения комбинаторики

Решать комбинаторные задачи нам приходится постоянно. Например, сколько различных сочетаний букв нужно учитывать филологу? Сколько разных нарядов может придумать модельер из трех различных тканей? Как составить список покупок, расписание уроков, футбольную команду, собрать кубик Рубика, припарковаться, приготовить блюдо, рассадить учеников в классе, расставить книги по полкам, сервировать стол? Многие детские игры начинаются со считалок, бросания жребия. Гадания на картах, спичках и ромашке также основаны на комбинаторике. И даже поэзия не обходится без комбинаторики! Стихи и музыка, графика и живопись – все это комбинаторные процессы. Недаром в этих областях искусства «компьютеры» добились впечатляющих успехов. И наконец, все люди – всего лишь комбинация генов в молекулах ДНК!

Ребусы
  • Ребус № 1 .png
  • Ребус № 2.png
  • Ребус № 3 Комбинаторика.png
  • Ребус № 4 .png
  • Ребус № 5 .png

Ответы:

  1. Вариант
  2. Сочетания
  3. Факториал
  4. Событие
  5. Исход
Пройди тестирование
Пройди тестирование
Источник — «https://bb.edu.gov.kg/index.php?title=Математика:_Основы_комбинаторики&oldid=27430»