Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Композиція (теорія чисел)



План:


Введення

Не слід плутати з Композиція функцій.

В теорії чисел композицією натурального числа називається його представлення у вигляді впорядкованої суми натуральних доданків. Складові, що входять у композицію, називають частинами, а їх кількість - довжиною композиції.

На відміну від композиції, розбиття числа не враховує порядок проходження частин. Тому число розбиття числа ніколи не перевершує числа композицій.

При фіксованій довжині композицій у них іноді також допускають нульові частини.


1. Приклади

Існує 16 композицій числа 5:

  • 5 = 5;
  • 5 = 4 + 1;
  • 5 = 3 + 2;
  • 5 = 3 + 1 + 1;
  • 5 = 2 + 3;
  • 5 = 2 + 2 + 1;
  • 5 = 2 + 1 + 2;
  • 5 = 2 + 1 + 1 + 1;
  • 5 = 1 + 4;
  • 5 = 1 + 3 + 1;
  • 5 = 1 + 2 + 2;
  • 5 = 1 + 2 + 1 + 1;
  • 5 = 1 + 1 + 3;
  • 5 = 1 + 1 + 2 + 1;
  • 5 = 1 + 1 + 1 + 2;
  • 5 = 1 + 1 + 1 + 1 + 1.

2. Кількість композицій

У загальному випадку існує 2 n - 1 композицій числа n і \ Binom {n-1} {k-1} композицій числа n довжини k . Для доказу цього твердження досить побудувати біекцію між композиціями n довжини k і (K - 1) -Елементними підмножинами (N - 1) -Елементного безлічі. Поставимо у відповідність композиції n = n_1 + \ ldots + n_k підмножина безлічі \ {1, \; \ ldots, \; n-1 \} , Що складається з часткових сум: \ {N_1, \; n_1 + n_2, \; \ ldots, \; n_1 + \ ldots + n_ {k-1} \} . Очевидно, у цієї відповідності є зворотне: по підмножині \ {M_1, \; \ ldots, \; m_ {k-1} \} , Елементи якого впорядковані за зростанням, можна відновити вихідну композицію:

n 1 = m 1 , n i = m i - m i - 1 при i = 2, \; \ ldots, \; k-1 і, нарешті, n k = n - m k - 1 .

Таким чином, побудоване відображення биективное, і тому кількість композицій числа n довжини k дорівнює кількості (K - 1) -Елементних підмножин (N - 1) -Елементного множини, тобто біноміальним коефіцієнту \ Binom {n-1} {k-1} .

Для підрахунку загального числа композицій числа n достатньо чи підсумувати біноміальних коефіцієнтів, або використовувати те ж відображення для побудови біекціі між усіма композиціями і всіма підмножинами.

Якщо в композиціях числа n довжини k дозволити нульові частини, то кількість таких композицій дорівнюватиме \ Binom {n + k-1} {k-1} , Оскільки збільшення 1 до кожної частини дає композицію (вже без нульових частин) числа n + k . Питання про загальну кількість композицій числа n з нульовими доданками не має сенсу, так як воно нескінченно.


Література

  • Сачков В. Н. Комбінаторні методи дискретної математики - М .: Наука, 1977. - С. 241. - 319 с.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Теорія чисел
Характер (теорія чисел)
Теорема Ейлера (теорія чисел)
Первісний корінь (теорія чисел)
Композиція
Композиція (літературознавство)
Композиція (музика)
Шахова композиція
Композиція функцій
© Усі права захищені
написати до нас