Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 97
Текст из файла (страница 97)
Предположим, имеется множество А, содержащее 1 объект типа а, 1 объект типа Ь, 2 объекта типа с и 2 объекта типа !1. Пусть х! представляет 2 объектов типа !. Таким образом, 1, обозначает О элементов типа а, хь обозначает 1 элемент типа Ь и хг обозначает 2 элемента типа с.
Например, х,'х'х21хо представляет выбор 1 объекта типа а, 1 объекта типа Ь и 2 объектов типа с. Тогда коэффициент при х4 равен количеству способов выбора 4 объектов среди объектов 4 типов, принадлежащих множеству А. Легко представить, что 1,+х,+хг означает выбор О, 1 или 2 объектов типа с. (1+ х)(1+ х+ хг)(1+ х + ха + хз)(1+ х+ ха + ха + х4+ хь) РАЗДеп 13.3.
производящие функции и комбинаторные подсчеты 537 Коэффициент при х" представляет количество способов выбора г объектов из множества, содержащего 1 элемент типа а, 2 элемента типа Ь, 3 элемента типа с и 5 элементов типа Ы, если нижние индексы в произведении опущены, а также количество решений уравнения е, + еь + е, + ек = т при О < е, < 1, О < еь < 2, О < е, < 3 и О < ек < 5. ПРИМЕР 13.8. В урне находятся 4 красных, 5 синих и 2 зеленых шара. (а) Сколь- ко существует способов выбора 7 шаров из урны? (б) Сколько существует спосо- бов выбора из урны 7 шаров, если 1 шар красный и 2 синие. Для части (а) производящая функция имеет вид (1+х+х +х +х )(1+х+х +х +х +х )(1+х+х ), и количество способов выбора 7 шаров равно коэффициенту при хт в разложении этой производящей функции.
В части (б) нужно учесть, что 1 вытянутый шар красный, соответствующий многочлен имеет вид (х + хг + хз + х"), что представляет вытягивание 1, 2, 3 или 4 красных шаров. Точно так же, учитывая, что 2 вытянутых шара синие, соответствующий многочлен должен иметь вид (хг+хз+х4+хз), что представляет вытягивание 2, 3, 4 или 5 синих шаров. Таким образом, производящий многочлен имеет вид (х + хг + хз + х')(хг + хз + х' + хз)(1+ х + хг), и количество способов выбора 7 шаров равно коэффициенту при хт в разложении производящей функции.
П ПРИМЕР 13.9. Допустим, в урне находятся 3 красных, 8 зеленых, 9 оранжевых и 2 белых шара. Сколько существует способов выбора 12 шаров из урны, если 1 выбранный шар — красный, количество выбранных зеленых шаров — четное, а количество оранжевых — нечетное? Учитывая, что хотя бы 1 выбранный шар должен быть красным, то могут быть выбраны 1, 2 или 3 таких шара, поэтому многочлен, представляющий красные шары, имеет вид х+х +х. Поскольку количество выбранных зеленых шаров четное, выбранными могут быть О, 2, 4, 6 или 8 таких шаров, поэтому многочлен, представляющий зеленые шары, имеет вид 1+х +х +х +х.
Количество выбранных оранжевых шаров должно быть нечетным, поэтому выбранными могут быть 1, 3, 5, 7 или 9 таких шаров, так что многочлен, представляющий оранжевые шары, имеет вид х+х +х +х +х. Следовательно, производящей функцией для рассматриваемой задачи будет (х+ хг + хз)(1+ г + а +,в +,з)(х+ хз + хз + хт + хэ)(1+ х+ хг), а ответ на вопрос даст коэффициент при х'г. 538 ГЛЯВА 13. Производящие функции Для нахождения коэффициентов некоторых полиномиальнык производящих функций введем в рассмотрение производящие функции из предыдущего раздела. ПРИМЕР 13.10. Найдем коэффициент при хз4 в разложении производящей функции (.з+,4+ з+ .а+...)4 (х +х +х +х + ° ) =(х ) (1+х+х +х +х + ) , 4 = (хга) ) — ) = по теореме 13.2 1,1 — х,~ — (х ) = (хга)(1+ 4х+ (з)х + + (4+„"')х" + ..) по теореме 13.2. Следовательно, чтобы найти коэффициент при х" в разложении этой производящей функции, необходимо найти коэффициент при х" га в разложении производящей функции 1+4х+ х + + х" + так что коэффициент при х" равен 4+т — 12 — 1 т — 9 а коэффициент при хз4 равен 24 — 12 12 ПРИМЕР 13.11.
Выясним, сколько существует способов выбора 12 объектов из совокупности объектов пяти типов, если необходимо выбрать не более 2 объектов первых трек типов и неограниченное количество объектов остальных двух типов. Производящая функция имеет вид (1+ х + х')'(1+ х + х' + х' + " )'. Но по теореме 13.3 (1+х+х) Поэтому заз (1+х+х ) (1+х+х +х + ) = — ) (1+х+х +х + ) 1,1 — х (1 х ) 1 (1 з)з 1 (1 з)з (1 — х)з (1 — х)а (1 — х)з (1 — х)з РАЗДЕЛ 13.З. Произеодяи4ие функции и комбинеторные подсчеты 539 Поскольку р .з)з 1 3 з+3 в з =1+бх+ х + + х" то, согласно правилу умножения полиномов, коэффициент при х'з в произведении Зхз+Зхв хэ) 1+5х+ ха+ + равен 5+12 — 1 5+9 — 1 5+5 — 1 5+3 — 1 ПРИМЕР 13.12.
Сколько существует способов выбора 20 объектов из множества объектов пяти типов, если количество выбранных объектов первого типа кратно 5, количество выбранных объектов второго типа кратно 3, объектов третьего типа следует выбрать не более 4, объектов четвертого типа — не менее 3, а объектов пятого типа — не более 2? Производяшая функция имеет вид (1+хз+хго+ И1+ з+хв+ )(1+х+ +х4)(хз+ 4+ И1+х+хз) и может быть представлена в виде выражения 1 1 — хв хз 1 — хз хз з 1 з 1 1 . 1 г1 .)з' исходя из этого, производящая функция имеет вид х' 1+Зх+ х + х +..
/7 — 11 20 Коэффициент при х' равен ~ ~, а коэффициент при хзо равен ~ ), П ~ -31' ПРИМЕР 13.13. Найдем производящую функцию, и-ый коэффициент которой дает количество неотрицательных целочисленных решений уравнения ег + 4ез + 5ез+ Зе4 = и, что эквивалентно нахождению количества способов выбора и объектов, когда объекты второго типа выбираются по 4 за один раз, объекты третьего типа выбираются по 5, а объекты четвертого типа выбираются по 3 за раз. Следовательно, производящая функция имеет вид (1 + х + х + .. )(1 + х + х + .. )(1 + х + х + )(1 + х + х + ), но это равно (1 — х)(1 — х4)(1 — хз)(1 — хз) 540 ГЛА8А 13. Производящие функции ° УПРАЖНЕНИЯ Найдите производящую функцию, в которой коэффициент при в' описывает количество решений уравнения а) е1 + ез + ез + е~ = т, где О < ез < 2 и О < ек < 4; б) ег + ез + ез = т, где 0 < е1 < 3 и ез четно; в) ег + ез + ез + еч = т, где ег нечетно, ез четно и ея > 4; г) ег + ез + ез + еа = т, где е, > г для всех й д) е1 + 2ез + Зез + 4ек — — т, Найдите производящую функцию, т-ый коэффициент которой дает количе- ство решений уравнения а) ег + ег + ез + ея = т, где е| > 2 и 0 < ез < 3: б) е1 + ез + ез = т, где О < е; < 3 для всех ю'; в) ег + ез + ез + ея = т, где ег нечетно, ез и ез четны и еа > 2; г) ег + ез + ез + ез = т, где е, > 3 для всех г; д) ег + 2ез + ез + 2еч = т.
Найдите производящую функцию, которую можно использовать для нахо- ждения количества способов выбора т элементов из 3. Найдите производящую функцию для определения количества способов со- ставить й центов, используя монеты стоимостью 1, 5, 10 и 25 центов. В маленьком городке 50 зарегистрированных избирателей, каждый из них либо голосует дважды, либо остается дома, за исключением мэра города, который голосует либо три раза, либо пять. Используя производящую функ- цию, определите, сколько существует способов собрать и голосов. а) 4 красных, 3 синих, 6 оранжевых и 2 зеленых шаров; б) 2 красных, 5 зеленых, 4 оранжевых и 3 зеленых шаров, если необходимо выбрать не менее 1 шара каждого цвета; в) 6 красных, 12 черных, 7 белых и 10 синих шаров, если необходимо выбрать не менее 4 черных шаров и четное количество синих шаров; г) 6 красных, 12 черных, 7 белых и 10 синих шаров, если необходимо выбрать не менее 1 шара каждого типа, четное количество красных шаров и нечетное количество белых шаров.
Найдите производящую функцию для нахождения количества способов выбора т элементов из а) 6 красных, 5 синих, 4 оранжевых и 3 зеленых шаров; б) 7 красных, 5 зеленых, 8 оранжевых и 4 белых шаров, если необходимо выбрать нечетное количество зеленых и красных шаров и четное количество оранжевых и белых шаров; в) 5 красных, 4 фиолетовых, 6 белых и 8 черных шаров, если необходимо выбрать не менее 2 черных шаров, 1 оранжевого, 3 красных и четное количество синих шаров; г) 9 красных, 7 черных, 6 белых и 11 синих шаров, если необходимо выбрать не менее 2 шаров каждого типа, нечетное количество красных шаров и нечетное количество белых шаров. РАЗДЕП 43.3.
Проиаводяигие функции и комбинаторные подсчеты 541 7. Для всех п ) 8, почтовое отправление стоимостью и центов оплачивается марками стоимостью 5 и 3 цента. Используйте производящую функцию для описания количества способов оплаты почтового отправления стоимостью к центов, используя исключительно марки по цене 5 и 3 центов. 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
