Название работы	Кол-во страниц	Размер
Комбинаторика Числа Логика	1	60.56kb.
Занятие №24 Комбинаторика 14. 03. 09	1	49.15kb.
Лекция Элементы комбинаторики	1	257.31kb.
Семинар по алгебре и линейной оптимизации, посвященный 100-летию...	1	86.55kb.
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика...	1	14.59kb.
Семинар работает по понедельникам с 15: 30 Порядок работы семинара	1	31.76kb.
Семинар «Комбинаторика инвариантов Васильева»	1	73.37kb.
Всякие времена	4	534.46kb.
Направления изучения представлений о справедливости	1	202.17kb.

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

Комбинаторика 2.

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

б) Во сколько из этих команд войдет девочка, а во сколько не войдет?

в) Докажите, что .

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

Определение. Треугольником Паскаля называется числовой треугольник, изображенный на рисунке (по краям треугольника стоят единицы, а каждое из остальных чисел равно сумме двух, стоящих справа и слева над ним)

3. 
   Н
   а рисунке выписаны первые 5 строк треугольника Паскаля. Напишите следующие 5 строк.
   
4. 
   Нарисуем треугольную сетку. Напишем в вершине 1, а в каждом узле   количество путей, которыми можно добраться до него из вершины, двигаясь вниз по линиям сетки. Докажите, что получился треугольник Паскаля
   
5. 
   а) Докажите, что k-е число n-й строки треугольника Паскаля равно (строки нумеруются сверху вниз, начиная с нуля, а числа в строках нумеруются слева направо, также начиная с нуля).
   

б) Найдите с помощью треугольника Паскаля числа , .

6. 
   а) Найдите число способов прочитать слово КВАДРАТ на рисунке справа.
   

б) Найдите сумму чисел в n-й строчке треугольника Паскаля.

в) Докажите, что в любой строчке треугольника Паскаля сумма чисел, стоящих на четных местах, равна сумме чисел, стоящих на нечетных местах.

7. 
   Возьмите любое число в треугольнике Паскаля и сложите все числа, начиная от него и идя по прямой вправо вверх. Что получилось? а) Запишите замеченную закономерность в виде тождества;
   

б) Докажите это тождество комбинаторно (т. е. опираясь на то, откуда берутся числа в треугольнике Паскаля);

в) У нас уже было тождество (Индукция 2, задача 2в)

.

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

8. 
   а) Сложите квадраты всех чисел, стоящих в одной строке треугольника Паскаля, найдите полученное число в треугольнике Паскаля. Запишите полученное тождество.
   

б) Докажите это тождество (Указание: используйте задачу 4.).

Алгебра (искусство раскрывать скобки)

9. 
   Сколько слагаемых будет после раскрытия скобок в выражении
   а) (a+b+c+d+e)(f+g+h);
   б) (1+a)(1+b)...(1+h);
   в) (a+b)¹⁰;
   г) Сколько слагаемых будет после раскрытия скобок и приведения подобных в выражении (a+b)ⁿ?
   
10. 
    а) Раскройте скобки и приведите подобные в выражениях , и выпишите результаты друг под другом. Заметьте, что коэффициенты образуют треугольник Паскаля.
    

б) Раскроем скобки и приведем подобные в выражении . Возьмем любое слагаемое. Оно имеет вид . Докажите, что .

Таким образом мы доказали формулу которую называют Бином Ньютона



Благодаря этой формуле числа часто называют биномиальными коэффициентами.

11. 
    Выведите из бинома Ньютона, что а)
    

б) . Сравните с задачей 6.
Еще задачи.

12. 
    а) Куб размером 10×10×10 разбит плоскостями, параллельными граням, на 1000 кубиков размером 1×1×1. Из любого кубика можно перейти в соседний с ним кубик, если тот находится выше, либо правее, либо дальше (мы поставили куб одной из граней к себе «лицом»). Найдите количество способов пройти из кубика, расположенного в нижнем левом ближнем углу в дальний правый верхний угловой кубик.
    

б) Найдите формулу для .

13. 
    Найдите сумму
    
14. 
    а) Какие тождества на биномиальные коэффициенты следуют из тождеств
    

Указание: Раскройте скобки слева и справа и приравняйте коэффициенты при x^p.

б) (Свертка Вандермонда) Докажите, комбинаторно тождество

.

в) Выведите из пункта а) или пункта б) задачу 8.

15. 
    а) Патриций решил устроить праздник и для этого приготовил 240 бочек вина. Однако к нему пробрался недоброжелатель, который подсыпал яд в одну из бочек. Недоброжелателя тут же поймали, дальнейшая его судьба неизвестна. Про яд известно, что человек, его выпивший, умирает в течение (не «через»!) 24 часов. До праздника осталось два дня, то есть 48 часов. У патриция есть пять рабов, которыми он готов пожертвовать, чтобы узнать в какой именно бочке яд. Как патрицию вычислить отравленную бочку?
    

б) Из скольких бочек можно найти отравленную, если дней k, а рабов n?