![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Перестановки с повторениями
Перестановкой с повторениями называется размещение с повторениями по n из n элементов k -множества M (k £ n) со следующим дополнительным условием: различные k элементов множества M повторяются соответственно n 1,…, nk раз, 1£ n 1,…, nk £ n, n 1+…+ nk = n. Теорема 6. Число перестановок с повторениями различных k элементов n 1,…, nk раз, 1£ n 1,…, nk £ n, n 1+…+ nk = n, равно Доказательство. Пусть M – множество номеров перестановки с повторениями, одной из указанных в условии теоремы, M 1,…, Mk – множества номеров с одинаковыми элементами, повторяющимися n 1,…, nk раз соответственно. Тогда семейство множеств { M 1,…, Mk } будет разбиением множества M на k блоков. Значит, каждой перестановке с повторениями соответствует вполне определенное разбиение множества M на k блоков. Ясно, что это соответствие является биекцией. Значит, искомое число перестановок с повторениями равно числу разбиений на k блоков Задача 3. Найти число всех перестановок букв слова «баобаб». Решение. n 1=3 (буква «б»), n 2=2 («а»), n 1=1 («о»), значит, 3. Производящие функции. Формальный ряд a 0+ a 1 x + a 2 x 2+…+ akxk +… называется производящей функцией последовательности a 0, a 1, a 2,…, ak,… Производящая функция является или сходящимся рядом, или расходящимся рядом. Два расходящихся ряда могут быть равны как функции, но быть производящимися функциями различных последовательностей. Например, ряды 1+2 x +22 x 2+…+2 kxk +… и 1+3 x +32 x 2+…+3 kxk +… определяют одну и ту же функцию (равную 1 в точке x =1, неопределенную в точках x >1), но являются производящими функциями различных последовательностей. Свойства производящих функций последовательностей: сумма (разность) производящих функций последовательностей an и bn равна производящей функции сумме (разности) последовательностей an + bn; произведение производящих функций последовательностей an и bn является производящей функцией свёртки последовательностей an и bn: cn = a 0 bn + a 1 bn -1+…+ an -1 b 1+ anb 0. Пример 1. Функция Пример 2. Функция
Дата добавления: 2014-01-03; Просмотров: 419; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |