АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Разбиения чисел

Читайте также:
  1. Алгебраическая и тригонометрическая формы записи комплексных чисел.
  2. Алгебраїчна замкненість поля комплексних чисел. Канонічний розклад многочленна над полем комплексних чисел та його єдиність.
  3. Алгебраїчна форма запису комплексних чисел та дії над комплексними числами, записаними у цій формі
  4. В будущее с помощью чисел
  5. В результате суммарный спин (и сумма спиновых квантовых чисел) электронов на оболочке, состоящей из нескольких орбиталей, будет максимальным.
  6. Введите через пробел 15 чисел
  7. Ввод чисел и символов в калькулятор
  8. Взаимосвязь чисел и букв
  9. Визначення необхідної чисельності вибірки.
  10. Властивості логарифмів чисел
  11. Властивості спряжених чисел
  12. Вопрос №21. Операционный блок для сложения и вычитания двоичных чисел с фиксированной точкой. Назначение узлов и блоков. Алгоритм выполнения операций сложения и вычитания.

Разбиением натурального числа n на k слагаемых называется последовательность таких положительных натуральных чисел (a1, a2, × × ×, ak), что

n = a1 + a2 + × × × + ak, k>0, a1³ a2³ × × × ³ ak > 0.

Пусть P(n,k) – число разбиений n на k слагаемых. Тогда число всех разбиений равно , n>0.

Полагаем по определению P(0)=P(0,0)=1.

Пример 1. P(5)=7:

5 = 5,

5 = 4+1,

5 = 3+2,

5 = 3+1+1,

5 = 2+2+1,

5 = 2+1+1+1,

5 = 1+1+1+1+1.

Замечание. Каждое разбиение можно наглядно представить с помощью диаграммы Ферреса, которая для n = a1 + a2 + × × × + ak состоит из k строк, а i -строка содержит ai точек. Например, для 5 = 2 + 2 + 1 диаграмма Ферреса показана слева на рисунке 3.1. Если отразить диаграмму относительно ее главной диагонали, то мы получим диаграмму Ферреса, которая называется сопряженной. На рисунке 3.1 справа показана сопряженная диаграмма Ферреса. Она будет соответствовать разбиению 5=3 + 2.

· · · · · · · · · ·    

 

Рис. 3.1. Диаграммы Ферреса

Лемма 1. Число разбиений P(n) равно количеству решений

(l1, l2, × × ×, ln)

уравнения l1 ×1 + l2 ×2 + × × ×+ ln ×n = n.

Доказательство. Если среди чисел a1³ a2 ³ × × × ³ ak разбиения числа n имеется l1 - единиц, l2 - двоек, × × ×, ln - n -ок, то получаем решение уравнения. Ясно, что это соответствие взаимно однозначно.

Обозначим через Ph(n) количество разбиений числа n на слагаемые, не большие чем h.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)