Перестановки (стр. 2 из 2)

P(n

, ..., n ) = n!/n !...n ! , где n = n +...+n .

Доказательство. Перестановка (b

, ..., b ) состава (n , ..., n ) множества {a , ..., a } кодируется кортежем длины k: на первом месте кортежа записано множество тех мест в перестановке на которых расположен элемент ; на втором месте кортежа записано множество тех мест в перестановке, на которых расположен элемент ; ...; на k - ом месте кортежа записано множество тех мест в перестановке, на которых расположен элемент . Первый элемент кортежа может быть выбран способами; если первый элемент выбран, то второй можно выбрать способами; ...; если первые элементов выбраны, то k- ый элемент может быть выбран способами. По правилу произведения получаем, что число всех перестановок с повторениями состава (n , ..., n ) из {a , ..., a } равно

P(n

, ..., n ) = ... =

=

Обозначение. Для " n

, ..., n ÎN полиномиальный коэффициент определяется равенствами:

если n

+...+ n = n, то ;

если n

+...+ n ¹ n, то .

Следствие 1. Пусть A и B- конечные множества такие, что |A| = n, |B| = k, (n

, ..., n )ÎN , n +...+ n = n, B = {b , ..., b }. Тогда число всех функций

f:A®B таких, что |f

(b )| = n для всех i = 1, ..., k, равно .

Доказательство. Пусть A={a

, ..., a }. Запишем функцию f:A®B в табличном виде .

Кортеж (f(a

), ..., f(a )) есть перестановка с повторениями состава (n , ..., n ) множества {b , ..., b }.

Следствие 2. Пусть U- конечное множество, |U| = n. Тогда число кортежей множеств (A

, ..., A ) таких, что

|A

| = n , ..., |A | = n ,

|A

ÇA | = Æ для всех i ¹ j,

A

È...ÈA = U, равно .

Доказательство. По теореме 2 п.3 число таких кортежей равно

... = .

Список литературы

Е.Е. Маренич, А.С. Маренич. Вводный курс математики. Учебно-методическое пособие. 2002

В.Е. Маренич. Журнал «Аргумент». Задачи по теории групп.

Кострикин А.И. Введение в алгебру. Ч.1 Основы алгебры. – М.: Физмат лит-ра, 2000

Кострикин А.И. Введение в алгебру. Ч.2 Основы алгебры. – М.: Физмат лит-ра, 2000

Кострикин А.И. Введение в алгебру. Ч.3 Основные структуры алгебры. – М.: Физмат лит-ра, 2000

Кострикин А.И. Сборник задач по алгебре. Изд. третье – М.: Физмат лит-ра, 2001