Сайт репетитора по математике Фельдман Инны Владимировны. Профессиональные услуги репетитора по математике в Москве. Подготовка к ГИА и ЕГЭ, помощь отстающим.

Задачи по комбинаторике. Часть 1

В этой статье использован материал из лекций Шарича Владимира Златковича и Максимова Дмитрия Васильевича на КПК foxford.

Очень рекомендую абитуриентам курсы foxford для подготовки к ЕГЭ и олимпиадам.

1. Сколько четырехзначных чисел содержит ровно одну семерку?

Решение.

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

1) на первом месте, и тогда на остальных трех местах могут стоять любые цифры от 0 до 9, кроме цифры 7, и по правилу произведения мы получаем  четырехзначных чисел, у которых семерка стоит на первом месте.

2) на любом месте, кроме первого, и тогда по правилу произведения мы получаем . У нас три возможности расположения цифры 7, на первом месте может стоять 8 цифр (все цифры, кроме нуля и 7), на тех местах, где не стоит цифра 7  - 9 цифр.

Сложим полученные варианты, и получим четырехзначных чисел, содержащих ровно одну семерку.

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

Решение.

Так же как в предыдущей задаче у нас две возможности:

1) Одна из семерок стоит на первом месте, а вторая на любом из оставшихся четырех мест. На трех местах, не занятых цифрой 7 может стоять любая из 9 цифр (все, кроме цифры 7). В этом случае мы получаем  чисел.

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

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

3. Сколько существует пятизначных чисел, цифры которых различны и расположены в порядке возрастания?

Так как первой цифрой не может быть 0, рассмотрим последовательность цифр 1-9, расположенных в порядке возрастания.

1, 2, 3, 4, 5, 6, 7, 8, 9

Если мы выберем из этой последовательности 5 произвольных цифр, например так:

1, 2, 3, 4, 5, 6, 7, 8, 9

то получим пятизначное число, цифры которого различны и расположены в порядке возрастания.

Осталось посчитать, сколькими способами мы можем выбрать из 9 цифр 5:

   

Итак существует 126 пятизначных чисел, цифры которых различны и расположены в порядке возрастания.

Треугольник Паскаля и число сочетаний.

4. Задача о хромом короле. Пусть есть доска размером . Король находится в левом верхнем углу доски и может перемещаться по доске, двигаясь только вправо и вниз. Сколькими способами король может добраться до левого нижнего угла доски?

Решение.

Посчитаем, для каждой клетки, сколькими способами король может до нее добраться.

Так как король может двигаться только вправо и вниз, до любой клетки первого столбца и первой строки он может добраться единственным способом:

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

Заполним начальные клетки, пользуясь этим правилом:

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

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

Например, чтобы попасть в клетку (4;3)  - четвертая строка, третий столбец, король должен сделать 4-1=3 шага вправо, и 3-1=2 шага вниз. То есть всего 3+2=5 шагов. Нам нужно найти число возможных последовательностей этих шагов:

То есть найти, скольким способами мы можем расположить 2 вертикальные (или 3 горизонтальные) стрелки на 5-ти местах. Число способов равно:

   

-  то есть ровно то число, которое стоит в этой клетке.

Для того, чтобы попасть в последнюю клетку, король должен сделать всего шага, из которых по вертикали. Таким образом, он может попасть в последнюю клетку

   

способами.

Можно получить  рекуррентное соотношение для числа сочетаний:

   

Смысл этого соотношения следующий. Путь у нас есть множество, состоящее из n элементов. И нам нужно выбрать из этого множества l элементов.  Все способы, которыми мы можем это сделать делятся на две группы, которые не пересекаются. Мы можем:

а) зафиксировать один элемент, и из оставшихся n-1-го элемента выбрать l-1 элемент. Это можно сделать способами.

б) выбрать из оставшихся n-1-го элемента все l элементов. Это можно сделать способами.

Всего получаем

   

способов.

 

Также можно получить  соотношение:

   

Действительно, левая часть этого равенства показывает число способов выбрать какое-то подмножество из множества, содержащего n элементов. (Подмножество, содержащее 0 элементов, 1 элемент и так далее.) Если мы пронумеруем n элементов, то получим цепочку из n нулей и единиц, в которой 0 означает, что данные элемент не выбран, а 1 - что выбран. Всего таких комбинаций, состоящих из нулей и единиц .

Кроме того, число подмножеств с четным числом элементов равно числу подмножеств с нечетным числом элементов:

   

Докажем это соотношение. Для этого докажем, что между подмножествами с четным числом элементов и подмножествами с нечетным числом элементов существует взаимно однозначное соответствие.

Зафиксируем один элемент множества:

Теперь возьмем произвольное подмножество, и если оно не содержит этот элемент, то поставим ему в соответствие подмножество, состоящее из тех же элементов, что и выбранное, плюс этот элемент. А если выбранное подмножество уже содержит это элемент, то поставим ему в соответствие подмножество, состоящее из тех же элементов, что и выбранное, минус этот элемент. Очевидно, что из этих пар подмножеств одно содержит четное число элементов, а другое - нечетное.

5. Рассмотрим выражение

1. Сколько слагаемых имеет этот многочлен?

а) до приведения подобных членов

б) после приведения подобных членов.

2. Найти коэффициент при произведении

Решение. показать

Рассмотрим частный случай: - Бином Ньютона. И получим формулу для биномиальных коэффициентов.

Произвольный член многочлена, полученного возведением двучлена в степень имеет вид , где А - биномиальный коэффициент, . Как мы уже получили,

   

Таким образом,

   

   

Тогда если мы положим х=1 и y=1, то получим, что

   

 

6. Задача про кузнечика.

Есть n клеточек, расположенных последовательно. Кузнечик должен попасть из крайней левой клеточки в крайнюю правую, прыгая вправо на произвольное число клеток.

а) Сколькими способами он может это сделать?

Решение. показать

б) сколькими способами кузнечик может добраться в n-ю клетку, сделав k шагов?

Решение. показать

в) сколькими способами кузнечик может добраться в n-ю клетку, двигаясь на одну или на две клетки вправо?

Решение.

Распишем, сколькими способами можно попасть в каждую клетку.

В первую и вторую клетки можно попасть единственным способом: в первую - никуда из нее не уходя, и во вторую из первой:

В третью можно попасть из первой или второй, то есть двумя способами:

В четвертую - из второй или третьей, то есть 1+2=3 способами:

В пятую - из третьей или четвертой, то есть 2+3=5 способами: Можно заметить закономерность: чтобы найти число способов, которыми кузнечик может попасть в клетку с номером k нужно сложить число способов, которыми кузнечик может попасть в две предыдущие клетки: 

 

 

Мы получили интересную последовательность чисел - числа  Фибоначчи - это линейная рекуррентная последовательность натуральных чисел, где первое и второе равно единице, а каждое последующее — сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...

 

Для вас другие записи этой рубрики:

Задачи по комбинаторике. Часть 1

Отзывов (2)

  1. Зарецкая М.А.

    В задачах 1 и 2 если уже поставлена 7, а ее количество ограничено, значит, на другие места остается не 10 цифр, а 9 или 8. Расчеты принимают несколько иной вид.

    • Инна

      Конечно, спасибо!

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *