Таблицы Брадиса

Комбинаторика 1

Комбинаторика 1

Элементы математики в задачах - Г. А. Мерзон

Решение. Формально нам надо проверить 6 утверждений: можно ли установить биекцию между первым и вторым множеством, между первым и третьим, вторым и третьим и т. д. Однако, воспользо­вавшись утверждением задачи 9, мы можем показать, что между всеми вышеперечисленными множествами можно установить биек­цию, построив (явно) лишь три отображения. А именно, построим биективные отображения между множеством натуральных чисел и остальными тремя.

Обозначим множества из пунктов а), б), в) и г) соответственно буквами А, В, С и В и зададим биективные отображения:

 

А

 

 

п

 

 

 

I

 

 

 

 

 

 

В

 

 

2п

 

 

А

 

п

 

I

 

 

і

 

 

 

 

С

 

п +1

А

 

 

 

 

I

 

 

I

 

 

В

 

'

 

 

-Є-

Комбинаторика 1

листок 3 / сентябрь 20 04

Ш в этом листке обсуждаются простейшие комбианторные задачи на нахождение числа каких-то объектов. Общий метод решения этих задач следующий. Нужно придумать разумный способ перечисления (возможно с повторениями) всех интересующих нас объектов. На­пример, часто удобно перечислять что-либо в лексикографическом («алфавитном») порядке. Длину получившегося списка часто неслож­но вычислить.

После этого следует учесть наличие в списке повторений — раз­ных записей, соответствующих одному и тому же (с точки зрения данной задачи) объекту. В простейшем случае все объекты повторя­ются одно и то же число раз, и достаточно разделить число элементов в списке на количество повторений («число симметрий объекта»). Развитием этой идеи является, например, лемма Бернсайда (простей­шие проявления которой можно встретить и в этом листочке).