Сколько различных перестановок можно составить из букв слова треугольник

Упр.1068 ГДЗ Алимов 10-11 класс (Алгебра)

©Reshak.ru — сборник решебников для учеников старших классов. Здесь можно найти решебники, ГДЗ, переводы текстов по школьной программе. Практически весь материал, собранный на сайте — авторский с подробными пояснениями профильными специалистами. Вы сможете скачать гдз, решебники, улучшить школьные оценки, повысить знания, получить намного больше свободного времени.

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

Лекции по дискретной математике / Лекция 4.Комбинаторика (прод)

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

Пусть имеется n₁ предметов 1-го типа, n₂ предмета 2-го, n_k пред­метов k-го типа и при этом n₁ + n₂ + … + n_k = n. Количество разных перестановок предметов:

(5)

Для обоснования сначала будем переставлять n предметов в предположении, что они все различны. Число таких перестановок равно n!

Затем заметим, что в любой выбранной перестановке пере­становка n₁ одинаковых предметов не меняет комбинации, аналогично перестановка n₂ одинаковых предметов также не меняет комбинации и т. д. Поэтому получаем выражение (5).

Задача. Сколькими способами можно расставить белые фигуры на первой линии шахматной доски?

Решение. На первой линии могут находиться король, ферзь, 2 ладьи, 2 коня и 2 слона. Без учета общепринятых шахматных правил образуются кортежи длины 8, имеющие указанный состав (1, 1, 2, 2, 2). Тогда число перестановок с размещениями найдем по формуле (5):

Задача. Сколько разных слов можно составить из всех букв слова МАТЕМАТИКА?

Решение. Имеем следующее количество разных букв: М – 2, А – 3, Т – 2, Е – 1, И – 1, К – 1. Всего 10 букв.

Т.о., образуются кортежи длины 10, имеющие указанный состав (2, 3, 2, 1, 1, 1). Число перестановок с размещениями найдем по формуле (5):

Задача. В магазине продается 4 сорта пирожных: бизе, эклеры, песочные, наполеоны. Сколькими способами можно выбрать 7 пирожных?

Решение. Каждая покупка – это выборка из 4 элементов по 7, причем с повторениями, так как 4 < 7. Порядок следования сорта пирожных внутри выборки не важен. Следовательно, число таких покупок равно числу всех сочетаний с повторениями:

Задача. У врача 3 таблетки одного лекарства, 2 таблетки – другого и 4 таблетки – третьего. Сколькими способами он может распределить прием имеющихся таблеток по одной в день?

Решение. Порядок приёма таблеток важен. Есть повторяющиеся таблетки. Общее число таблеток 3 + 2 + 4 = 9 равно числу дней приема лекарств. Решение задачи сводится к нахождению числа всех перестановок с повторениями из 9 элементов:

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

Решение. Общее количество различных слов, полученных перестановкой букв слова огород, равно

Если в каком-то слове все три буквы «о» стоят рядом, то тройную «о» можно считать единым символом, и количество слов, в которых три буквы «о» стоят рядом, равно Р(4) = 4! =24.

В итоге получаем: 120 — 24 = 96.

Задача. Найти разложение (a+b) 6 , используя треугольник Паскаля.

Задача. Написать разложение бинома (x–2y) 5 .

Задача. Найти наибольший член разложения бинома .

Задача. Из данной пропорции найти x и y.

Записав отдельно отношение первого члена пропорции ко второму и второго к третьему, после сокращения получим:

В силу условия задачи мы приходим к системе:

Комбинаторика (практическая работа)

Практическая работа по теме: "Комбинаторика без повторений" для студентов колледжа.

Просмотр содержимого документа
«Комбинаторика (практическая работа)»

Инструкционная карта № 34

Тақырыбы/ Тема: Комбинаторика.

Мақсаты/ Цель:

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

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

Воспитание познавательной самостоятельности: развитие умения самостоятельно классифицировать, выполнять анализ, оценивать результаты.

Теоретический материал:

Множество В называется подмножеством множества А, если каждый элемент В принадлежит А.Запись: В( множество В является подмножеством множества А). Считают также , что пустое множество является подмножеством любого множества () и любое множество является подмножеством самого себя (АА). Каждое упорядоченное подмножество множества А называют размещением. Пусть множество А содержит n элементов. Часто возникает вопрос: сколько размещений по m элементов можно составить из n(mn) элементов множества А? Чтобы ответить на этот вопрос, докажем теорему: число размещений, состоящих из n элементов, взятых из m элементов, равно т.е. =n(n-1)(n-2)…(n-m+1).

Пример1. Число перемещений из 5 элементов по 3 равно

Пример 2. Сколькими способами можно выбрать четырёх человек на различные должности из девяти кандидатов на эти должности?

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

Ответ:3024 способами.

Перестановки.

Часто приходится рассматривать упорядоченные множества , т.е. множества в которых , каждый элемент занимает своё , вполне определенное место. Упорядочить множество-это значить поставить какой –либо элемент множества на первое место, какой либо другой элемент- на второе место и.т.д. Упорядоченные множества принято иногда записывать в круглых скобках .

Упорядочить множество можно различными способами. Например, множество состоящие из трёх элементов a,b и c, можно упорядочить шестью способами(a,b,c,);(a,c,b);(b,a,c);(b,c,a);(c,a,b);(c,b,a).

Каждое упорядоченное множество каких-либо элементов называется перестановкой. Сколько можно составить перестановок из n элементов?

Пример1. Если множество состоит из одного элемента а₁, то его можно, очевидно, упорядочить единственным способом , а именно (а₁). Итак, из одного элемента можно составить одну перестановку.

Пример2. Пусть имеются два элемента :а₁и а_2. Ясно, что из этих элементов можно составить только две перестановки: поставить а₂ перед а₁ или поставить а₂ после а₁:(а₂,а₁); (а₁,а₂). Итак, число перестановок из двух элементов равно 1.

Пример3. Пусть имеются три элемента: а₁,а₂ и а₃.Запишем сначала перестановки из двух элементов а₁и а₂ и в каждую из этих перестановок впишем элемент а₃ вначале на первое место, потом на второе место и , наконец, на третье -последние место. Получи шесть перестановок: (,а₃,а₂,а₁); (а₂,а₃,а₁); (а₂,а₁,а₃);(а₃,а₃,а₂);(а₁,а₃,а₂);(а₁,а₂,а₃). Итак, число перестановок из трех элементов равно

Пример4.Пусть имеются четыре элемента: а₁,а₂,а₃,а₄.Запищем все перестановки из трёх элементов а₁,а₂ и а₃(их число равно)

и в каждую из этих перестановок впишем элемент а₄ в начале на первое место, потом на второе, затем на третье и, наконец, на четвёртое- последние место). Получаем 24 перестановки:

Итак, число перестановок из четырёх элементов равно

Теперь можно сформулировать теорему : число перестановок из n элементов равно произведению n первых натуральных чисел, т.е. P_n=(где P_n-число перестановок из n элементов). Произведение n первых натуральных чисел обозначают n! (читается «эн факториал»), например:

1!=1;2!=12;3!=123;4!=1234.

Пусть имеется множество А=, состоящие из n элементов. Из этого множества можно составить подмножество, состоящие из m элементов (mn). Каждое подмножество состоящие из m элементов, содержащихся в множестве А из n элементов, называется сочетанием из n элементов по m . Число всех таких сочетаний обозначается через Сколько всех сочетаний по m элементов можно образовать из данных n элементов? Для ответа на этот вопрос докажем теорему: число сочетаний из n элементов по m равно .

Пример 1. Вычислить . Применяя формулу сочетаний, имеем =.

Пример 2. На плоскости расположено 5 точек. Сколько отрезков, концами которых являются эти точки, определяются этими точками?

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

13. Перестановки с повторениями

При перестановке букв в слове «толпа» получается P5 = 5! = 120 «слов». Если же переставлять буквы в слове «топот», то получится меньше различных «слов», потому что ни перестановка двух букв «т», ни перестановка двух букв «о» не изменяют «слова»; всего перестановок в данном случае будет . Мы имеем здесь дело с перестановками с повторениями.

Общую задачу сформулируем следующим образом.

Имеется n элементов k различных типов: n1 элементов первого типа, n2 элементов второго типа, …, nk элементов k-го типа, . Сколько можно составить различных перестановок из этих элементов?

Число перестановок c повторениями обозначают . Сколько же их? Если бы все элементы были различны, то число перестановок равнялось бы n!. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. В первой группе элементы (первого типа) можно переставлять друг с другом n1! способами. Но так как все эти элементы одинаковы, то перестановки ничего не меняют. Точно также ничего не меняют n2! перестановок элементов во второй группе и т. д. Перестановки элементов в разных группах можно делать независимо друг от друга. Поэтому (из принципы умножения) элементы можно переставлять друг с другом способами так, что она остаётся неизменной.

Число различных перестановок с повторениями, которые можно составить из данных элементов, равно

, (11.1) где .

Замечание. Отметим, что формула числа сочетаний из n элементов по k элементов совпадает с формулой для числа перестановок с повторениями из k элементов одного типа и n–k элементов другого типа:

.

Пример 11.1. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус?

Решение. Речь идет об отыскании числа перестановок с повторениями, которые можно сделать из k1=4 элементов первого типа (зеленых бус), k2=5 элементов второго типа (синих бус) и k3=6 элементов третьего типа (красных бус). По формуле (6) получаем

.

Пример 11.2. У мамы было 2 одинаковых яблока, 3 одинаковых груши и 4 одинаковых апельсина. Каждый день она давала ребенку по одному фрукту. Сколькими способами она могла это сделать?

Решение. Данная задача есть задача на отыскание числа перестановок с повторениями:

.

Пример 11.3. Сколько различных браслетов можно сделать из пять одинаковых изумрудов, шести одинаковых рубинов и семи одинаковых сапфиров (в браслет входят все 18 камней)?

Решение. Камни можно переставлять P(5, 6, 7) способами. При циклических перестановках и при зеркальном отражении браслет остается неизменным. В результате получаем

.

Пример 11.4. Сколько способами можно переставлять буквы слова «огород» так, чтобы: а) три буквы «о» не стояли рядом? б) если запрещается, чтобы две буквы «о» стояли рядом?

Решение. а) Буквы данного слова можно переставлять P(3,1,1,1) способами. Если три буквы «о» стоят рядом, то их можно считать за одну букву. Тогда буквы можно переставлять 4! Способами. Вычитая этот результат из предыдущего, получим

.

Б) Сначала расставляем согласные (3! способов). Для трёх букв «о» остаётся 4 места, и их можно расставить способами. Всего получаем способа.

11.1. Сколькими способами можно расположить в ряд две зелёные и четыре красные лампочки?

Ответ: .

11.2. Десять человек надо разбить на три группы соответственно по 2, 3, 5 человек в группе. Сколькими способами можно это сделать?

Ответ: .

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

Ответ: .

11.4. Группу командировочных из восьми человек требуется расселить в три комнаты, из которых две трёхместные и одна двухместная. Сколько вариантов расселения возможно?

Ответ: .

11.5. Сколько различных слов можно получить, переставляя буквы в следующих исходных словах: а) академия, б) электротехника, в) молокопродукт?

Ответ: .

11.6. Сколькими способами можно разделить 12 предметов между тремя студентами, чтобы каждому досталось ровно по четыре предмета?

Ответ: .

11.7. Для премий на математической олимпиаде выделено 3 экземпляра одной книги, 4 экземпляра другой и 8 экземпляров третьей. Сколькими способами могут быть распределены эти премии между 30 участниками олимпиады, если каждому вручается не более одной книги?

Ответ: .

11.8. Сколькими способами можно переставить буквы слова «обороноспособность» так, чтобы две буквы «о» не шли подряд?

Ответ: .

11.9. Сколькими способами можно переставить буквы слова «каракули» так, чтобы никакие две гласные не стояли рядом?

Ответ: Гласные можно переставлять P(2,1,1)=12 способами, Аналогично, P(2,1,1)=12 способами можно расставить согласные буквы. Если согласные уже расставлены, то для гласных останется 5 мест. Поэтому места для них можно выбрать способами. Всего способов.