4.2. Сочетания с повторениями
Пусть М = {e1, e2, … em}.
Количество вхождений объекта в комбинацию называется кратностью.
Пусть кратность объекта ei может составлять k1(ei) или k2(ei) или …
Рассмотрим произведение:
(xk1 (e1) + xk2 (e1) + … ) (xk1 (e2) + xk2 (e2) + … ) …(xk1 (em) + xk2 (em) + … ).
После раскрытия скобок и приведения подобных коэффициент при xk равен числу требуемых сочетаний с повторениями.
Теорема. Число сочетаний с повторениями из m по k без всяких ограничений на кратность элементов в данном сочетании составляет C k m+ k −1.
4.3. Размещения
Составим экспоненциальную производящую функцию последовательности a(k) = Akm:
A0m + (A1m / 1!) x + (A2m / 2!) x2 + … = Cm0 + Cm1 x + Cm2 x2 + …= (1+x) m.
4.4. Размещения с повторениями
Пусть t − такая выборка из М = {e1, e2, … em}, что объект e1 входит в t t1 раз, e2 входит в t t2 раз,… em входит в t tm раз, причём t1 + t2 + … + tm = k. Тогда t называется k–выборкой состава t1, t2, … , tm .
Обозначим:
P (t1, t2, … , tm) = k! / ( t1! t2! … tm ! ).
Пусть кратность объекта ei может составлять k1(ei) или k2(ei) или …
Составим экспоненциальную производящую функцию:
(xk1 (e1) / k1(e1)! + xk2 (e1) / k2(e1)! + … ) ×
× (xk1 (e2) / k1(e2)! + xk2 (e2) / k2(e1)! + … ) ×
…
× (xk1 (em) / k1(em)! + xk2 (em) / k1(em)! + … ).
Предположим, что скобки раскрыли. Проанализируем состав одного слагаемого в коэффициенте при xk, соответствующего выборке (k
(e1), k
(e2), …, k
(em)):
[ x
(e1) / k(e1)! ] × [x
(e2) / k(e2)! ] × … × [x
(em) / k(em)! ] =
= xk / [k(e1)! k(e2)! … k(em)!] * (k! / k!) =
= P (k(e1), k(e2), … k(em)) × xk / k!.
Теорема. Число k–выборок без ограничения на количество повторений составляет mk .
4.5. Композиции числа k – это суммы вида: 
zi = k, где m, k, zi Î N, причём суммы, отличающиеся порядком слагаемых, считаются различными.
Обозначим zk (m) – количество композиций числа k на m частей;
zk – количество композиций числа k на произвольное количество частей.
zk(m) равно числу способов разместить m–1 разделитель в k–1 ячейках между k единицами, т. е. 
.
Доопределим z(x) = 0, если k < m.
Пусть ak = 
= 
. Тогда a(x) = 1/ (1–x)m .
Очевидно, что
zk(m) = 
® z(m)(x) = a(x) xm = xm / (1–x)m .
Перейдём к определению zk: zk = 
zk(m) = = 2k−1.
Пусть bk = 2k. Тогда b(x) = 1/ (1–2x).
Очевидно, что
zk = 
® z(x) = b(x) x = x / (1–2x) .
4.5. Разбиения числа k – это суммы вида: zi = k, где m, k, zi Î N, причём суммы, отличающиеся порядком слагаемых, считаются одинаковыми.
Обозначим
rk (m) – количество разбиений числа k на m частей;
R(m,k) – количество разбиений числа k на части, максимальная из которых не превышает m.
Лемма. Число решений уравнения 1× x1 + 2× x2 + … m × xm = k в целых неотрицательных числах равно R(m,k).
Теорема. Количество разбиений числа k на m частей равно количеству разбиений числа k на части, максимальная из которых равна m, т. е. rk (m) = R(m,k) – R(m–1,k).
Теорема. Пусть R(m,x) – производящая функция последовательности R(m,k). Тогда
R(m,x) = (1+x+x2+…) (1+x2+x4+…) (1+x m +x2 m +…) = (1/ (1– x)) (1/ (1– x2)) …(1/ (1– xm)).
ГЛАВА II. РЕКУРРЕНТНЫЕ УРАВНЕНИЯ (РУ)
§ 1. Основные определения
Задача Фибоначчи.
Пара кроликов приносит 1 раз в 1 месяц приплод − девочку и мальчика. Через 1 месяц после рождения крольчата вырастают и через 2 месяца после рождения приносят приплод. Сколько пар кроликов набралось к концу года, если в начале года была 1 пара (в течение года кролики не умирали, воспроизводство не прекращалось)?
Составим математическую модель задачи. Обозначим
f(n+1) − количество пар кроликов по истечении (n+1) месяца с начала года. Тогда через месяц количество пар кроликов составит:
f(n+2) = f(n+ 1) + f(n), причём f(0) = 1, f(1) = 2.
Решением этой задачи является последовательность Фибоначчи: 1, 2, 3, 5, 8, 13, 21, …, f(12) = 377, …
Чтобы получить выражение для f(n) в симметричном виде, к этой последовательности слева добавляют единицу: 1, 1, 2, 3, 5, 8, 13,…, т. е. считают, что f(0) = f(1) = 1.
Общий вид РУ:
f(n+k) = F(n, f(n+k−1), …, f(n)), (1.1)
где
k − порядок РУ, f(n) − неизвестная числовая последовательность, F − функция от (k+1)-й переменной.
Последовательность a(n) называется решением РУ (1.1), если при подстановке её в (1.1) вместо f(n) получается истинное равенство при n=0,1,2,...
В общем случае РУ имеет бесконечное множество решений. Чтобы однозначно определить решение РУ (1.1), следует задать k начальных условий:
f(0) = j0, f(1) = j1, …, f(k−1) = jk−1.
Пусть C1, C2,…,Ck − независимые числовые параметры.
Последовательность Ф(C1, C2,…,Ck, n) называется общим решением РУ (1.1), если
- при любом выборе параметров C1, C2,…,Ck последовательность является решением (1.1), для любого решения a(n) можно так подобрать значения параметров C1*, C2*,…,Ck*, что равенство a(n) = Ф(C1*, C2*,…,Ck*, n) выполняется при n=0,1,2,...
Решение, полученное из общего решения при фиксированном значении параметров, называется частным решением РУ (1.1).
§ 2. Линейные РУ с постоянными коэффициентами
РУ вида
f(n+k) = a1 f(n+k−1) + a2 f(n+k−2) + … + ak f(n) + u(n), где k > 0, (2.1)
называется линейным РУ с постоянными коэффициентами;
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)