dimaniac
Удален
|
    
2 Guest
Блин Стенли это книга для МатеМатов(матерых математиков) уж слишком все сжато. В задаче про перестановки мне не ясно доказательство принципа включения-исключения см стр 103-106. Из чего следует
sum(Y <= T) ((-1)^|T-Y|*sum(Z <= Y) f(Z)) = sum(Z <= T) (sum(Z <= Y <= T) (-1)^|T-Y|)*f(Z)? (Имеется ввиду двойственная форма) Кстати в других книгах этот принцип формулируется как-то иначе. В "Комбинаторном анализе" Рыбникова например N(r) = sum(k=r)^m ((-1)^(k-r) * C(k)^(r) * sum(1<=i1 <...<ik<m) Ni1,...,ik) Не улавливаю связи. Что в моем случае является свойствами? Разжуйте и положите в рот, пожалуйста.
Честно говоря у меня нет времени разбираться со Стенли. Всего месяц до сессии, сами понимаете. Поэтому можно еще одну формулу. В последней задачке при фиксированном числе слагаемых множители изменялись от 1 до n. Теперь то же самое но множители ограничены сверху числом l 1 <= l <= n, т.е. если l = 2, то 1*3 и 3*1 не входят в сумму.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 1 мая 2005 1:55 | IP
|
|
Guest
Новичок
|
Цитата: dimaniac написал 1 мая 2005 1:55
В задаче про перестановки мне не ясно доказательство принципа включения-исключения см стр 103-106. Из чего следует
sum(Y <= T) ((-1)^|T-Y|*sum(Z <= Y) f(Z)) = sum(Z <= T) (sum(Z <= Y <= T) (-1)^|T-Y|)*f(Z)?
Здесь просто поменяли порядок суммирования. Было сначало суммирование по Z, потом по Y, а стало суммирование по Y, потом по Z, с учетом включения Z <= Y <= T.
sum(Y <= T) sum(Z <= Y) ... = sum(Z <= T) sum(Z <= Y <= T) ...
Цитата: dimaniac написал 1 мая 2005 1:55
Кстати в других книгах этот принцип формулируется как-то иначе. В "Комбинаторном анализе" Рыбникова например N(r) = sum(k=r)^m ((-1)^(k-r) * C(k)^(r) * sum(1<=i1 <...<ik<m) Ni1,...,ik) Не улавливаю связи. Что в моем случае является свойствами? Разжуйте и положите в рот, пожалуйста.
Достаточно положить Z = { i1, i2, ..., ik }, f(Z) = Ni1,...,ik, и заменить суммирование по Z суммированием по k=|Z| и 1<=i1 <...<ik<m.
Цитата: dimaniac написал 1 мая 2005 1:55
В последней задачке при фиксированном числе слагаемых множители изменялись от 1 до n. Теперь то же самое но множители ограничены сверху числом l 1 <= l <= n, т.е. если l = 2, то 1*3 и 3*1 не входят в сумму.
Производящая функция равна
(1-x)^2 / (1 - 3x + x^2 + (l+1)x^(l+1) - lx^(l+2))
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 2 мая 2005 5:39 | IP
|
|
|
Форум
Кодирование перестановок.
