Вопросы и задачи

  • 1. Какие задачи рассматриваются в разделе дискретной математики, называемом комбинаторикой?
  • 2. Чем вызван интерес к комбинаторике в настоящее время?
  • 3. Перечислите основные классы комбинаций, которые изучаются комбинаторикой.
  • 4. Перечислите общие принципы комбинаторики, позволяющие решать комбинаторные задачи.
  • 5. В чем состоит правило суммы?
  • 6. Объясните суть правила произведения.
  • 7. Решите следующие задачи:
    • а) На вершину горы ведут семь дорог. Сколько способов подъема и спуска с горы?
    • б) Сколько способов подъема и спуска с горы, если они осуществляются различными путями?
    • в) Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?
    • г) Сколькими способами могут разместиться семь человек в очереди?
    • д) В классе изучают десять предметов: в понедельник — шесть разных уроков. Сколькими способами можно составить расписание на понедельник?
    • е) Сколько существует пятизначных чисел, у которых все цифры разные?
    • ж) Сколько существует двузначных чисел, у которых обе цифры четные?
  • 8. Объясните суть метода включений и исключений.
  • 9. Решите следующие задачи:
    • а) В классе тридцать пять учащихся. Из них двадцать посещают математический кружок, одиннадцать — физический и десять учеников не посещают этих кружков. Сколько учеников посещают математический и физический кружки?
    • б) Сколько чисел в первой сотне не делится ни на одно из чисел: 2, 3, 5?
  • 10. Дайте определение перестановки элементов конечного множества.
  • 11. Напишите формулу вычисления числа перестановок элементов множества, состоящего из к элементов.
  • 12. Определите, на сколько больше число перестановок из десяти элементов множества, чем из его семи элементов?
  • 13. Во сколько раз больше число перестановок из семи элементов множества, чем из пяти его элементов?
  • 14. Сколькими способами можно упорядочить множество чисел {1, 2, 3, 4, ..., 2п) так, чтобы каждое число имело четный номер?
  • 15. Сколько можно составить перестановок из п элементов некоторого множества, в которых выбранные два элемента стоят рядом?
  • 16. Составьте все перестановки множества чисел {1,2, 3,4} методом транспозиции числа 1 с соседним элементом.
  • 17. Составьте все перестановки множества чисел {1,2, 3,4} методом вставки числа 4 во всех перестановках чисел {1,2, 3}.
  • 18. Дайте определение перестановки с повторениями.
  • 19. Напишите формулу для вычисления числа перестановок с повторениями для д-элементного множества с г группами повторяющихся перестановок.
  • 20. Сколько различных слов можно составить, переставляя буквы в слове «математика»?
  • 21. Сколько пятибуквенных слов можно составить из букв А, В, С, если А повторяется в слове не более двух раз, В — не более одного раза и С — не более трех раз?
  • 22. Сколько всех подмножеств имеет 2/7-элементное множество А?
  • 23. Что представляет собой число сочетаний /7-элементного множества по т элементов?
  • 24. Напишите формулы для вычисления числа сочетаний из «-элементного множества по т.
  • 25. Докажите равенство С™ = Спп~т.
  • 26. Напишите формулы для вычисления С*±2, С"^, С"“2„.
  • 27. Установите, правильны ли равенства Су +С2 = С%, г5 + г6 - г6 7

'-'10 + '-ло - '-'и •

  • 28. В девятом классе тридцать пять учеников. Сколько возможностей выбрать четырех делегатов на конференцию?
  • 29. Сколько способов разделить группы из пятнадцати учащихся на две группы так, чтобы в первой группе было четыре ученика, а во второй — одиннадцать учеников?
  • 30. Дайте определение сочетаний с повторениями.
  • 31. Напишите формулу для вычисления сочетаний с повторениями.
  • 32. Напишите все сочетания с повторениями из трех элементов а, Ь, с по три. Убедитесь, соответствует ли число сочетаний, вычисленному по формуле.
  • 33. Напишите разложение биномов (а + Ь)5, (1 +х)6.
  • 34. Какие сочетания называются размещениями?
  • 35. В чем основное различие сочетаний и размещений?
  • 36. Напишите все формулы для вычисления числа размещений ИЗ п элементов ПО /77.
  • 37. В каком случае число размещений из п элементов по т равно числу перестановок п элементов?
  • 38. Сколько способов рассадить четырех учеников на 25 местах?
  • 39. Сколько способов упорядочения множества {1,2, ...,4} так, чтобы числа 1, 2, 3 стояли рядом в порядке возрастания?
  • 40. Дайте определение размещения с повторениями.
  • 41. Напишите формулу для вычисления числа размещений из /7 элементов ПО /77 С ПОВТОреНИЯМИ.
  • 42. Сколько существует неудачных попыток открыть камеру хранения, если для кодирования используется 30 букв русского алфавита и десять цифр, а код состоит из 1 буквы и 3 цифр?
  • 43. Каков смысл чисел Стирлинга второго рода?
  • 44. Чему равно число Стирлинга второго рода для множества из 3 элементов и 2 блоков?
  • 45. Каков смысл чисел Белла?
  • 46. Напишите формулу для вычисления чисел Белла по числам Стирлинга второго рода.
  • 47. Что понимают под разбиением целого числа п?
  • 48. Напишите все разбиения числа 4.
  • 49. Вычислите, сколько существует способов распределения 20 предметов по 5 ящикам, если в первом ящике должно быть 4 предмета, а в остальных ящиках на 1 предмет больше, чем в первом ящике?
  • 50. Напишите формулу для размещения я, = 10, п2 - 12, пъ =8 предметов в двух ящиках так, чтобы в первом из них было не меньше 3 предметов, во втором — не меньше 6 предметов и в третьем ящике — не меньше 4 предметов.
  • 51. Вычислите число распределения 10 предметов на 5 групп.
  • 52. Вычислите число распределения 12 предметов на 5 групп так, чтобы в каждой группе было не менее 2 предметов.
  • 53. Вычислите число распределения 15 предметов на 5 групп с учетом порядка расположения предметов в группах.
  • 54. Дайте определение рекуррентного соотношения.
  • 55. Приведите примеры рекуррентных соотношений.
  • 56. Вычислите число перестановок я-элементного множества, если оно известно для (п - 1)-элементного множества.
  • 57. Напишите, чему равен (п + 2)-й член последовательности чисел Фибоначчи.
 
< Пред   СОДЕРЖАНИЕ     След >