Дискретная математика для будущего учителя математики (стр. 1 )

Государственное образовательное учреждение высшего профессионального образования

«Красноярский государственный педагогический университет им. »

Дискретная математика для будущего учителя математики

Учебное пособие

Красноярск

2008

Аннотация

Пособие составлено в соответствии с требованиями к содержанию дисциплины «Дискретная математика» Государственного образовательного стандарта высшего профессионального образования по специальности 050201 «Математика» с дополнительной специальностью «Информатика».

С позиций профессиональной направленности в пособии представлен дополнительный материал по двум основным разделам лекционного курса «Дискретная математика» для будущего учителя математики: комбинаторика и теория графов. К каждому разделу прилагается комплекс заданий для самостоятельной работы студентов.

Пособие предназначено для студентов, преподавателей педагогических вузов.

Введение

Нет ни одной области математики, как бы абстрактна она ни была, которая когда-нибудь не окажется применимой к явлениям действительного существующего мира (), знаменитый русский математик, первооткрыватель неевклидовой геометрии

Реальный мир, в сущности, противоречив: он представляет собой единство противоположных сторон – прерывного и непрерывного, конечного и бесконечного.

В философии под прерывностью и непрерывностью понимают категории, характеризующие строение материи и процесс ее развития. Прерывность (дискретность от лат. discretus – разделенный, прерывистый) – пространственно-временная отграниченность, изолированность, раздельность, скачкообразность, локальность, предельная делимость, периодичность элементов, состояний объекта. Непрерывность (континуум от лат. сontinuum - непрерывный) – взаимосвязь, взаимообусловленность, слитность, постепенность, нелокальность, беспредельная делимость, апериодичность элементов и состояний объекта [2].

Диалектика непрерывного и прерывного пронизывает всю историю познания. В понимании строения вещества, начиная с античности, соперничали атомизм Демокрита и континуализм Аристотеля.

Подобные концепции обычно являются дополнительными, их синтез ведет к более глубокому пониманию реальности.

Известный советский философ писал: «Непрерывное превращение форм движения представляет собой бесконечный ряд количеств и качеств и создание других… каждый такой переход – это скачок, перерыв определенной конкретной непрерывности. При этом прерывность выступает как момент разрешения внутренних противоречий определенного качества, которые обуславливают это качество и готовят его переход в другое… Прерывность материальных состояний вносит в непрерывность пространства дискретность» [15].

Критикуя попытки противопоставления непрерывного дискретному и попытки сведения их друг к другу, Гегель () – немецкий философ, создавший теорию диалектики, утверждал: «Взятые со стороны одной только дискретности, субстанция, материя, пространство, время и т. д. безусловно разделены; их принципом служит «одно». Взятое же со стороны непрерывности, это «одно» есть лишь нечто снятое; деление остается делимостью, остается возможность делить как возможность, никогда в действительности не приводящая к этому… Так как каждая из двух противоположных сторон содержит в самой себе другую и ни одну из них нельзя мыслить без другой, то следует, что ни одно из этих определений, отдельно взятое, не истинно, а истинно лишь их единство» [12].

Математика, изучающая количественный аспект материальной действительности, отражает противоречивость реального мира. Непрерывность и однородность пространства – это предпосылки возникновения континуальных разделов математики, а разрывность и неоднородность – дискретных разделов. В то же время единство мира, тесная связь его непрерывных и дискретных свойств являются основанием единства математики.

Деление математики на непрерывную и дискретную во многом условно. «Диалектика рассматриваемых противоположностей вносит важный вклад в общую гармонию математического познания, которое заключается не в симметрическом синтезе противоположностей, а в разрешении противоречий между бедным, отвлеченно-абстрактным, формализованным и жизненным, богатым, содержательным» [27].

В настоящее время практически любая математическая дисциплина изучает как непрерывные, так и дискретные математические модели. В алгебре наряду с конечными группами рассматриваются непрерывные и топологические. Теория чисел изучает целые числа и различные приближения иррациональных чисел. Теория управления рассматривает управление непрерывными и дискретными процессами. С помощью дискретных сигналов, передаваемых компьютером, воспроизводятся непрерывные объекты. Даже в математическом анализе наряду с непрерывными преобразованиями изучаются дискретные. Связь дискретного и непрерывного хорошо видна на примере разложения функций в ряд Тейлора. Здесь непрерывная функция задается с помощью дискретного набора коэффициентов.

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

Дискретная математика – область математики, занимающаяся изучением свойств различных структур, имеющих дискретный (конечный, финитный) характер. Они могут возникать как в самой математике, так и в ее приложениях. К их числу принято относить объекты, имеющие прерывный (дискретный) характер в отличие от объектов, изучаемых непрерывной математикой и носящих непрерывный характер.

Использование непрерывной математики или дискретной математики как аппаратов исследования связано с тем, какие задачи ставит перед собой исследователь, и в связи с этим, какую модель изучаемого явления он рассматривает: дискретную или непрерывную.

Характер объектов, исследуемых дискретной математикой, настолько своеобразен, что методов классической математики не всегда достаточно для их изучения. Поэтому те специфические методы, которые применяются для очень широкого класса конечных (финитных) дискретных объектов, и были объединены в общее направление – дискретную математику.

Необходимость изучения этой дисциплины студентами педагогических вузов обусловлена тем, что в наше время мы стали свидетелями бурного развития дискретной математики, которая является сегодня не только фундаментом кибернетики, но и важным звеном математического образования. Современный учитель математики и информатики должен овладеть не только ее основными понятиями и методами, но и методикой ее преподавания в школе.

Основной целью курса «Дискретная математика» является формирование у будущих учителей математики основ профессионально-педагогической компетентности в области исследования конечных математических структур.

С позиций профессиональной направленности в пособии представлен дополнительный материал по двум основным разделам лекционного курса «Дискретная математика»: элементы комбинаторики и теории конечных графов в школьном курсе математики.

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

Когнитивный блок содержания включает в себя предметные знания и методические рекомендации по интеграции основ дискретной математики в сложившуюся систему школьного математического образования.

Деятельностный блок содержания представлен комплексом проектно-ориентированных, творческих заданий, которые представляют собой модель учебной ситуации. «Погружаясь» в неё, будущий учитель учится владеть определенной системой знаний, применять знания на практике, в своей преобразующей деятельности. Проектные задания являются альтернативными заданиями, которые выполняются проектной группой студентов по их выбору, предпочтениям и способностям, и, делятся на три разновидности: предметные, общепрофессиональные и профессионально-педагогические проекты.

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

Общепрофессиональные задания направлены на формирование и развитие у будущих учителей математики основ ключевых компетентностей.

Профессионально-педагогические задания ориентированы на формирование у будущих учителей математики основ профессионально-педагогической компетентности, опыта профессиональной деятельности – это задания методического, творческого характера, обеспечивающие проекцию ценностей знаний и отношений к ним в деятельность и поведение студентов.

Ценностный блок содержания состоит из комплекса задач, ориентирующих будущего учителя на осознание ценностных аспектов изучаемого материала. Это задачи на анализ, сравнение и оценку ценностных объектов, которые подразумевают осуществление студентом оценочной деятельности, ставят его в ситуацию выбора ценностей, на проявление рефлексии, критического мышления.

Новизна данного пособия определяется методическим планом подбора материала и организацией его изложения. В процессе подготовки данного пособия был использован материал ряда отечественных и зарубежных авторов (см. список литературы). При этом наиболее близко целям и задачам настоящего курса соответствуют пособия [1], [19], [21], [39], [50], [51], [52], [53], [68].

Раздел 1

Комбинаторика в школьном курсе математики

Тот побеждает, кто знаком С искусством мыслить тонким Уильям Вордсворт, английский поэт

О необходимости изучения в школе элементов комбинаторики говорили многие педагоги еще очень давно. Приведем цитату более чем столетней давности: «Приходилось слышать, что теория сочетаний и бином Ньютона предлагаются иногда как отделы, которые можно было бы сократить. Соглашаясь на другие сокращения, выскажусь решительно против сокращения теории сочетаний. Теория эта по особенному значению своему принадлежит к таким отделам, преподавание которых в гимназии следует непременно сохранить и поставить в лучшие условия. Теория сочетаний представляет средство для одной из важнейших способностей ума – способности представлять явления в разных комбинациях. Эта способность нужна в жизни всякому…» - писал профессор Московского учебного округа в 1899 г.

С учебного года началось повсеместное преподавание в основной школе элементов комбинаторики, статистики и теории вероятностей. Изучение данного курса осуществляется в соответствии с письмом Министерства образования российской Федерации от 01.01.2001 г. «О введении элементов комбинаторики, статистики и теории вероятностей в содержание математического образования основной школы».

Основная цель изучения комбинаторики в школьном курсе математики – это формирование так называемого комбинаторного мышления у учащихся, позволяющее ему разумно организовать перебор ограниченного числа данных, подсчитать все возможные комбинации элементов, составленных по определенному правилу.

Без минимальной вероятностно-статистической грамотности трудно адекватно воспринимать социальную, политическую, экономическую информацию и принимать на ее основе обоснованные решения. Практически вся математика основана на комбинаторно-логических задачах. Кроме того, в современном образовании физика, химия, биология, весь комплекс социально-экономических наук реализуются на вероятностно-статистической базе. При изучении комбинаторики обогащаются представления учащихся о современной картине мира и методах его исследования.

В результате изучения комбинаторики учащиеся должны:

·  знать основные комбинаторные объекты и числа;

·  уметь решать комбинаторные задачи;

·  уметь использовать приобретенные знания и умения в практической деятельности.

Введение в практику обучения этого нового материала должно сопровождаться накоплением и изучением методического опыта. В настоящее время в учебной и учебно-методической литературе существуют различные подходы к реализации нового содержания программы по математике. Вышли несколько учебников, в которых комбинаторика представлена по-разному. В одних учебниках этот раздел включен в основное содержание отдельными параграфами. В других же – в форме вкладышей дополнительных глав к своим учебникам. Отрадно отметить серию книг по математике автора , в которых элементы дискретной математики уже начинают появляться для учеников 2, 3 классов начальной школы.

§ 1. Основные комбинаторные объекты и числа

Комбинаторика занимается изучением объектов, получаемых выборкой из конечного множества М={a1,a2,...an} некоторых элементов. Комбинаторными объектами, например, могут быть подмножества множества М, подмножества с повторяющимися элементами из М, упорядоченные подмножества множества М и тому подобные. Наряду с классами комбинаторных объектов рассматриваются и комбинаторные числа, характеризующие число объектов в данном классе и зависящие от некоторых параметров.

Вычисление или хотя бы относительно точная оценка комбинаторных чисел связаны с эффективностью работы компьютерных программ и тех алгоритмов, на которых они основаны. Зачастую вследствие обилия возможностей, возникающих на каждом очередном шаге работы программы, проявляется эффект «комбинаторного взрыва». Как правило, в этом случае компьютер не может справиться с лавинообразно поступающей новой информацией и «виснет». Например, потерпели полный провал попытки создать программу, играющую в шахматы, на основе перебора всех возможных ходов. Действующие в настоящее время шахматные программы основаны на существенно других принципах.

При вычислении комбинаторных чисел и решении задач широко применяются два нижеследующих правила, связанных с выборками элементов.

Правило суммы. Если объект А может быть выбран m способами, а объект В – другими n способами, то выбор «А или В» осуществляется (m+n) способами.

Правило произведения. Если объект А может быть выбран m способами, и после каждого из таких выборов объект В в свою очередь может быть выбран n способами, то выбор «А и В» в указанном порядке осуществляется (m×n) способами.

Задача 1.1. В меню столовой имеется 4 первых, 5 вторых и 6 третьих блюд. Сколькими способами можно выбрать обед из одного первого, одного второго и одного третьего блюда?

Решение: Представим, что у вас есть разнос с углублениями для первого блюда, второго и третьего. Число способов заполнить углубление для первого блюда равно 4, для второго блюда – 5, а для третьего – 6. Общее число способов равно произведению 4·5·6=120.

Число подмножеств

Применяя правило произведения, легко подсчитать сколько различных подмножеств имеется у n-элементного множества М. В самом деле, если выбрать произвольное подмножество К множества М, то для каждого элемента ai (i=1,2,...n) из М существуют две возможности: либо ai принажлежит К либо нет. То же самое верно для любого элемента из М. Так как в М всего n элементов, то по правилу произведения получается, что различных подмножеств у n-элементного множества будет 2n.

Например, если М={a1, a2, a3}, то различных подмножеств будет 23=8, имеем: {a1}, {a2}, {a3}, {a1, a2}, {a2, a3}, {a1, a3}, {a1, a2, a3}, {}.

Размещения k элементов из М

Размещением k элементов из n-элементного множества М называется упорядоченное подмножество множества М, содержащее k элементов этого множества.

Например, если k=2 и М={a1,a2,a3},то все размещения по 2 элемента будут такими: (a1,a2),(a3,a1),(a2,a1),(a3,a2),(a1,a3),(a2,a3).

Число размещений из М по k обозначается .

Для подсчёта этого числа нужно выбрать k элементов из М и расставить их по k местам. Очевидно, что на первом месте может находиться любой из n элементов множества М, на втором – любой из (n–1) оставшихся и так далее. По правилу произведения: , где k≤n, n, kÎN (1).

При k>n , при k=0 .

Задача 1.2. Сколько существует различных пятизначных чисел, не содержащих одинаковых цифр?

Решение: Всего цифр 10: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. В пятизначном числе пять позиций: первая позиция – разряд десятков тысяч, четвертая – тысяч, третья – сотен, вторая – разряд десятков и третья – разряд единиц. Число размещений из 10 цифр по 5 местам равно . Однако если число начинается с 0, то оно не пятизначное. Таких чисел будет . Отсюда, искомое число равно .

Перестановки множества М

Перестановкой множества М={a1,a2,...an} называется упорядоченное подмножество из n элементов, принадлежащих М.

Например, если М={a1,a2,a3}, то все перестановки элементов из М имеют вид: (a1,a2,a3), (a3,a1,a2), (a2,a1,a3), (a3,a2,a1), (a1,a3,a2), (a2,a3,a1).

Число перестановок множества М обозначается Pn.

Ясно, что перестановки – частный случай размещений, который получается при k=n. Pn==n×(n–1)×...×2×1=n! (2).

Задача 1.3. За круглым столом надо рассадить пять мальчиков и пять девочек так, чтобы не было двух рядом сидящих мальчиков и двух рядом сидящих девочек. Сколькими способами это можно сделать?

Решение: Если по кругу занумеровать стулья, то либо мальчиков нужно посадить на чётные стулья, а девочек – на нечётные, либо наоборот, то есть нумерация может быть проведена двумя способами. При этом как девочек, так и мальчиков можно рассадить по выбранным для них стульям P5 способами. Отсюда вытекает решение: 2(P5)2 = 2×1202 = 28800 (способов).

Сочетания k элементов изМ

Сочетанием k элементов из n-элементного множества М называется подмножество множества М, содержащее k элементов.

Например, если М={a1,a2,a3} и k=2, то всеми сочетаниями из М по 2 будут {a1,a2}, {a1,a3}, {a2,a3}.

Число сочетаний из М по k обозначается . Сочетание отличается от размещения тем, что в нём не учитывается порядок выбора элементов. Поэтому, переставляя элементы, можно из каждого сочетания k элементов получить k! размещений. Тогда будет в k! раз меньше, чем .

при k<n (3)

Из формулы (3) вытекает, что и .

Кроме того, считается, что =0 при k>n.

Можно обобщить сочетания на действительные числа, положив

где a Î R (4)

Задача 1.4. Сколькими способами в игре «Спортлото» можно выбрать шесть чисел из 49? (одно число может быть выбрано не более одного раза).

Решение: .

Сумма чисел сочетаний из М по всем k, очевидно, равна числу всех подмножеств множества М, поэтому (5).

Числа сочетаний из М тесно связаны с известной алгебраической формулой бинома Ньютона: (6).

Поэтому числа сочетаний иначе называют биномиальными коэффициентами.

Для доказательства формулы (6) достаточно рассмотреть произведение n сомножителей (1+x)(1+x)...(1+x) и заметить, что коэффициент при xk получается, если выбрать из k скобок x, а из остальных – единицы. Это можно сделать способами.

Мы назвали формулу для биномом Ньютона. Это название с точки зрения истории математики неверно. Формулу для хорошо знали среднеазиатские математики: Омар Хайям, Гиясэддин и др. В Западной Европе задолго до Ньютона ее знал Блез Паскаль. Заслуга же Ньютона была в ином – ему удалось обобщить формулу для на случай нецелых показателей. Именно, он доказал, что если a>0 и |x|<a, то для любого действительного значения имеет место равенство (7).

Эта формула настолько знаменита, что даже в таком далеком от математики литературном произведении, как роман «Мастер и Маргарита», один из спутников Воланда часто повторяет: «Подумаешь, бином Ньютона!».

Сочетания с повторениями k элементов из М

Сочетанием с повторениями k элементов из n-элементного множества М называется неупорядоченная выборка (или мультимножество) из k элементов, принадлежащих М, в которой допускается повторение элементов.

Например, если М={a1,a2,a3} и k=2, то всеми сочетаниями с повторениями по 2 элемента из М будут {a1,a1}, {a1,a2}, {a1,a3}, {a2,a2}, {a2,a3}, {a3,a3}.

Число сочетаний с повторениями из М по k обозначается .

При выборе из множества М элемента ai нужно всякий раз, кроме последнего, добавлять к этому множеству ещё один такой же элемент ai, чтобы была возможность его выбора на следующем шагу. Следовательно, добавить нужно (k–1) элемент. Тогда (8). Более строгое доказательство справедливости формулы (8) смотрите в [9].

Задача 1.6. В кондитерском отделе продаются пирожные четырех сортов. Сколькими способами можно купить семь пирожных?

Решение: Поскольку не возбраняется покупать одинаковые сорта пирожных, то искомое число равно

Перестановки с повторениями из М

Перестановкой с повторениями множества М={a1,a2,...an} по k1, k2,…kn называется упорядоченная выборка из (k1+k2+...+kn) элементов, в которую элемент ai входит ki раз (ki > 0; i = 1,...n).

Например, для М={a1,a2} всеми перестановками по 3, 1 из М будут (a1,a1,a1,a2),(a1,a1,a2,a1),(a1,a2,a1,a1),(a2,a1,a1,a1).

Число перестановок с повторениями (k1+k2+...+kn) элементов из М обозначается

По сравнению с перестановками без повторений это число будет меньше в k1!k2!...kn! раз, так как перестановки одинаковых элементов не учитываются. Поэтому (9).

Задача 1.7. Сколько различных "слов" можно получить перестановкой букв в слове "абракадабра"?

Решение: В слове "абракадабра" буква "а" встречается 5 раз, "б" и "р" – по 2 раза, "к" и "д" – по одному разу. Поэтому число таких "слов" равно:

Размещения с повторениями k элементов из М

Размещением с повторениями k элементов из n-элементного множества М называется упорядоченная выборка из k элементов, принадлежащих М, в которой допускается повторение элементов.

Например, если k=2 и М={a1,a2,a3}, то всеми размещениями с повторениями двух элементов из М будут (a1,a1), (a1,a2), (a1,a3), (a2,a1), (a2,a2), (a2,a3), (a3,a1), (a3,a2), (a3,a3).

Число размещений с повторениями из М по k обозначается .

Поскольку для выбора каждого из k элементов существует n возможностей, то по правилу произведения: (10).

Ясно, что число всех подмножеств множества М равно

Задача 1.8. В некотором сказачном государстве ни у каких двух жителей не было одинакового набора зубов. Найти наибольшую численность населения этого государства.

Решение: У человека может быть максимум 32 зуба и столько же мест во рту для каждого из них. Таким образом, для каждого места существуют две возможности (независимо от других мест): либо зуб на этом месте есть, либо его нет. Поэтому искомая численность равна: 232 = 4 Внушительное число! Похоже на Китай.

Задача 1.9. Каких семизначных чисел больше: тех, в записи которых есть единица, или остальных?

Решение: Ясно, что семизначных чисел 9000000 (от 1000000 до 9999999). Чисел, в записи которых единицы нет, будет Но из них начинаются с нуля, а значит они не семизначные. Поэтому семизначных чисел, в записи которых нет единицы 4782969 – 531441 = 4251528. Следовательно, тех чисел, в которых есть единица, будет больше.

Для лучшего понимания школьниками сущности основных комбинаторных объектов и чисел можно рассмотреть модель с шарами и ящиками.

Итак, дано n ящиков и k шаров (k£n), которые нужно разместить по ящикам в соответствии с некоторыми дополнительными условиями.

1. Пусть все шары одинаковые, и в каждый ящик можно положить не более одного шара. В этом случае раскладывание шаров по ящикам фактически сводится к выбору тех k ящиков, в которые будут помещены шары. Поэтому шары можно разместить по ящикам способами.

2. Теперь пусть ящики имеют большую вместимость, то есть в каждый можно положить хотя бы и все шары, было бы желание. При этом ящик, в котором уже есть некоторое количество шаров, может выбираться для дальнейшей раскладки с тем же основанием, что и любой другой ящик. Тогда число способов раскладки будет равно .

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

4. Если шары попарно различны, но в ящик можно помещать любое их количество, то шары раскладываются способами.

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

6. Как и в предыдущем пункте, в каждый ящик можно положить только один шар, но не все шары являются различными. Пусть, например, имеется k1 красных шаров, k2 оранжевых шаров и так далее, наконец, ks фиолетовых шаров, где k1+k2+…+ks=n. Тогда шары раскладываются способами

Вышеизложенные результаты можно свести в схему (рис. 1).

Рис 1. Основные комбинаторные объекты и числа

.

§ 2 Рекуррентные соотношения. Числа Фибоначчи

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

Рекуррентные соотношения играют важную роль при составлении компьютерных программ. Многие программы основаны на так называемых рекурсивных процедурах. В каждой из них одна и та же операция последовательно применяется к возникающим с помощью этой же операции объектам. Зачастую такая операция задаётся рекуррентным соотношением.

Само понятие рекуррентного соотношения впервые было введено итальянским математиком Леонардо из Пизы (ок. ), более известным как Фибоначчи. В книге «Liber Abaci», появившейся в 1202 году он рассмотрел следующую задачу: Пара кроликов раз в месяц приносит потомство из двух крольчат (самки и самца), причём новорожденные крольчата через два месяца после рождения уже сами приносят такой же приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов, и в течение этого года кролики не умирают, а их воспроизводство не прекращается?

Из условия задачи вытекает, что через два месяца крольчата будут только у первой пары и получится три пары. А ещё через месяц приплод дадут две пары кроликов, поэтому всего будет уже пять пар кроликов. Эту ситуацию можно обобщить: если аn+1 – количество пар кроликов через (n+1) месяц с начала года, то через (n+2) месяца к этим аn+1 пар прибавится ещё столько новорожденных пар кроликов, сколько их было в конце n-ого месяца, то есть ещё аn пар кроликов. Таким образом, каждый член числовой последовательности {аn}, начиная с третьего, будет равен сумме двух предыдущих членов. Тогда для этой последовательности выполняется соотношение аn+2=аn+1+аn (11). Числа, удовлетворяющие такому условию, принято называть числами Фибоначчи.

Так как по условию задачи а0=1 (в начале года была одна пара кроликов) и а1=2, то по соотношению (10) легко можно последовательно вычислить а2=3, а3=5, а4=8, а5=13, а6=21, а7=34, а8=55, а9=89, а10=144, а11=233, а12=377.

Итого через год будет 377 пар кроликов. Кстати, завезенные в Австралию кролики так быстро размножались, что стали национальным бедствием.

Иногда рекуррентные соотношения между комбинаторными числами позволяют гораздо эффективнее и быстрее вычислять конкретные значения этих чисел, чем явная формула. Так как рекуррентные соотношения легко алгоритмизируются, то в таких вычислениях большую помощь может оказать компьютер.

Например, из формулы (1) для чисел размещений , очевидно, вытекает соотношение: =n(n–1)...(n–k+1)=n=(n–k+1).

Используя это соотношение, можно последовательно находить числа размещений из М по k, начиная с k=0 и постепенно переходя к большим значениям. Для 0£k£n£7 результат вычислений приведен в таблице 1.