Новиков Ф.А. Дискретная математика для программистов (860615), страница 38
Текст из файла (страница 38)
Имеем:ДОКАЗАТЕЛЬСТВОт — (п— 1)5(m,n) = | B | =J2ь=1 В£ВU&\В\=Ьт — (п— 1)= J2C(m-l,b-l)S{m-b,n-l)ь= 171 — 1=^7П-1С ( г а - 1 , г а - г - 1 ) 5 ( г , п - 1) = ^г=тп— 1где г: — т. — Ь.1=Джеймс Стерлинг ( 1 6 9 9 - 1 7 7 0 ) .С(га - 1, г)5(г, п - 1),i=n— 1•1975.5. Включения и исключения5.4.3. Числа Стирлинга первого родаЧисло сюръективных функций, то есть число размещений т предметов по пящикам, таких, что все ящики заняты, называется числом Стирлинга первого родаи обозначается s(m,n).ТЕОРЕМАs ( m , п)= п! S(m,п).Каждое разбиение множества { 1 , . . . , ш } соответствует семейству множеств уровня сюръективной функции и обратно (см. 1.7.3).
Таким образом, число различных семейств множеств уровня сюръективных функций — эточисло Стирлинга второго рода S(m, п). Всего сюръективных функций s(m,n) == п\ S(m, п), так как число сюръективных функций с заданным семейством множеств уровня равно числу перестановок множества значений функции.•ДОКАЗАТЕЛЬСТВО5.4.4. Число БеллаЧисло всех разбиений m-элементпого множества называется числом Белла1 и обозначается В(т),ТПB(m) =f^S(m,n),В(0) =f 1.71=0771ТЕОРЕМАВ(т+1)=C(m,i)B(i).£г=0Пусть Ъ — множество всех разбиений множества М\ — l..(m + 1).Рассмотрим множество подмножеств множества Mi, содержащих элемент га+ 1:ДОКАЗАТЕЛЬСТВОВ: = {В С 2 M l | m + 1 еВ}.Тогда Ъ =(Jгде Ъв : = {X е Ъ \ В е X}. Пусть В е В и b = \В\. Тогдавев_\ЪВ\ = В(т + 1 - 6 ) .
Заметим, что \{В е В \ \В\ = b} \ = C{m,b- 1). Следовательно,771+1В(т+ 1) = \Ъ\ =Y^С(т,Ъ -1 )В(т-b + 1)=Ь=10=yт.c m т( '-=i=mЛг=0где г: = т — b + 1.•5.5. Включения и исключенияПриведённые в предыдущих четырёх разделах формулы и алгоритмы дают способы вычисления комбинаторных чисел для некоторых распространённых комбинаторных конфигураций. Практические задачи пе всегда прямо сводятся к1Эрик Тсмпл Белл (18831960).198Глава 5.
Комбинаторика'известным комбинаторным конфигурациям. В этом случае используются различные методы сведения одних комбинаторных конфигураций к другим. В этоми двух следующих разделах рассматриваются три наиболее часто используемыхметода.Мы начинаем с самого простого и прямолинейного, но имеющего ограниченнуюобласть применения метода включений и исключений.5.5.1. Объединение конфигурацийЧасто комбинаторная конфигурация является объединением других, число комбинаций в которых вычислить проще. В таком случае требуется уметь вычислятьчисло комбинаций в объединении.
В простых случаях формулы для вычисленияочевидны:\АиВ\= \А\ +\АиВиС\\В\-\АпВ\,= \А\ + |£| + \С\ - \АГ) В\ - \В (1С\ - \АпС\+ \АГ) В Г)С\.Пример Сколько существует натуральных чисел, меньших 1000, которые неделятся ни на 3, ни на 5, ни на 7? Всего чисел, меньших тысячи, 999. Из них:999 : 3 = 333 делятся на 3,999 : 5 = 199 делятся на 5,999 : 7 = 142 делятся на 7,999 : (3 * 5) = 66 делятся на 3 и на 5,999 : (3 * 7) = 47 делятся на 3 и на 7,999 : (5 * 7) = 28 делятся на 5 и на 7,999 : (3 * 5 * 7) = 9 делятся па 3, на 5 и на 7.Имеем: 999 - (333 + 199 + 142 - 66 - 47 - 28 + 9) = 457.5.5.2. Формула включений и исключенийСледующая формула, известная как формула включений и исключений, позволяет вычислить мощность объединения нескольких множеств, если известны ихмощности и мощности всех возможных пересечений.ТЕОРЕМАп1Мг= 1=£г=1|Л<ПЛ,| +l<i<j<n+ (-1Г-1|л1п...пЛп|.\AinAjHAk\-...l^,i<i<k£.n1995.5.
Включения и исключенияИндукция по п. Для п = 2,3 теорема проверена в предыдущемподразделе. ПустьП— 171-1ДОКАЗАТЕЛЬСТВОи*= Е"| Ai П A j | + . . . + ( - l ) n " 2 | Ai П . . . П A n . ,Ег=11 jsjn — 1'тг—1 \тг— 1Заметим, что ( (J Ai ) ПАп = (J (AiDA n ) f и по индукционному предположению. г=1 /г=1тг—1тг — 1г=1г= 1—1+ ( 1)Тогдапп-2'тг—1U Ai] U Ап.1=1тг-1и*г=1ЕI^I-=| ^ 1 П . .
. П Ап-\П71 — 1'тг—1+ |Лг| -г=1Е\Ап\.U Ai)ПАтЛ=1л*п+ • • • + (-1)71"Viп...пAn—i|] +У г=1/тг-1+ \Ап\- [ Y \Ain An \-Е\A\ П . . . П An-iП An\| Ai П A j П A n | + . . . +,г=1+=n-1l^n^l + ^l^nXnl)i=1'n-1=+- (£,i=l-(-1)П~2\А1П...ПАП-1ПАП\+...-=Tl=г=1EИг nAj\ + ... + (-l)n_1|>lil^iCj^nП ... П An\.•ЗАМЕЧАНИЕОбозначения сумм с неравенствами в пределах суммирования, использованные в формулировке и доказательстве теоремы, являются не более чем сокращённой формой записикратных сумм.
Например,тг— 1означает1пY,•г=1 j=j + 1200Глава 5. Комбинаторика'5.5.3. Число булевых функций, существенно зависящихот всех своих переменныхРассмотрим применение формулы включений и исключений на примере следующей задачи. Пусть р п = f \Рп\ = 2 2 " — число всех булевых функций п переменных,а Рп — число булевых функций, существенно зависящих от всех п переменных(см. 3.1.2). Пусть Р* — множество булевых функций, у которых переменная х*фиктивная (кроме х-, могут быть и другие фиктивные переменные). Имеем:p„ = i p „ \ ( P , ; U .
. . U ^ ) | =г= 12С другой стороны, \Рп\ = 2 " \ более того, |Р^ П ... П Р^К\ = 22"нение 3.1). Следовательно,\г=11(см. упраж-lsjicjsjn= 2 2 ' 1 - ( С ( п , 1 ) 2 2 " - 1 — С ( п , 2)2 2 "2+ . . . + ( — 1 ) п _ 1 С ( г г , п)2^ =пг=05.6. Формулы обращенияОчень полезную, но специфическую группу приёмов образуют различные способы преобразования уже полученных комбинаторных выражений. В этом разделерассматривается один частный, но важный случай.5.6.1.
Теорема обращенияПусть а П А; и Ьп,к — некоторые (комбинаторные) числа, зависящие от параметровпик, причём 0 ^ к ^ п. Если известно выражение чисел ап^ через числа Ьпто в некоторых случаях можно найти и выражение чисел Ьп,к через числато есть решить комбинаторное уравнение.ТЕОРЕМАПустьVn^Qn.fc = У^ Ап,А:,гЬтг,г^ ^u пусть3fin,k,i(v/c<nVIVm^nV{y^Un,k,iK,i,mV^= s i'm, f'[о, тф к2015.6.
Формулы обращенияТогдаVfc ^ п I brhk =y^n,k,ian,i\i=о,ДОКАЗАТЕЛЬСТВО=Е ^ А 'г=0г=0=Е=\тп=0/п / тг\^ ^ ( ^ ^ Р п , к , г I Ьп тп —т=0СИ\г=05.6.2. Формулы обращения для биномиальныхкоэффициентовПрименение теоремы обращения предполагает отыскание для заданных чиселAn,fc,i (коэффициентов комбинаторного уравнения) соответствующих чисел /хп,л,г>удовлетворяющих условию теоремы обращения. Особенно часто числами \n,k,iявляются биномиальные коэффициенты.пЛЕММА(У ( - 1 ) ^ШС ( П . Г ) С ( Г , Т )={I0'Ы_'т < п•Используя формулу 3 из подраздела 5.3.1 иС(п — m,i — т) = 0 при г ^ га, имеем:ДОКАЗАТЕЛЬСТВОТОТфакт, чтог)С(г, га) = ^ ( - 1 )*~ m C(n, т)С(п - га, i - га) =г=0г=0п= y^( — l)i~rnC(n,m)C(n— m,i — га) =г=тпп= С(п, тп)i=mНо при т < п имеем:П£ ( - 1 у-тС(пг=т)*~тС(п-га,г-т).Tl — TTl- m,t - га) = Y , ( - 1 ) J ' C ' ( n j=Огде у, —г — т. С другой стороны, при га = п имеем:пС(п, га) {-iy~mC{n-m,i-m)= С(п, п)(-1)п~пС(0,0)== 1.•202Глава 5.
Комбинаторика'ккг=0г=0Если ап,к = £ С{к, i)bn4, то Ъщк = £ ( - 1 )к~{С(к,ТЕОРЕМА 1ДОКАЗАТЕЛЬСТВОг)апА.Здесь Xnikii = С(/г, г) и /zn,fc,i = (-l) f c _ i C(fc, г). При кимеем:г=0г=Ог=0к= J2(-l)k~i+m~mC(k,i)C(i,m)=г=О= (-1)*-т£(-1ГтС(М)С(г,ш) = (г=0•I£слм аП)А: = £ С(г, /с)ьп,г, т о ЪП}к = £ ( - l ) i _ f c C ( i , fe)an>i.ТЕОРЕМА 2г=кДОКАЗАТЕЛЬСТВОi=kЗдесь Xn<k}i = С(г, /:) и /in,fc,i = (-l)*~ f c C(i, к). При кимеем:ппг=0г=05.6.3. Формулы для чисел СтирлингаВ качестве примера использования формул обращения рассмотрим получениеявных формул для чисел Стирлинга первого и второго рода.
Рассмотрим множество функций / : А —• В, где \А\ = п и \В\ = к. Число всех таких функций равнокп. С другой стороны, число функций / , таких, что \f{A)\ = г, равно s(n,г), поскольку s(n,i) — это число сюръективиых функций / : 1 ..п —> 1 ..г. Но множествозначений функции (при заданном г) можно выбрать С(к, г) способами. Поэтомуг=0пОбозначив aTl)fc : = к и Ьп,г: = s(n, г), имеем по теореме 1 предыдущего подразделакl)/c-iC(fc,s(n,k) =г=0г)гп.2035.7. Производящие функцииУчитывая связь чисел Стирлинга первого и второго рода, окончательно имеем:1к5.7.
Производящие функцииДля решения комбинаторных задач в некоторых случаях можно использовать методы математического анализа. Разнообразие применяемых здесь приёмов весьмавелико и не может быть в полном объёме рассмотрено в рамках этой книги. В данном разделе рассматривается только основная идея метода производящих функций, применение которой иллюстрируется тремя простыми примерами.
Болеедетальное рассмотрение можно найти в литературе, например, в [22].5.7.1. Основная идеяПусть есть последовательность комбинаторных чисел а* и последовательностьфункций ifii(x). Рассмотрим формальный рядi7(х) называется производящей функцией (для заданной последовательности комбинаторных чисел ai относительно заданной последовательности функций <Pi(x)).ИЛИ pi(x) =f xl/i\.Обычно используют Ifi(x)ПримерИз формулы бинома Ньютона при у = 1 имеем:п(1+х)п = ^ С ( п , г ) х \г=0Таким образом, (1 4- х)п является производящей функцией для биномиальныхкоэффициентов.5.7.2. Метод неопределённых коэффициентовИз математического анализа известно, что если= Yaiifi(x)iи7(х) = Ybi(pi(x),iто Уг (ai = bi) (для рассматриваемых здесь систем функций щ).В качестве примера применения производящих функций докажем следующеетождество.204Глава 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
