Задачи на размещения с повторениями

Пример 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 с..