Коллеги - педагогический журнал Казахстана

Наша библиотека

Главная » Файлы » В помощь учителю » Математика

Научный проект "Комбинаторные задачи и методы их решения"
[ Скачать с сервера (457.5 Kb) ] 2014-02-04, 7:58 AM
Министерство образования и науки Республики Казахстан
Восточно-Казахстанская область

Направление: математика
Секция: математика



Тема: «Комбинаторные задачи и методы их решения»

Автор проекта: Лунегова Алиса
ВКО. Г. Риддер
КГУ «Средняя школа№3»
7 «Б» класс

Руководитель: Которова Н.С.
учитель математики



Г. Риддер
2013

Аннотация (абстракт)
Аталған жұмыс комбинаторлық есептерді шешу үшін арнайы формулаларды қолдану жолдарын зерттеуге арналған. Бұл комбинаториканың тапсырмаларын толық шешу міндеттері мен қолдану негіздері, формулалары көрсетілген.
Шешуі бар комбинаторлық есептердің жинағы – аталған жұмыстың нәтижесі іспеттес. Ол оқушыларды математика пәні бойынша өткізілетін байқаулар мен олимпиадаларға даярлау үшін қосымша материал ретінде қолдануға болады.

Аннотация
Данная работа посвящена исследованию способов применения специальных формул для решения комбинаторных задач. Она содержит задачи с подробными решениями и обоснованием применения той или иной формулы комбинаторики.
Результат данной работы – сборник комбинаторных задач с решениями. Он может быть использован в качестве дополнительного материала для подготовки учащихся к конкурсам и олимпиадам по математике.

Annotation
This work is dedicated to the using of special formulas to solve combinatorial problems. The work contains detailed problem and explanation of using this or that formulas.
The result of this work is -the textbook of combinatorial problems with answers - It may be used as additional materials for preparing of Olympiads in Maths

Комбинаторлық есептер және оны шешу жолдары» атты
Лунегова Алисаның жобалық жұмысына
ПІКІР
Жұмыс комбинаторлық есептерді шешу үшін арнайы формулаларды қолдану жолдарын үйрену мәселесіне арналған. Алиса жұмысын арнайы әдебиеттерді талдау барысында байқау тапсырмалары мен түрлі жинақтарды талдауда жинастырылған материалдар негізінде даярлады.
Жұмыстың өзектілігі еш күмәнді келтірмейді. Математиканың «Комбинаторика» тарауы есептердің шешілуінің түрлі нұсқаларын таңдап талдауға үйретеді, қалыпсыз түрде ойлауға үйретеді, ойын, қиялын, зеректігін дамытады, шығармашылық қабілеттерін дамытады. Ал бұлардың барлығы, әрине, өмірде қажет.
Жұмыс жоғары деңгейде орындалған, комбинаторлық есептерді шешу үшін қажетті теориялық материал берілген. Жұмыста қарастырылған комбинаториканың барлық формулалары және комбинаторлық есептерді шешу жолдары нақты мысалдар арқылы көрсетілген.
Автор өз бетімен түрлі типті практикалық тапсырмаларды іріктеп, комбинаторлық есептер жинағына жүйелендірді.
Жұмыс нақты құрастырылған: кіріспе бөлімі, жұмыстың міндеттері, негізгі бөлім, әдебиеттер тізімі берілген.

Математика мұғалімі Которова Н.С.

Отзыв на научный проект Лунеговой Алисы
«Комбинаторные задачи и методы их решения»

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


Учитель математики Которова Н. С.

Review
on the research project
by Lunegova Alisa
"Combinatorial problems and methods of their solutions "

The work is devoted to studying ways of using special formulas to solve combinatorial problems. The work was prepared on the basis of material collected in the course of the study of special literature, analysis of the competitive task assignments and various compilations.
The relevance of this work is not in doubt. A branch of mathematics "Combinatorics " teaches to reason, think outside of the box, touch various solutions to the problem , develop logic, imagination and wit , develops creativity. And all of this, of course, will be necessary in life.
The project is performed at a sufficiently high level, contains theoretical material to solve combinatorial problems. All formulas of combinatorics and their use in solving combinatorial problems are illustrated with specific examples.
The author chose various types of practical tasks and systematized the collection of combinatorial problems with solutions.

The work is clearly structured : there are introduction , task , main content , a list of the studied literature.

Math teacher Korotova NS

Оглавление
1. Введение.
2. Основные комбинаторные формулы
1)Размещения с повторениями
2) Размещения без повторений
3) Перестановки без повторений
4) Перестановки с повторениями
5) Сочетания
3. Заключение
4. Сборник комбинаторных задач с решением

"Учимся не для школы, а для жизни" (Сенека).

1.Введение

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

Цель моего проекта – исследовать способы применения специальных формул для решения комбинаторных задач; проиллюстрировать их на конкретных примерах.
Предмет исследования – комбинаторные задачи, включенные в конкурсные и олимпиадные задания.
Гипотеза исследования – знание специальных формул и умение анализировать условие задачи, даёт возможность решать любые задачи комбинаторики .
Цель, предмет и гипотеза исследования, обусловили выдвижение и решение следующих задач:
1) изучить основные формулы комбинаторики
2) решать комбинаторные задачи с использованием изученных формул
3) систематизировать работу по теме в сборник комбинаторных задач с решениями, способствующих усвоению, закреплению, проверке знаний по формулам комбинаторики и их применению в решении комбинаторных задач.











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

Комбинаторика – раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторики является изучение комбинаторных конфигураций, в частности, вопросы их существования, алгоритмы построения, решение задач на перечисление. Примерами комбинаторных конфигураций являются, размещения перестановки и сочетания.
Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие:
1) образование упорядоченных подмножеств – составление размещений;
2) образование упорядоченных множеств, состоящее в установлении определенного порядка следования элементов множества друг за другом, составление перестановок;
3) образование подмножеств, состоящее в выделении из данного множества некоторой части его элементов, - составление сочетаний;
Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения (умножения).
1) Размещения с повторениями

Размещениями с повторениями из n элементов по k называются всевозможные комбинации по k элементов, составленные из элементов данных n видов. При этом в комбинацию могут входить и предметы одного вида, а две комбинации считаются различными, если они отличаются друг от друга или видом входящих в них элементов, или порядком этих элементов.

Количество размещений с повторениями обозначается и вычисляется по формуле

Задача 1
Для того чтобы открыть камеру хранения, используется комбинация из 4 цифр (от 0 до 9), набираемая на 4 колесиках. Сколько различных комбинаций существует?
Решение.
Из условия задачи следует, что необходимо составить всевозможные комбинации по 4 элемента из данных 10. По формуле размещений с повторением получаем:
2) Размещения без повторений

Как изменится решение задачи о камере хранения, если известно, что цифры, набираемые на колесиках, различны.
Решение.
Вариантов выбора первой цифры 10 (от 0 до 9). Так как повторения быть не может, то вариантов выбора второй цифры всего 9. Аналогично для выбора третьей цифры остается 8 вариантов, для выбора четвертой – 7. По правилу произведения получаем, что всего комбинаций, в которых все числа различны, 10987=5 040.

Данная задача относится к классу задач о размещении без повторений.
Размещениями без повторений из n элементов по k называются всевозможные комбинации по k элементов, составленные из элементов данных n видов. При этом две комбинации считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.
Количество размещений без повторений обозначают . Общее правило вычисления количества размещений:
.
Доказательство.
Действительно, на первом шаге можно выбрать любой из n имеющихся предметов. Если этот выбор уже сделан, то на втором шаге приходится выбирать из n – 1 предметов – ведь повторный выбор сделать уже нельзя. Точно так же на третьем шаге для выбора остается n – 2 предмета и т. д. Используя правило произведения, получим требуемую формулу.
Произведение всех натуральных чисел от единицы до n обозначают символом n! (читается «эн факториал»). Используя знак факториала, можно, например, записать:
1! = 1,
2! = 2∙1 = 2,
3! = 3 ∙2 ∙1 = 6,
4! = 4 ∙3 ∙2 ∙1 = 24,
Будем считать 0! = 1.

Для нахождения числа размещений из n элементов по k элементов можно также применять следующую формулу:


Задача 2
В первенстве России по футболу участвуют 17 команд. Разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами они могут быть распределены?
Решение.
Переформулируем задачу: Сколько существует комбинаций из 17 элементов по 3, если важны порядок элементов в комбинации, состав элементов и в комбинацию не могут входить элементы одного типа. (Повторения здесь быть не может – одна и та же команда не может получить и золотую и серебреную медаль.)
Эта задача относится к задачам на размещения без повторения. По формуле получаем:


Ответ: медали могут распределиться 4080 способами.
Задача 3
Автомобильные номера некоторой страны состоят из 3 букв (все буквы различны) и четырех цифр (цифры могут повторяться). Сколько максимально машин может быть в этой стране, если в её алфавите 26 букв?
Решение.
Число комбинаций по 3 буквы из данных 26, при условии, что буквы не могут повторяться, определим с помощью формулы для вычисления количества размещений без повторений:

Число комбинаций по 4 цифры из данных 10, если в комбинацию могут входить одинаковые цифры, найдем с помощью формулы для вычисления количества размещений с повторениями:
Тогда по правилу произведения, различных автомобильных номеров будет 
Ответ: 156 000 000 машин может быть максимально.

3) Перестановки
При составлении размещений без повторений из n элементов по k мы получали расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все n элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называют перестановками из n элементов или n-перестановками.
Перестановками из n элементов называют всевозможные комбинации из n элементов, каждая из которых содержит все элементы по одному разу. Комбинации отличаются друг от друга лишь порядком элементов.

Число n-перестановок обозначают через .Общее правило вычисления количества перестановок:

Рассмотрим несколько задач, решаемых с применением этой формулы.
Задача 4
Сколькими способами можно расположить на книжной полке 5 томов детской энциклопедии?
Решение
Так как на полке располагаем все 5 томов, то различные расположения отличаются только порядком, но не составом. По формуле перестановок имеем Р5 = 5!= 120
Ответ: 120.
Задача 5
В танцевальном кружке 6 парней и 6 девушек. Сколькими способами их можно разбить на пары парень – девушка?
Решение.
Выстроим парней в одну линию в произвольном порядке. Пусть каждая девушка выбирает себе пару. Тогда количество способов разбиения на пары равно количеству способов переставить 6 различных предметов, то есть равно Р6 = 6!=720.
Ответ: 720.
Задача 6
Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?
Решение.
Если бы девушки стояли на месте, то получилось бы 7! способов. Так как танцующие кружатся, то их положение относительно окружающих предметов не существенно, а важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении танцовщиц, необходимо считать одинаковыми. Из каждой перестановки получим еще шесть новых путем
вращения. Значит, число 7! необходимо разделить на 7. Получаем 7!:7=6!=720 различных перестановок девушек в хороводе.
Задача 7
Сколькими способами можно рассадить за круглым столом 6 мужчин и 6 женщин таким образом, чтобы мужчины и женщины чередовались?
Решение
Пронумеруем все места за круглым столом подряд от 1 до 12.
Пусть мужчины занимают нечётные места 1,3,5,7,9 и 11, а женщины четные места 2,4,6,8,10 и 12.Рассадить мужчин на 6 нечётных местах можно Р6 = 6! способами; каждому способу посадки 6 мужчин на 6 нечётных местах соответствует Р6 = 6! способов посадки 6 женщин на 6 чётных местах. Поэтому общее число способов рассадить за круглым столом 6 мужчин и 6 женщин таким образом, чтобы мужчины и женщины чередовались, по правилу произведения равно .
Ответ: (6!)2.
Задача 8
Сколько существует перестановок из n различных элементов, в которых один данный элемент идет впереди другого данного элемента?
Решение
Определим число перестановок, в которых данный элемент идёт впереди другого данного элемента . Могут быть следующие случаи: стоит на первом месте, стоит на втором месте,….., стоит на (n -1) месте, а стоит правее , число таких случаев равно n – 1. Каждому из этих способов соответствует (n -2)! перестановок других элементов. Следовательно, число перестановок из n элементов, в которых один данный элемент идёт впереди другого данного элемента, равно
( n - 1) (n - 2)! = (n -1)!
Ответ: (n – 1)! перестановок.
Задача 9
Сколько можно сделать перестановок из n различных элементов, в которых данные два стоят рядом?
Решение
Определим число перестановок, в которых данные 2 элемента и стоят рядом. Могут быть следующие случаи: стоит на первом месте, стоит на втором месте,….., стоит на (n -1) месте, а стоит правее , число таких случаев равно n – 1.Кроме того и можно поменять местами, и, следовательно, существует 2(n – 1) способов размещения и рядом. Каждому из этих способов соответствует (n -2)! перестановок других элементов. Следовательно, число перестановок из n различных элементов, в которых данные два стоят рядом, равно2(n-1) (n-2)! = 2 (n-1)!
Ответ: 2 (n-1)! перестановок.

Задача 10
Сколько можно сделать перестановок из n различных элементов, в которых данные два не стоят рядом?
Решение
По решению предыдущей задачи мы знаем, что число перестановок из n различных элементов, в которых данные два стоят рядом, равно
2(n-1) (n-2)! = 2 (n-1)! Число всех перестановок из n различных элементов равно n!.
Следовательно, число перестановок из n различных элементов, в которых данные два не стоят рядом, равно n! - 2 (n-1)! = (n -1)! (n – 2).
Ответ: (n -1)! (n – 2) перестановок.

4)Перестановки с повторениями
Если же некоторые переставляемые предметы одинаковы, то получается меньше перестановок – какие-то перестановки совпадают друг с другом.
Перестановками с повторениями из n1 элементов первого типа, n2 элементов второго типа, ... , nk элементов k-го типа называются всевозможные

комбинации из этих элементов, каждая из которых содержит ni элементов i-го вида. Комбинации отличаются друг от друга лишь порядком элементов.
Число перестановок с повторениями обозначают через Р(n1, n2, ..., nk). Общее правило вычисления количества перестановок с повторениями:
.
Доказательство
Если бы все элементы были различны, то число перестановок равнялось бы n!. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. Возьмем, например, перестановку, в которой сначала выписаны элементы первого типа, потом все элементы второго типа, …, наконец, все элементы k-го типа. Элементы первого типа можно переставлять n1! способами, это ничего не меняет. Точно так же ничего не меняют n2! перестановок элементов второго типа, ... , nk! перестановок элементов k-го типа. Перестановки элементов первого типа, второго типа и т. д. можно делать независимо друг от друга. По правилу произведения элементы перестановки можно переставлять n1!∙n2! ∙...∙nk! способами так, что она останется неизменной. То же самое верно и для любого другого расположения элементов. Поэтому множество всех n! перестановок распадается на части, состоящие из n1! ∙n2! ∙...∙nk! одинаковых перестановок каждая. Значит, число различных перестановок с повторениями, которые можно сделать из данных элементов, равно .
Задача 11
Сколькими способами можно поставить в ряд 3 красных, 4 синих и 5 зеленых кубиков?
Решение
По формуле перестановок с повторениями получаем: Р(3, 4, 5)= .
Ответ: 27 720 способов.

Задача 12
Сколько существует различных последовательностей длины 5, составленных из трех 1 и двух 0?
Решение
По формуле перестановок с повторениями получаем: Р( 3,2) = .
Ответ: 10 различных последовательностей.
Задача 13
Сколько существует различных пятизначных чисел, составленных из трех 1 и двух 0?

Решение
Ноль не может быть первой цифрой числа, поэтому на первом месте в числе будет стоять одна из трёх 1. Количество комбинаций из оставшихся двух единиц и двух нулей найдём по формуле перестановок с повторениями:
Р(2,2) =
Ответ: 6 чисел.

Задача 14
Имеется шесть различных кошельков. Сколькими способами можно разложить в них двенадцать одинаковых монет, чтобы пустым остался максимум один кошелёк?
Решение:
Так как пустым должен остаться максимум один кошелёк, то либо не должно быть пустых кошельков, либо пустым будет только один из шести. Рассмотрим случай, когда пустых кошельков не должно быть. Это означает, что в каждый кошелёк надо положить не менее одной монеты. Так как по одной монете уже лежит в каждом кошельке, то осталось рассмотреть все способы распределения оставшихся шести монет по шести кошелькам. Поставим в соответствие каждому размещению монет в кошельках последовательность из нулей и единиц следующим образом: сначала последовательность имеет столько нулей, сколько монет поместим в первый кошелёк, затем записываем единицу и далее пишем столько нулей, сколько монет поместим во второй кошелёк, снова единицу, затем столько нулей, сколько монет поместим в третий кошелёк, и т.д. Заканчивается последовательность таким количеством нулей, сколько монет поместим в шестой кошелёк. Значит, последовательность имеет 6 нулей и 6 – 1= 5 единиц.
Переставим всеми возможными способами 6 нулей и 5 единиц. Каждая такая перестановка определяет один из способов распределения монет в кошельках. А именно нули, расположенные до первой единицы положим в первый кошелёк, нули, расположенные между первой и второй единицей, – во второй кошелёк и так далее, нули, расположенные после пятой единицы, - в шестой кошелёк. По формуле перестановок с повторениями число таких перестановок равно
способа распределения 12 монет по шести кошелькам так, чтобы не было пустых.
Если же один кошелёк обязательно должен быть пустым, то нужно рассмотреть все способы распределения 12 монет в пять кошельков так, чтобы ни один из этих пяти не был пустым. Используя предыдущие рассуждения, получаем:
способов распределения 12 монет по пяти кошелькам так, чтобы не было пустых.
Пустым может быть любой из шести кошельков, всего 6 вариантов, тогда по правилу произведения, получаем способов распределения 12 одинаковых монет по шести разным кошелькам так, чтобы ровно один был пустым. По правилу суммы, получаем 462+1980 = 2442 способа разложить в шесть разных кошельков двенадцать одинаковых монет, чтобы пустым остался максимум один кошелёк.
Ответ: 2442 способа.

Задача15
Сколько разных слов можно составить перестановкой букв в слове
« математика»?
Решение:
В слове « математика» имеется две буквы «м», три буквы «а», две буквы «т» и ещё три различных буквы. По формуле перестановок с повторениями получаем:
Р(2,3,2,1,1,1)=
Ответ: 151200 слов.

5) Сочетания
До сих пор при составлении комбинаций из элементов различных типов нас интересовал порядок расположения элементов. Но некоторый класс задач приводит к составлению комбинаций, в которых порядок элементов совершенно не важен.
Сочетаниями из n элементов по k называют всевозможные комбинации по k элементов, составленные из данных n элементов. Комбинации отличаются друг от друга составом, но не порядком элементов.
Количество сочетаний из n элементов по k обозначают .
Формула для вычисления числа сочетаний получается из формулы для вычисления количества размещений. Составим сначала все k-сочетания из n элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получатся все k-размещения из n элементов, причем каждое только по одному разу. Элементы каждого k-сочетания можно переставить k! способами, а число этих сочетаний равно . Значит, справедлива формула . Получаем .

Задача 16
Два филателиста хотят обменяться марками. У одного для обмена есть 7 марок, у другого – 5. Сколькими способами они могут поменять две марки одного на две марки другого?
Решение.
Первый филателист должен выбрать 2 марки из 7. Он может это сделать способами. Второй должен выбрать 2 марки из 5. Он может это сделать способами. По правилу произведения получаем,

Ответ: 210 способов совершить обмен
Задача 17
На плоскости отмечено 10 точек так, что никакие три из них не лежат на одной прямой. Сколько прямых можно провести через эти точки?
Решение:
Так как никакие три точки не лежат на одной прямой, то любые две точки будут определять одну прямую, на которую другие точки не попадут. Количество прямых будет равно количеству сочетаний из 10 по 2:

Ответ: 45 прямых.

Задача 18
На плоскости отмечено 10 точек так, что никакие три из них не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках?
Решение:
Так как никакие три из данных 10 точек не лежат на одной прямой, то любые выбранные три точки можно соединить отрезками и получить треугольник. Выбрать три точки из 10 можно способами.
Ответ:120 треугольников.

3. Заключение
В заключении можно сказать, что при выполнении конкурсных или олимпиадных заданий по математике часто встречаются комбинаторные задачи, для решения которых пригодятся рассмотренные мною формулы.
Итогом данной исследовательской работы по теме явилось создание математического сборника комбинаторных задач с решениями.
Данный сборник поможет учащимся подготовиться к математическим олимпиадам и конкурсам, а также будет способствовать развитию их творческих способностей, логики, смекалки и воображения.



Литература:

1) Андреева Е. В. «Комбинаторные задачи», Москва «Чистые пруды»,2005 г.
2) И.И. Ежов, А.В. Скороход. « Элементы комбинаторики»,Москва «Наука», 1977г.
3) Перельман Я.И. «Занимательная алгебра. Занимательная геометрия.» Москва, АСТ «Астрель»,2002 год.
4) Савин А. П. «Энциклопедический словарь юного математика», Москва «Педагогика», 1985 г.
5) Фадеев Д.К., Никулин М.С., Соколовский. Элементы высшей математики
для школьников. Москва «Наука», 1987 год.
6) Элементы теории вероятностей. Математика. Приложение к газете "Первое
сентября", 1999 год, № 41, 42.

Сборник комбинаторных задач с решениями
( пособие для учащихся)



КГУ « Средняя школа№3»
Лунегова Алиса, ученица 7 «Б» класса
Руководитель: учитель математики Которова Н.С.

Риддер 2013

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

Оглавление
1. Задачи на размещения
2. Задачи на перестановки
3. Задачи на сочетания

Задачи на размещения
1) Автомобильные номера некоторой страны состоят из 3 букв (все буквы различны) и четырех цифр (цифры могут повторяться). Сколько максимально машин может быть в этой стране, если в её алфавите 26 букв?
Решение.
Число комбинаций по 3 буквы из данных 26, при условии, что буквы не могут повторяться, определим с помощью формулы для вычисления количества размещений без повторений:
=
Число комбинаций по 4 цифры из данных 10, если в комбинацию могут входить одинаковые цифры, найдем с помощью формулы для вычисления количества размещений с повторениями: =104.
Тогда по правилу произведения различных автомобильных номеров –  =15600104=156106.
Ответ: 156 000 000 машин может быть максимально.

2) Назовем натуральное число «симпатичным'», если в его записи встречаются только нечетные цифры. Сколько существует 4-значных «симпатичных» чисел?
Решение:
Число комбинаций по 4 из 5 (нечётные цифры), при условии, что цифры могут повторяться, определим по формуле размещений с повторениями . Существует 625 4-значных «симпатичных» чисел.
Ответ: 625
3) В первенстве России по футболу участвуют 17 команд. Разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами они могут быть распределены?
Решение.
Переформулируем задачу: Сколько существует комбинаций из 17 элементов по 3, если важны порядок элементов в комбинации, состав элементов и в комбинацию не могут входить элементы одного типа. (Повторения здесь быть не может – одна и та же команда не может получить и золотую и серебреную медаль.)
Эта задача относится к задачам на размещения без повторения. По формуле получаем:

Ответ: медали могут распределиться 4080 способами.
4) Алфавит племени Мумбо-Юмбо состоит из трех букв А, Б и В. Словом является любая последовательность, состоящая не более чем из 4 букв. Сколько слов в языке племени Мумбо-Юмбо?
Решение.
Количество слов, состоящих из одной буквы, будет равно 3, так как в алфавите данного племени только три буквы. Количество слов, состоящих из двух, из трёх и из четырёх букв будем считать по формуле размещений с повторениями, так как в словах буквы могут повторяться.
Количество слов из двух букв будет равно , из трёх букв: , из четырёх букв: .
Тогда всего слов в племени Мумбо-Юмбо равно 3 + 9 + 27 + 81 =120.
Ответ: 120 слов в племени.
5) Трое юношей и две девушки выбирают место работы. В городе есть три завода, где требуются рабочие в литейный цех (туда берут лишь мужчин), две ткацкие фабрики (туда приглашают лишь женщин) и две фабрики, где требуются и мужчины и женщины. Сколькими способами могут они распределиться между этими предприятиями?
Решение:
Количество способов распределения юношей найдём по формуле размещений с повторениями, учитывая, что каждый из трёх юношей может устроиться работать на пяти предприятиях: . Количество способов распределения двух девушек на четырёх предприятиях равно . Тогда по правилу произведения количество способов распределения троих юношей и двух девушек между предприятиями равно .
Ответ: 2000 способов.
6) В клубе велосипедистов считается плохим знаком иметь членский билет, в номере которого есть цифра 8. Поэтому председатель клуба решил выдавать билеты с номерами, в которые ни одна 8 не входит. Сколько было членов в группе, если известно, что использованы все трехзначные номера, не содержащие ни одной восьмерки?
Решение:
Число комбинаций по 3(трёхзначные номера) из 9 (все цифры, кроме 8), при условии, что цифры могут повторяться, определим по формуле размещений с повторениями . Значит в группе 729 членов.
Ответ: 729 членов клуба.
7) Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили два различных числа?
Решение:
Всего чисел 6, для составления дроби нужно два различных числа, значит, количество дробей найдём по формуле размещений без повторений: .
Ответ: 30 дробей.
8)Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов? А если одна полоса обязательно должна быть красной?
Решение:
Количество способов составить трёхцветный полосатый флаг из имеющегося материала 5 цветов найдём по формуле размещений без повторений
(способов)
Существует 3 способа расположения красной полосы на трёхцветном флаге. Количество выборов материала для двух полос флага (третья полоса обязательно красная) из оставшихся 4 цветов найдём по формуле размещений без повторений (способов). По правилу произведения получаем, что составить полосатый трёхцветный флаг из имеющегося материала 5 различных цветов так, чтобы одна полоса была обязательно красной, можно способами.
Ответ: 60 способов, 36 способов.
Задачи для самостоятельного решения
1) Четыре студента сдают экзамен. Сколько может быть вариантов распределения оценок, если известно, что все студенты экзамен сдали?
2) На железнодорожной станции имеется m светофоров. Сколько может быть дано различных сигналов, если каждый светофор имеет три состояния: красный, желтый, зеленый?
3) Сколькими способами можно отправить 6 писем с тремя курьерами?
4) Сколькими способами в группе студентов из 34 человек можно выбрать старосту и казначея? Если известно, что один человек не может занимать две должности сразу. Если известно, что один человек может занимать две должности сразу.
5) В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?
6) Сколькими способами можно сделать трехцветный флаг с горизонтальными полосами одинаковой ширины, если имеется материя шести различных цветов?
7) Забор состоит из 100 дощечек. У Тома Сойера есть краски 150 различных цветов. Сколько существует различных раскрасок забора, если все дощечки покрашены в разный цвет? Та же задача, но дощечки могут быть покрашены в одинаковый цвет.
8) Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4 и 5? Тот же вопрос, но при условии, что ни одна цифра не повторяется?
9) У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имен равно 300, а ему дают ровно три имени?
10) У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен?
11) Сколькими способами можно составить расписание на день из 5 различных уроков, если изучается 14 предметов?
12) В комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец и 6 чайных ложек (все чашки, блюдца и ложки отличаются друг от друга). Сколькими способами они могут накрыть стол для чаепития (каждый получает одну чашку, одно блюдце и одну ложку)?

Задачи на перестановки
1)Сколькими способами можно расположить на книжной полке 5 томов детской энциклопедии?
Решение
Так как на полке располагаем все 5 томов, то различные расположения отличаются только порядком, но не составом. По формуле перестановок имеем Р5 = 5!= 120
Ответ: 120.
2) В танцевальном кружке 6 парней и 6 девушек. Сколькими способами их можно разбить на пары парень – девушка?
Решение.
Выстроим парней в одну линию в произвольном порядке. Пусть каждая девушка выбирает себе пару. Тогда количество способов разбиения на пары равно количеству способов переставить 6 различных предметов, то есть равно Р6 = 6!=720.
Ответ: 720.

3) Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?
Решение.
Если бы девушки стояли на месте, то получилось бы 7! способов. Так как танцующие кружатся, то их положение относительно окружающих предметов не существенно, а важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении танцовщиц, необходимо считать одинаковыми. Из каждой перестановки можно получить еще шесть новых путем вращения. Значит, число 7! необходимо разделить на 7. Получаем 7!:7=6!=720 различных перестановок девушек в хороводе.
Ответ: 720.
4) Сколькими способами можно рассадить за круглым столом 6 мужчин и 6 женщин таким образом, чтобы мужчины и женщины чередовались?
Решение
Пронумеруем все места за круглым столом подряд от 1 до 12.
Пусть мужчины занимают нечётные места 1,3,5,7,9 и 11, а женщины четные места 2,4,6,8,10 и 12.Рассадить мужчин на 6 нечётных местах можно Р6 = 6! способами; каждому способу посадки 6 мужчин на 6 нечётных местах соответствует Р6 = 6! способов посадки 6 женщин на 6 чётных местах. Поэтому общее число способов рассадить за круглым столом 6 мужчин и 6 женщин таким образом, чтобы мужчины и женщины чередовались, по правилу произведения равно .
Ответ: (6!)2.
5)Сколько существует перестановок из n различных элементов, в которых один данный элемент идет впереди другого данного элемента?
Решение
Определим число перестановок, в которых данный элемент идёт впереди другого данного элемента . Могут быть следующие случаи: стоит на первом месте, стоит на втором месте,….., стоит на (n -1) месте, а стоит правее , число таких случаев равно n – 1. Каждому из этих способов соответствует (n -2)! перестановок других элементов. Следовательно, число перестановок из n элементов, в которых один данный элемент идёт впереди другого данного элемента, равно
( n - 1) (n - 2)! = (n -1)!
Ответ: (n – 1)! перестановок.
6) Сколько можно сделать перестановок из n различных элементов, в которых данные два стоят рядом?
Решение
Определим число перестановок, в которых данные 2 элемента и стоят рядом. Могут быть следующие случаи: стоит на первом месте, стоит на втором месте,….., стоит на (n -1) месте, а стоит правее , число таких случаев равно n – 1.Кроме того и можно поменять местами, и, следовательно, существует 2(n – 1) способов размещения и рядом. Каждому из этих способов соответствует (n -2)! перестановок других элементов. Следовательно, число перестановок из n различных элементов, в которых данные два стоят рядом, равно2(n-1) (n-2)! = 2 (n-1)!
Ответ: 2 (n-1)! перестановок.
7)Сколько можно сделать перестановок из n различных элементов, в которых данные два не стоят рядом?
Решение
По решению предыдущей задачи мы знаем, что число перестановок из n различных элементов, в которых данные два стоят рядом, равно
2(n-1) (n-2)! = 2 (n-1)! Число всех перестановок из n различных элементов равно n!.
Следовательно, число перестановок из n различных элементов, в которых данные два не стоят рядом, равно
n! - 2 (n-1)! = (n -1)! (n – 2).
Ответ: (n -1)! (n – 2) перестановок.
8) Сколькими способами можно поставить в ряд 3 красных, 4 синих и 5 зеленых кубиков?
Решение
По формуле перестановок с повторениями получаем:
Р(3, 4, 5)= . Ответ: 27 720 способов.

9) Сколько существует различных последовательностей длины 5, составленных из трех 1 и двух 0?
Решение
По формуле перестановок с повторениями получаем:
Р( 3,2) = .
Ответ: 10 различных последовательностей.
10) Сколько существует различных пятизначных чисел, составленных из трех 1 и двух 0?
Решение
Ноль не может быть первой цифрой числа, поэтому на первом месте в числе будет стоять одна из трёх 1. Количество комбинаций из оставшихся двух единиц и двух нулей найдём по формуле перестановок с повторениями:
Р(2,2) = .
Ответ: 6 чисел.

11) Имеется шесть различных кошельков. Сколькими способами можно разложить в них двенадцать одинаковых монет, чтобы пустым остался максимум один кошелёк?
Решение:
Так как пустым должен остаться максимум один кошелёк, то либо не должно быть пустых кошельков, либо пустым будет только один из шести. Рассмотрим случай, когда пустых кошельков не должно быть. Это означает, что в каждый кошелёк надо положить не менее одной монеты. Так как по одной монете уже лежит в каждом кошельке, то осталось рассмотреть все способы распределения оставшихся шести монет по шести кошелькам. Поставим в соответствие каждому размещению монет в кошельках последовательность из нулей и единиц следующим образом: сначала последовательность имеет столько нулей, сколько монет поместим в первый кошелёк, затем записываем единицу и далее пишем столько нулей, сколько монет поместим во второй кошелёк, снова единицу, затем столько нулей, сколько монет поместим в третий кошелёк, и т.д. Заканчивается последовательность таким количеством нулей, сколько монет поместим в шестой кошелёк. Значит, последовательность имеет 6 нулей и 6 – 1= 5 единиц.
Переставим всеми возможными способами 6 нулей и 5 единиц. Каждая такая перестановка определяет один из способов распределения монет в кошельках. А именно нули, расположенные до первой единицы положим в первый кошелёк, нули, расположенные между первой и второй единицей, – во второй кошелёк и так далее, нули, расположенные после пятой единицы, - в шестой кошелёк. По формуле перестановок с повторениями число таких перестановок равно
способа распределения 12 монет по шести кошелька так, чтобы не было пустых.
Если же один кошелёк обязательно должен быть пустым, то нужно рассмотреть все способы распределения 12 монет в пять кошельков так, чтобы ни один из этих пяти не был пустым. Используя предыдущие рассуждения, получаем:
способов распределения 12 монет по пяти кошелькам так, чтобы не было пустых.
Пустым может быть любой из шести кошельков, всего 6 вариантов, тогда по правилу произведения, получаем способов распределения 12 одинаковых монет по шести разным кошелькам так, чтобы ровно один был пустым. По правилу суммы, получаем 462+1980 = 2442 способа разложить в шести разных кошельках двенадцать одинаковых монет, чтобы пустым остался максимум один кошелёк.
Ответ: 2442 способа.

12) Сколько разных слов можно составить перестановкой букв в слове « математика»?
Решение:
В слове « математика» имеется две буквы «м», три буквы «а», две буквы «т» и ещё три различных буквы. По формуле перестановок с повторениями получаем: Р(2,3,2,1,1,1)=

=

Ответ: 151200 слов.

Задачи для самостоятельного решения
1) Сколько существует трехзначных чисел, в записи которых цифры 1, 2, 3 встречаются ровно по одному разу?
2) Сколькими способами можно выложить в ряд красный, черный, синий и зеленый шарики?
3) В ряду зрительного зала 15 кресел. Сколькими способами можно разместить на них 15 человек?
4) На полке n различных книг. Скольким способами их можно переставить.
5) Лингвисты разгадывают записи некоторого племени. Известно, что каждый символ обозначает один звук. Всего в алфавите 26 символов. Сколькими способами можно сопоставить звуки знакам письма? Во сколько раз уменьшится количество возможных вариантов, если ученым удалось найти 7 знаков, обозначающих гласные, и 19 согласные?
6) Бусы - это кольцо, на которое нанизаны бусины. Бусы можно поворачивать, но не переворачивать. Сколько различных вариантов бус можно сделать из 13 разноцветных бусин?
7) Предположим теперь, что бусы можно и переворачивать. Сколько тогда различных бус можно сделать из 13 разноцветных бусин?
8) Сколькими способами на доске из n вертикалей и горизонталей можно расположить n ладей так, чтобы они не могли бить друг друга? Ответьте на вопрос задачи, если все ладьи одинаковы и если все они различны.
9) Слово - любая конечная последовательность букв русского алфавита. Выясните, сколько различных слов можно составить из слов а) «ВЕКТОР'»; б) «ЛИНИЯ»; в) «ПАРАБОЛА»; г) «БИССЕКТРИСА»?

Задачи на сочетания
1) Два филателиста хотят обменяться марками. У одного для обмена есть 7 марок, у другого – 5. Сколькими способами они могут поменять две марки одного на две марки другого?
Решение:
Первый филателист должен выбрать 2 марки из 7. Он может это сделать способами. Второй должен выбрать 2 марки из 5. Он может это сделать способами. По правилу произведения получаем,

Ответ: 210 способов совершить обмен
2) На плоскости отмечено 10 точек так, что никакие три из них не лежат на одной прямой. Сколько прямых можно провести через эти точки?
Решение:
Так как никакие три точки не лежат на одной прямой, то любые две точки будут определять одну прямую, на которую другие точки не попадут. Количество прямых будет равно количеству сочетаний из 5 по 2:

Ответ: 45 прямых.
3) На плоскости отмечено 10 точек так, что никакие три из них не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках?
Решение:
Так как никакие три из данных 10 точек не лежат на одной прямой, то любые выбранные три точки можно соединить отрезками и получить треугольник. Выбрать три точки из 10 можно способами.
Ответ:120 треугольников.

4) На прямой отмечено 10 точек, а на параллельной ей прямой – 11 точек. Сколько существует треугольников с вершинами в этих точках?
Решение:
1 случай: для построения треугольников будем выбирать одну точку на прямой, где отмечено 10 точек, а две точки – на параллельной ей прямой, где есть 11 точек. Выбрать 1 точку из 10 можно способами. Выбрать две точки из 11 можно способами. По правилу произведения получаем, треугольников.
2 случай: будем выбирать одну точку на прямой, где отмечено 11 точек, а две точки – на параллельной ей прямой, где есть 10 точек. По правилу произведения получаем,
треугольников.
Итого существует 550 + 495 = 1045 треугольников
5) При встрече 12 человек обменялись рукопожатиями. Сколько сделано рукопожатий?
Решение: Когда два человека обмениваются рукопожатиями, всего будет одно рукопожатие, поэтому количество всех рукопожатий посчитаем по формуле сочетаний рукопожатий.
Ответ: 66 рукопожатий.

Задачи для самостоятельного решения
1) Сколько вариантов экзаменационной комиссии, состоящей из 5 человек, можно создать их 14 преподавателей?
2) Сколькими способами можно выбрать из n человек упорядоченную группу из k человек? Сколькими способами можно выбрать из n человек неупорядоченную группу из k человек?
3) У одного школьника есть 6 книг по математике, а у другого - 8. Сколькими способами они могут обменять три книги одного на три книги другого?
4) Из класса, в котором учатся 30 человек, нужно выбрать двоих школьников для участия в математической олимпиаде. Сколькими способами это можно сделать?
5) Из класса, в котором учатся 30 человек, нужно выбрать двоих школьников: одного для участия в математической олимпиаде, другого для участия в олимпиаде по физике. Сколькими способами это можно сделать, при условии, что олимпиады проходят в одно время?
6) Есть 3 билета в различные театры. Сколькими способами они могут быть распределены среди 25 студентов группы, если каждый студент может получить только один билет?
7) На группу из 25 человек выделены 3 пригласительных билета на вечер. Сколькими способами они могут быть распределены (не более одного билета в руки)?
8) В шахматном кружке занимаются 2 девочки и 7 мальчиков. Для участия в соревновании необходимо составить команду из четырех человек, в которую обязательно должна входить хотя бы одна девочка. Сколькими способами это можно сделать?
Категория: Математика | Добавил: masha
Просмотров: 5938 | Загрузок: 426 | Комментарии: 1 | Рейтинг: 0.0/0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Пятница, 2024-03-29, 11:14 AM
Приветствую Вас Гость

Форма входа

Категории раздела

Психология [194]
Педагогика [338]
Математика [864]
Физика [274]
История [385]
Классному руководителю [571]
Русский язык и литература [770]
Физическая культура [246]
Английский язык [456]
Искусство [204]
Родительский совет [19]
Биология [360]
Информатика [398]
Начальная школа [2040]
Мой Казахстан [258]
Технология [147]
Самопознание [197]
Технология труда [66]
Персональная рубрика учителя технологии труда Шукурова Суюнгали Сагинтаевич. Западно-Казахстанская область,Жанибекский район,СОШ имени Т.Жарокова
НВП и ОБЖ [47]
Профессиональное образование [180]
Дошколенок [574]
География [142]
Школьная библиотека [55]
Казахский язык и литература [642]
Химия [54]

Социальные закладк

Поиск

Друзья сайта

Академия сказочных наук

  • Теги

    презентация Ирина Борисенко открытый урок информатика флипчарт животные новый год 9 класс 5 класс творчество Казахские пословицы проект конспект урока 6 класс физика язык класс педагогика стихи Казахстан математика урок праздник наурыз познание мира музыка доклад программа литература география природа сценарий семья воспитание классному руководителю осень игра казахский язык и литература викторина Начальная школа тест конкурс ИЗО внеклассная работа литературное чтение Русский язык 3 класс технология воспитательная работа сказка Здоровье Оксана 8 марта искусство независимость английский язык психология учитель 3 класс биология статья внеклассное мероприятие классный час ЕНТ выпускной школа 1 класс Русский язык ЕГЭ тесты химия начальные классы Дети экология Дошкольники любовь разработка урока казахский язык самопознание Английский родители br конспект спорт критическое мышление патриотизм дружба дошколенок История обучение тренинг разработка 7 класс физическая культура игры КВН занятие детский сад физкультура Абай коучинг

    Статистика

    Рейтинг@Mail.ru