Задачи на размещения с повторениями
Пример 1. Множество Р={2,4,5}. Перечислите все размещения этого множества по 2 с повторениями.
Решение: <2,2>,<2,4>,<4,2>,<2,5>,<5,2>,<4,4>,<4,5>,<5,4>,<5,5>.
Мы можем проверить себя, вычислив число данных размещений, воспользовавшись формулой (3):
.
Число размещений, которое мы получили, равно 9.
Ответ. <2,2>,<2,4>,<4,2>,<2,5>,<5,2>,<4,4>,<4,5>,<5,4>,<5,5>.
Пример 2. Сколько пятизначных чисел мы можем получить из цифр 2,4,9?
Решение: Нам нужно получить пятизначные числа, тогда как даны 3 цифры, значит, мы будем вычислять число размещений с повторениями:
.
Ответ. 243 числа.
Пример 3. Сколько трехзначных чисел, кратных 5, можно составить из цифр 0,1,4,5,8 (цифры могут повторяться)? А кратных 2?
Решение: У нас есть 5 цифр и нужно составить трехзначные числа с повторяющимися цифрами, т.е. мы будем находить число размещений с повторениями, и чтобы число было кратно 5, его последней цифрой должен быть 0 или 5. Значит, мы воспользуемся правилом произведения: . Однако нам надо исключить числа, У которых на первом месте стоит 0. Тогда искомое число будет равно:
.
Мы могли посчитать это другим способом. Нам необходимо получить трехзначное число, кратное 5, т.е. на первое место мы можем поставить 1 из 4 цифр (все, кроме 0), на второе – 1 из 5 цифр и на третье – 1 из 2 цифр (0 или 5), т.е.:
.
Вычислим количество чисел, кратных 2. На первом месте у нас может стоять любая цифра, кроме 0, т.е. , на втором – любая из пяти цифр, т.е.
, и на третьем месте может стоять 0,4 и 8, т.е.
. Тогда искомое число мы можем вычислить следующим образом:
.
Ответ. 40 чисел, кратных 5; 60 чисел, кратных 2.
Пример 4. Сколько двузначных чисел можно составить из четных цифр, исключая 0.
Решение: {2,4,6,8}, n=4.
.
Ответ. 16 чисел.
Пример 5. В автобусе по маршруту №210 сидит 6 пассажиров. До конечной осталось 10 остановок. Сколькими способами пассажиры могут выходить из автобуса на каждой остановке, начиная с 10 с конца?
Решение: 6 пассажиров, т.е. n=6; осталось 10 остановок и конечная, т.е. в сумме 11, т.е. k=11. Распределим 6 пассажиров по 11 остановкам. Пассажиры могут выходить как по одному, так и все вместе, т.е. будем искать число размещений с повторениями:
.
Ответ. 177156 способами.
Пример 6. Сколькими способами можно разместить 4 кресла по трем комнатам дома, если каждая из комнат может вместить все 4?
.
Ответ. 81 способом.
Выводы к главе 2
Таким образом, существует много типов задач, сводящихся к нахождению числа размещений с повторениями и без повторений. В том числе могут встречаться задачи, где комбинируются числа размещений, сочетаний и перестановки. Необходимый уровень владения теоретическим материалом и практическими навыками в области решения комбинаторных задач существенно упрощает процесс поиска решений, так как зачастую существует очень много способов и подходов к решению одного и того же задания. Умение видеть простейший из них позволяет быстрее и эффективнее найти требуемое решение. Из чего можно сделать вывод, что должным образом изученная и рассмотренная теоретическая часть должна быть подкреплена соответствующими практическими навыками, что позволит быстрее и проще продвигаться в изучении и исследовании различных областей знаний, в том числе и математичеких.
ЗАКЛЮЧЕНИЕ
В ходе исследования темы «Размещения» были изучены и проанализированы найденные исторические сведения и теоретический материал, благодаря чему было выявлено, что комбинаторика формируется и развивается в течение уже очень долгого времени. Ее история насчитывает много веков. Хотя в качестве раздела науки она начала развиваться сравнительно недавно. Значительный вклад в ее развитие внесли известные ученые-математики, такие как Паскаль, Лейбниц, Бернулли, Эйлер и многие другие задолго до них, к примеру, в Древней Греции и Индии.
В ходе исследования теоретического материала и практических задач темы «Размещения» было выявлено, что комбинаторика имеет связи с различными областями математики, такими как алгебра, геометрия, теория вероятностей, а так же имеет широкий спектр применения в разных областях знаний (генетике, информатике, статистической физике).
Различные задачи на размещения в комбинаторике опираются как на абсолютно абстрактные ситуации, так и на вполне способные на существованию, что говорит о практической пользе науки.
К тому же, как уже говорилось ранее, комбинаторика достаточно популяризованная наука на данный момент. Так, к примеру, в книге Н. Я. Виленкина «Популярная комбинаторика» (1975 г.) [6] научно-популярным, доступным и понятным языком рассказывается история возникновения комбинаторики, ее основы, а также в книге представлены комбинаторные задачи. В целом ее можно считать очень понятным учебником по комбинаторике с подробной и интересной исторической справкой. На примере этой книги можно показать, что популяризация комбинаторики проходит достаточно успешно. Кроме того это наука действительно интересна не только для ученых, но и для людей не вовлеченных в науку тоже.
Таким образом, в ходе проведенного исследования и реализации всех поставленных мной целей этой работы было выявлено, что комбинаторика тесно связана со многими разделами математики, широко применяется в различных сферах знаний. А также она может применяться и для решения привычных нам задач, связанных с окружающим нас бытом.
Список литературы
1. http://hijos.ru/izuchenie-matematiki/algebra-10-klass/18-kombinatorika-razmeshheniya-perestanovki-sochetaniya/
2. Айгнер М. Комбинаторная теория. М.: Мир, 1982.
3. Андерсон, Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8.
4. Белешко Дмитрий Дискретная математика: алгоритмы.– СПб: Изд-во СПбНИУ ИТМО, 2004.
5. Бородин А.И., Бугай А.С. Биографический словарь деятелей в области математики. Киев: Ряданська школа, 1979.
6. Виленкин Н. Я. Популярная комбинаторика . — М.: Наука, 1975.
7. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.
8. Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.
9. Ерусалимский Я. М. Дискретная математика: теория, задачи, приложения. 10-е изд., перераб. и доп.– М.: Вузовская книга, 2009, 288 с.
10. История математики с дрвнейших времён до начала XIX столетия / Под ред. А.Н. Колмогорова, А.П. Юшкевича. М: Наука, 1970-1972. T.1-3.
11. Клейн Ф. Лекции о развитии математики в XIX столетии. М.: Наука, 1989.
12. Липский В. Комбинаторика для программиста. — М.: Мир, 1988. — 213 с.
13. Райгородский А. М. Линейно-алгебраические и вероятностные методы в комбинаторике . — Летняя школа «Современная математика». — Дубна, 2006.
14. Раизер Г. Дж. Комбинаторная математика. — пер. с англ. — М., 1966.
15. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.
16. Риордан Дж. Введение в комбинаторный анализ. — пер. с англ. — М., 1963.
17. Романовский И.В. Дискретный анализ. — 3-е изд. — СПб: Невский Диалект; БХВ Петербург, 2003.
18. Рыбников К.А. Введение в комбинаторный анализ.– М.: Изд-во МГУ, 1985
19. Рыбников К.А. История математики. М.: МГУ, 1994.
20. Сачк пов В.Н Введение в Комбинаторные методы дискретной математики.– М.: Наука, 1982
21. Стенли Р. Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2.
22. Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции = Enumerative Combinatorics. Volume 2. — М.: «Мир», 2009. — С. 767. — ISBN 978-5-03-003476-8.
23. Степанов В. Элементы комбинаторики.– СПб., 2004.
24. Холл М. Комбинаторика.– М.: Мир, 1970
25. Яблонский С.В. Введениев дискретную математику: Учеб. Пособие для вузов.- 2-е изд., перераб. И доп.- М.: Наука, 1986. Гл. ред. Физ.-мат. аЛит.- 384 с..