Решение комбинаторных задач

Решить задачи, указанные преподавателем.

На вершину горы ведет 7 дорог. Сколькими способами турист может подняться на гору и спуститься с нее? (Ответ: 49).

На вершину горы ведет n дорог. Сколькими способами турист может подняться на гору и спуститься с нее, если подъем и спуск должен осуществляться различными дорогами? (Ответ: n (n -1)).

Сколькими способами можно разложить n различных шаров по m различным урнам. (Ответ: mⁿ).

Сколько трехзначных чисел можно составить из цифр 1,2,3,4,5? (Ответ: 125).

Сколько трехзначных чисел можно составить из цифр 1,2,3,4,5, если каждую из этих цифр можно использовать не более одного раза? (Ответ: 60).

Найти количество чисел от 0 до 999999, в записи которых встречается «1», и в записи которых ее нет. (Ответ: 468559, 531441).

Сколько существует чисел от 0 до 999999, в которые не входят две идущие друг за другом одинаковые цифры? (Ответ: 597871).

Сколько имеется пятизначных чисел, которые делятся на 5? (Ответ: 18000).

Сколько имеется двузначных чисел, у которых обе цифры четные? (Ответ: 20).

Сколько имеется пятизначных чисел, у которых все цифры нечетные? (Ответ: 3125).

Какое наибольшее количество номеров нужно перебрать, чтобы открыть автоматическую камеру хранения с пятизначным номером? (Ответ: 100000).

Человек забыл пятизначный номер автоматической камеры хранения. Он только помнит, что в номере были числа 17 и 78. Какое наибольшее количество номеров нужно перебрать, чтобы открыть камеру? (Ответ: 60).

Сколько диагоналей имеет выпуклый n -угольник? (Ответ: n (n -3)/2).

Каково число матриц из n строк и m столбцов с элементами из множества {0,1}. (Ответ: 2 ^mn).

В комнате 6 лампочек, каждая имеет свой выключатель, сколькими способами можно осветить комнату? (Ответ: 63).

Сколькими способами можно усадить 7 гостей на 7 стульях? (Ответ:5040).

Сколькими способами можно разместить в аудитории 10 человек, если есть 10 мест? (Ответ:3628800).

Сколько можно составить перестановок из n элементов, в которых данные m элементов не стоят рядом в любом порядке? (Ответ: n!- m!(n - m +1)!).

Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы никакие два лица одного пола не сидели рядом? (Ответ: 2(n!)²).

Сколькими способами можно выбрать 2 детали из ящика, содержащего 10 деталей? (Ответ: 45).

На плоскости поставили 5 точек. Каждые две точки соединили отрезком. Сколько всего отрезков получилось? (Ответ: 10).

На плоскости поставили n точек. Каждые две точки соединили направленным отрезком. Сколько направленных отрезков получилось? (Ответ: n!/(n-2)!).

В группе из 30 студентов каждый пожал руку всем остальным. Сколько было рукопожатий? (Ответ: 435).

Каково число матриц из n строк и m столбцов с элементами из множества {0,1} при условии, что строки каждой матрицы должны быть попарно различны. (Ответ: ).

Сколькими способами можно избрать президиум для ведения собрания в группе из 25 человек, если в президиум входят: председатель, секретарь и член президиума? (Ответ:13800).

Сколько можно составить сигналов из 6 флажков различного цвета, взятых по два? (Ответ: 30).

В классе изучают 10 предметов. В понедельник 6 уроков, причем все уроки различные. Сколькими способами можно составить расписание на понедельник? (Ответ: 151200).

У англичан принято давать детям несколько имен. Два способа, различающиеся лишь порядком имен, считаются различными. Пусть ребенку дают не более трех имен, а общее число имен равно 300. Сколькими способами можно назвать ребенка, если все данные ему имена различны, и если имена могут повторяться? (Ответ: 26820600, 27090300).

Сколько различных слов можно составить, переставляя буквы слова «мама»? (Ответ: 6).

Сколько различных слов можно составить, переставляя буквы слова «комбинаторика»? (Ответ: 389188800).

Для премирования трех студентов купили 12 различных книг. Сколько возможных способов распределения книг по 4 каждому студенту? (Ответ: 34650).

Сколькими способами множество из n элементов может быть разбито на m подмножеств, из которых первое содержит k ₁ элементов, второе k ₂ и т.д. (Ответ: n!/(k ₁! k ₂!... k_m!)).

Сколькими способами можно разложить n = k ₁+ k ₂+...+ k_m различных шаров по m различным урнам так, чтобы в первую урну попало k ₁ шаров, во вторую – k ₂ и т.д., в m -ю – k_m шаров? (Ответ: n!/(k ₁! k ₂!... k_m!)).

Найти число способов размещения n различных шаров по m различным урнам так, чтобы m ₁ урн содержали по p ₁ шаров, m ₂ – по p ₂ и т.д., m_k урн по p_k шаров (m = m ₁+ m ₂+...+ m_k, n = m ₁ p ₁+ m ₂ p ₂+...+ m_kp_k). (Ответ: ).

Найти число способов размещения n различных шаров по m урнам так, чтобы m ₁ урн содержали по p ₁ шаров, m ₂ – по p ₂ и т.д., m_k урн по p_k шаров (m = m ₁+ m ₂+...+ m_k, n = m ₁ p ₁+ m ₂ p ₂+...+ m_kp_k), если урны, содержащие одинаковое число шаров неразличимы. (Ответ: ).

Дано m предметов одного сорта и n предметов другого. Найти число выборок, составленных из r предметов одного сорта и s – другого. (Ответ: ).

В группе из 22 студентов 6 девушек и 16 юношей. Сколькими способами можно выбрать 5 человек так, чтобы среди них были 2 девушки и 3 юноши? (Ответ: 8400).

Сколькими способами можно составить три пары из n шахматистов? (Ответ: ).

Коалиции A и B ведут войну между собой; n нейтральных государств находятся в нерешительности, причем p из них не присоединяются к A, а k не присоединяются к B. Сколько новых положений может оказаться в этой войне в зависимости от дальнейшего поведения нейтральных государств. (Ответ: 2 ^k 2 ^p 3 ^{n - k - p} -1).

Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу, т.е. на них должны быть одинаковые числа? (Ответ: 147).

Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не атаковали друг друга, т.е. чтобы никакие две ладьи не стояли на одной вертикали или горизонтали? (Ответ: 40320).

Пронумеруем слева направо первый горизонтальный ряд клеток шахматной доски числами от 1 до 8, второй – от 9 до 16 и т.д. Докажите, что сумма номеров клеток, на которых стоят 8 ладей, не атакующих друг друга всегда равна 260.

Пусть L =(m, n) – точка с натуральными координатами на целочисленной решетке. Найти число «монотонных» траекторий, ведущих из начала координат в точку L. Под монотонной понимается траектория, на каждом шаге которой можно идти либо вправо, либо вверх. (Ответ: ).

Пусть в предыдущей задаче m = n × k (k – целое). Во сколько раз «монотонных» траекторий, у которых первое звено лежит на оси 0X больше чем траекторий, у которых первое звено лежит на оси 0Y? (Ответ: в k раз).

Сколькими способами можно число n представить в виде суммы k слагаемых (представления, отличающиеся лишь порядком слагаемых, считаются различными), если каждое слагаемое является целым неотрицательным числом? (Ответ: ).

Сколькими способами можно число n представить в виде суммы k слагаемых (представления, отличающиеся лишь порядком слагаемых, считаются различными), если каждое слагаемое является натуральным числом? (Ответ: ).

Сколькими способами можно расставить n нулей и k единиц так, чтобы никакие две единицы не стояли рядом? (Ответ: ).

Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется: а) хотя бы один туз; б) ровно один туз; в) не менее двух тузов; г) ровно два туза? (Ответ: а) б) в) г) ).

Рассмотрим 8 классов графов с отмеченными вершинами. Каждый из этих классов определяется параметрами a,b,gÎ{0,1}. Элементы класса (a,b,g) будем называть (a,b,g)-графами. При этом, если a=0, то рассматриваются графы без петель, если a=1, то петли допускаются. Ели b=0, то рассматриваются графы без параллельных ребер, если b=1, то параллельные ребра допускаются. Если g=0, то рассматриваются неориентированные графы, если g=1, то рассматриваются ориентированные графы. Обозначим g _a,b,g(n, k) число (a,b,g)-графов с n вершинами и k ребрами.

Докажите, что

Исходя из комбинаторных соображений, доказать, что следующие числа целые: , .