Теория графов и комбинаторика

С С И , К ) С И - К ) ! = ; S O = 5 1 C - 0 \ S , = ^ I K = O t ^ o K! ' 1 ^ 0 K l ' Совпадениями называются первотановки, в которнх помора некоторых элементов совпадают о их порядковые номор&мк в пе­ рестановке. Вычиолны число совпадеякй, в которых ровно t эламенто:^ находятся на "своих" меотах, т . е , ; S ^ = S K - O Y C W K . - ' J - V K - = К = О ^ К = О t[ К I (ПК)! '2-{ K | 'til ® • 513 . 9 . Понятав 0 методе ппоизволшиих $.у'пагаГ! Метод производящих ^!7Н1Щий яиляотоя од1П1м из садах мощ­ ных методов комбшзаторикн. ГГуоть (Z = ( ЛО,ЙЧ ,... ,Й.Ц,... J- числовая пооледоввтвльноотъ. Обычной производящей функцией пооледова' .^льяооти Л называвг- оя ^)ункция S( l C ^) , равная оумме степеяпого ряпа о коэ1р(|,ип ;и- ентами й . ; : о » ^ •=Z - Л ч t . (13.20) И « О Воли производящая функция извеотна, то, оперируя с f a . С •t J , можно "производить" свойства пооладовательяоотп С1 . Таким образом, метод производящих функций позволяет при­ менят ь для решения комбинаторных задач мегоды матвма^ичеокого "HavTOaa. Однахсо на этом пути возникает препятотвие, связонное с иоосЗходнмоотью ..ооледоват1я охсдимооти ряда ( 13.ЙО ) и опре­ д е л е ни я ого 1ддяуоа сходимооти. Для ил>.Х1траций Еозможнсстей метода прсцзводшцлх функций раоомотаим пример псоледовательнооти биношалъных коайицнея- тов С С(>^гК) , и ) . Как видно из формулы (Х3.6), про­ изводящей функцией пооледоватолъиооти биномиальных коэффици­ ентов является функция и 4 S (ji-Ь) 'i , jv,T:/ VI (13.21) 85