- Найдите количество последовательностей из n единиц и n минус единиц, таких что сумма от начала последовательности до любого числа неотрицательна.
- Найдите количество путей из точки (0, 0) в точку (n, n) по линиям клетчатой бумаги, идущих вверх и вправо и не поднимающихся выше прямой y = x.
- Найдите количество способов соединить 2n точек на окружности n непересекающимися хордами.
- С помощью разбиения скобочной последовательности на две докажите рекуррентную формулу для чисел Каталана: Cn+1 = C0Cn + C1Cn-1+C2Cn-2+…+CnC0.
- Посчитайте по этой формуле первые восемь чисел Каталана.
- Какие числа Каталана чётные, а какие нет?
- Выведите из рекуррентной формулы формулу, выражающую следующее число Каталана только через одно предыдущЕЕ.
- Докажите, что Сn+1k+1 = Cnk+1 + Cnk
- Докажите, что из n предметов четное число предметов можно выбрать 2n-1способами
- Найдите количество слов длины 2, 3, 4, …, 10, состоящих только из букв “k” ”m”, причем так, чтобы две буквы “m” не шли подряд.
- Сколько нулей на конце числа 1150 – 1?
- Найдите два или три треугольных числа, которые являются квадратами.
- Дана скобочная последовательность: ( ) ( ) ( ( ) ) ( ( ( ) ) ) ( ). Нарисуйте соответствующее ей дерево.
- Докажите, что любые два соседних числа Фибоначчи взаимно просты.
- Какой коэффициент стоит при x4в разложении (x+1)7?
- Продолжите последовательность Фибоначчи «влево».
- Найдите количество слов длины 2, 3, 4, …, 10, состоящих только из букв "а" и "б" и не содержащих в записи двух букв "б" подряд.
- От открытки размером 21 x 13 сантиметров отрезают квадрат со стороной, равной ширине этой открытки. От получившейся открытки вновь отрезают квадрат и т.д. Проделайте эту операцию до конца и напишите а) размеры всех получившихся квадратов, б) формулу, которая свяжет квадраты чисел Фибоначчи. в) Докажите эту формулу.
- Найдите наибольший общий делитель чисел а) F5 и F6, б) F9 и F10, в) F100 и F101. (Используйте тот факт, что НОД (a,b)=НОД(a-b, b).)
- Требуется сделать набор из 10 гирек, каждая из которых весит целое число граммов, с помощью которых можно взвесить любой целый вес от 1 грамма до 55 граммов включительно даже в том случае, если какая-то одна из гирек потеряется (гирьки кладутся на одну чашку весов, измеряемый вес – на другую).
- а) Леша поднимается по лестнице из 10 ступенек. За один раз он прыгает вверх либо на одну ступеньку, либо на две ступеньки. Сколькими способами Леша может подняться по лестнице?
б) При спуске с той же лестницы Леша перепрыгивает через некоторые ступеньки (может даже через все 10). Сколькими способами он может спуститься по этой лестнице? - На доске были записаны два числа: a1 и a2. Рядом с ними записали третье:
- a3 = a1 + a2, затем четвертое: a4 = a2 + a3, и так далее.
- Найдите значение суммы: a1 + a2 + a3 + a4 + a5 + a6, если a5 = 7.