2.4. Принцип взаимно однозначного соответствия
Формулировка принципа: если каждому элементу a множества A соответствует единственный элемент b множества B, и наоборот - каждому элементу b множества B соответствует единственный элемент a множества A, иначе говоря, между множествами A и B установлено взаимно однозначное соответствие, то мощности (число элементов) этих множеств совпадают, т.е. | A | = | B |.
На данном принципе, относящемся к разряду основополагающих (ключевых), базируются очень многие математические понятия, например, такие как равномощные множества, эквивалентные системы алгебраических уравнений, обратные функции и т.п.
Идея применения принципа взаимно однозначного соответствия достаточно проста. Она состоит в том, что комбинаторная задача, когда ее прямое решение затруднительно (не представляется возможным), сводится к другой (не обязательно похожей, подобной) задаче, которая либо уже решена, либо ее решение проще, чем исходной задачи.
Фактически исследуемая комбинаторная ситуация заменяется некой (специально построенной, подобранной) математической моделью, позволяющей, с одной стороны, адекватно отражать (описывать) характер ситуации и, с другой стороны, упростить процесс решения искомой задачи.
Ясно, что одно дело - провозгласить (выдвинуть) идею, а другое – реализовать ее на практике. Трудности здесь очевидны. Они обусловлены прежде всего тем, что каждая конкретная комбинаторная задача (ситуация) по своей сути уникальна и поэтому какого-то общего (единого, универсального) подхода (приема) к построению (выбору) подходящей модели просто не может быть.
В примере 2.8 для реализации принципа взаимно однозначного соответствия используется специальный искусственный прием, основанный на том, что изучаемое множество (множество подмножеств) заменяется его моделью - более простым (с точки зрения структуры) равномощным множеством двоичных чисел (последовательностей нулей и единиц).
Этот прием, не претендующий на универсальность, достаточно успешно применяется для исследования различных комбинаторных ситуаций, что подтверждается целым рядом представленных далее примеров.
Так, в примере 2.9 с помощью указанного приема обосновано рекуррентное уравнение, выполняющее роль математической модели исследуемой комбинаторной ситуации с двоичными числами. Это уравнение давно известно, оно, в частности, отражает динамику размножения (изменения числа) кроликов применительно к условиям задачи, приведенной в рукописи итальянского математика Л.Фибоначчи еще в XIII веке (1202 год):
Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?
Правомерность использования рекуррентного уравнения для решения задачи Фибоначчи подтверждается как путем графического отображения процесса изменения числа пар кроликов, так и более строгим математическим обоснованием, представленным в примере 2.10.
Элементы (значения) числовой последовательности (решетчатой функции) f ( n ) ( n = 0,1,2,…), удовлетворяющие полученному в примере 2.9 рекуррентному уравнению и определяющие количество пар кроликов на конец n-го месяца, получили название чисел Фибоначчи. Последние обладают целым рядом замечательных свойств и занимают особое положение в теории непрерывных (цепных) дробей.