Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2009_2010/8mat_0910/spec/050_Combinatorics.doc
Дата изменения: Sun Sep 2 21:08:19 2012
Дата индексирования: Tue Feb 5 07:37:54 2013
Кодировка: koi8-r

Поисковые слова: закон вина

Гимназия 1543, 8-В класс
Листик 5, 29 октября 2009.
Комбинаторика 2.

1. Докажите, что [pic] двумя способами - алгебраически (по формуле) и
комбинаторно (т. е. исходя из определения числа сочетаний поясните,
почему левая часть равна правой)
2. а) Каким числом способов можно выбрать из 10 мальчиков и 1 девочки
команду из 6 человек на матбой?
б) Во сколько из этих команд войдет девочка, а во сколько не войдет?
в) Докажите, что [pic].

Треугольник Паскаля.
Определение. Треугольником Паскаля называется числовой треугольник,
изображенный на рисунке (по краям треугольника стоят единицы, а каждое из
остальных чисел равно сумме двух, стоящих справа и слева над ним)
3. На рисунке выписаны первые 5 строк треугольника Паскаля. Напишите
следующие 5 строк.
4. Нарисуем треугольную сетку. Напишем в вершине 1, а в каждом узле -
количество путей, которыми можно добраться до него из вершины, двигаясь
вниз по линиям сетки. Докажите, что получился треугольник Паскаля
5. а) Докажите, что k-е число n-й строки треугольника Паскаля равно [pic]
(строки нумеруются сверху вниз, начиная с нуля, а числа в строках
нумеруются слева направо, также начиная с нуля).
б) Найдите с помощью треугольника Паскаля числа [pic], [pic].
6. а) Найдите число способов прочитать слово КВАДРАТ на рисунке справа.
б) Найдите сумму чисел в n-й строчке треугольника Паскаля.
в) Докажите, что в любой строчке треугольника Паскаля сумма чисел,
стоящих на четных местах, равна сумме чисел, стоящих на нечетных местах.
7. Возьмите любое число в треугольнике Паскаля и сложите все числа, начиная
от него и идя по прямой вправо вверх. Что получилось? а) Запишите
замеченную закономерность в виде тождества;
б) Докажите это тождество комбинаторно (т. е. опираясь на то, откуда
берутся числа в треугольнике Паскаля);
в) У нас уже было тождество (Индукция 2, задача 2в)
[pic].
Как из него получить тождество о числах [pic]? Где они находятся в
треугольнике Паскаля? Подумайте над обобщением.
8. а) Сложите квадраты всех чисел, стоящих в одной строке треугольника
Паскаля, найдите полученное число в треугольнике Паскаля. Запишите
полученное тождество.
б) Докажите это тождество (Указание: используйте задачу 4.).
Алгебра (искусство раскрывать скобки)
9. Сколько слагаемых будет после раскрытия скобок в выражении

а) (a+b+c+d+e)(f+g+h);

б) (1+a)(1+b)(...((1+h);

в) (a+b)10;

г) Сколько слагаемых будет после раскрытия скобок и приведения подобных в
выражении (a+b)n?
10. а) Раскройте скобки и приведите подобные в выражениях [pic], [pic]
[pic] и выпишите результаты друг под другом. Заметьте, что коэффициенты
образуют треугольник Паскаля.
б) Раскроем скобки и приведем подобные в выражении [pic]. Возьмем любое
слагаемое. Оно имеет вид [pic]. Докажите, что [pic].
Таким образом мы доказали формулу которую называют Бином Ньютона
[pic]
Благодаря этой формуле числа [pic] часто называют биномиальными
коэффициентами.
11. Выведите из бинома Ньютона, что а) [pic]
б) [pic]. Сравните с задачей 6.

Еще задачи.
12. а) Куб размером 10в10в10 разбит плоскостями, параллельными граням, на
1000 кубиков размером 1в1в1. Из любого кубика можно перейти в соседний с
ним кубик, если тот находится выше, либо правее, либо дальше (мы
поставили куб одной из граней к себе «лицом»). Найдите количество
способов пройти из кубика, расположенного в нижнем левом ближнем углу в
дальний правый верхний угловой кубик.
б) Найдите формулу для [pic].
13. Найдите сумму [pic]
14. а) Какие тождества на биномиальные коэффициенты следуют из тождеств
[pic] [pic]
Указание: Раскройте скобки слева и справа и приравняйте коэффициенты при
xp.
б) (Свертка Вандермонда) Докажите, комбинаторно тождество
[pic].
в) Выведите из пункта а) или пункта б) задачу 8.
15. а) Патриций решил устроить праздник и для этого приготовил 240 бочек
вина. Однако к нему пробрался недоброжелатель, который подсыпал яд в одну
из бочек. Недоброжелателя тут же поймали, дальнейшая его судьба
неизвестна. Про яд известно, что человек, его выпивший, умирает в течение
(не «через»!) 24 часов. До праздника осталось два дня, то есть 48 часов.
У патриция есть пять рабов, которыми он готов пожертвовать, чтобы узнать
в какой именно бочке яд. Как патрицию вычислить отравленную бочку?
б) Из скольких бочек можно найти отравленную, если дней k, а рабов n?
-----------------------
[pic]

[pic]

[pic]