Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Комбинации элементов с повторениями
Пусть имеем неупорядоченное n -злементное множество A элементы которого разбиты на n классов (в каждом классе находится по одному элементу), которые будут называться типами элементов.
Комбинацией из n элементов по m с повторениями называется m -элементное подмножество множества A, каждый элемент которого принадлежит одному из n типов. Совокупность таких комбинаций называют комбинациями из n элементов по m
Теорема 1.2.8. Количество различных комбинаций из n элементов по m элементов с повторениями равно
Доказательство. «Закодируем» каждую комбинацию следующим образом. Если комбинация включает k1 элементов первого типа, то записываем подряд k1 единиц, ставим нуль. После него ставим подряд k2 единиц, если комбинация включает k2 элементов другого типа и т.д.
Например, если A ={a, b, c, d}, то комбинациям по два элементас повторениями соответствуют пары {a,a}, {а,b}, {а,с}, {а,d}, {b,b}, {b, с}, {с,d}, {с,с}, {с,d}, {d,d}, аих "кодами" будут соответственно
11000, 10100, 10010, 10001,..., 00011.
Нетрудно убедиться, что между "кодами" и комбинациями существует взаимно однозначное соответствие (убедитесь самостоятельно).
Таким образом, каждой комбинации из п элементов по m соответствует последовательность из т единиц и п-1 нулей (в рассмотренном примере п = 4, т = 2). Следовательно, число всех комбинаций из п элементов по т с повторениями равно числу последовательностей, состоящих из т единиц и п - 1 нулей, т. е. 
. Теорема доказана.
Пример 1.2.7
Сколько целых неотрицательных решений имеет уравнение
x1 + x2 +... + хn = т? (1.2.4)
Решение. Решения данного уравнения можно интерпретировать так. Если имеем целые неотрицательные числа x1, х2,..., xп, такие что х1 + х2 +... + xп = т, то можно составить комбинацию из п элементов по т, взяв хi элементов первого типа, х2 элементов второго типа,..., xп элементов n -го типа.
Наоборот, имея комбинацию из п по т элементов, получим решение уравнения (1.2.4) (x1, х2..., xn - число элементов первого, второго, и, соответственно, n -го типа), где все хi неотрицательные (i = 1, 2,..., n). Таким образом, между множеством всех неотрицательных решений уравнения (1.2.4) и множеством всех комбинаций из п элементов по т устанавливается взаимно однозначное соответствие. Следовательно, число целых неотрицательных решений уравнения (1.2.4) равно
Например, если x1 + x2 + x3 + х4 = 10, то это уравнение имеет
целых неотрицательных решений.
Date: 2015-07-24; view: 282; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |