В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 29
Текст из файла (страница 29)
Нетрудно видеть, что указанное соответствне являсгс» взаимно однозначным, откуда н следует справедлнвосгь доказываемого утверждения. Теперь для определенна кол«честна целочнсленных решений системы (Э.1) сделаем замену переменных. Пусть н =«;-ог. Тогда хг=иг+се, а следовательно, нз (3.!) получаем ь', +и +...+и =г — 2 аг, и~~О, 1=1, 2... и, (3.2) т. е.
мы свелн «сходную задачу к уже рассмотренному случаю (понятно, гю количество целочясленкык решений систем (3.1) Я (3.2] совпадает). Но тогда, вспольауя доказанное ранее утверждение, получаем, что «олнчество целочисленных решюшй сястемы (3.!) (нлн (3.2)) в случае г~ 2 ог равно ! (362 +г-Х М-1 га гай Есхи же г с Х аг, то множество целочисленных решений системы (9.1) является пустым, и количество решений в атом случае равно О. ЗЛ.З. Разбиения Подсчитаем число разбиений конечного множества Х, где (Х( =л, иа й подмножеств Хь Хм ..., Хз (3~1) таина, что каждое Хг содержит л, злеменгов, т. е.
ь Ц Хг=Х, Хб)Хг=Я прн (чь), (Хг(=пг, г=1, 2, ..., й. (ЗД) г Очевидно, что прп зтам Х л,=л. Отметим, что для некоторых номеров ( возможно Хг=(3(. Число указанных разбиений нри фиксированных л, обозначим через С "' "» "" . Загюмгппз 3.2. В данном случае набор подмножеств множества Х з разбиении является угюрядоченкым [т. е. Хь ..., Хь— упорядоченная последовательность множеств). Ниже, кроме тонг, рассматривается случай, когда набор подмножеств в разбиении не является уяорядочениым. Утверждение 3.7. С иь "" ч" = М,.
ь! Как отмечалось ранее, иаждое из множеств Хг можно рассматривать как сочетание без повторений. Предварительно докажем справедливость формулм Действительно, для образования сочетания,охпветствуюшего множеству Хь могут быть использованы все элементы множества Х. т, е. множество Х, может быть выбрано Сш сносе. бами.
После выбора Хг множество Х, может быть выбрано способами (так каи Х, является подмножеством множества Х'ьуг и (ХЧХ~( =я †,), и длп любого 1, где 2 С(~й, после выбора множеств Хь ... Хг г множество Хг может быш выбрано С»„', „,, способами. Но тогдапоправнлупронз. ведения выбор упорядоченной псследовательностимножествХь .... Хь удовлетворяющих (ЗА), можно осуществить Сш С"* м-чг — Са — л,—..
я„способами, т. е формула (33) доиазанз. Исяользуя теперь формулу (3.5), а также утверждение 3.3 в производя иеобводимые сокрашения, гюлучаем, что доказывае мое утверждение оправелливгь шв з, ., з з реизмдгине а.а. Число С "''' ' *,гхв кгжц П з, и,яезно юг ! лг (З, л)-дазмзмгмм г иоззшммкзк еред» шемааве шозим годггзкасн а, шглангав Гео пож е згемешюв З.зо гзза з т. д., л злезваоа Лчо ша3. Каждому размещению указанного типа поставим в соотвег стеке разбиение множества Х (1, 2, ...„л) номеров элемеитов в выборке иа подмножества Хь ..., Хь где Хг — множество но.
мероэ элементов 1-го типа в выборке. Очевидно, что при етом выполняется (3.4). Указанное соответствие ыежду размещекия. ми заданного типа и разбиеииями, удовлетворяющими (3.4), язлиется взаимно одказиачкым, откуда в силу утперждеиня 8.7 и вытекает справедливость доказываемого утверждения. Пример 3.9. В студенческой группе, состопщей из 25 человек, лрп выборе профорга за аыдзииугую каидидатуру проголосовали 12 челоаек, против — !О, воздержались — 3. Сколькимп скособами могло быть проведено такое голосоаакиез Пусть Х вЂ” мкожестзо студентов в группе, Х~ — множество студентов, проголосовавших за выдвинутую капдиааттру, Х,— множество студентов, ароголосозавших против, Хз — множество студентов, воздержавшихся от голосования. Тогда )Х( =25, (Х~(=12. )Хз(=10, )Хз)=3, Х=Х~ЦХз()Хз, Хг()Хт=(с! прп зчь1, а слеаоввтелько, искомое число равно Сзз" "*.
Используя утаерждеипе 3.7, получаем Сззы. ~з, з ' 1437285800 !тцп!з Пример 310. Сколькими способами можно раскрасить квадрат, разделепиый нв девять частей (рис. 3.2), четырьмя шмтамк таким образом, чтобы в первый цвет били опрашеиы 3 части, зо второй — 2, е третий — 3, в четаертмй — !з Пусть Х вЂ” множество дистов, тле у 2 у )х) 4. тогда каждое раскрашпзанке, Рассматриааемое как последовательность Пестов, в которые окрашиваются пронумерованные части квадрата, валяется Упорядоченной выборкой с повторения- у ми объема 9 из мпожестиа Х, т. е.
(4.9)- Размещением с повтореииями. При этом иас интересуют размезцеиия с заданной «омбияацией элемепмш,(3 элемеата— первый пает, 2 — второй, 3 третий, ! — лешертмй). Но тогда, иопользуя утшрждепие 3.8, получаем, что искомое число Равпо Сзк * х '= — =5040. з, з. 3!з!Згп Подсчатзем тепрь смаками еккоезмн комю рззошь икомм о !Зг х, гве !х(=н, не нолнножестве, стел» в юрых дв» «в»шоо 1 1в д .„ имеется ш, ш О поды» жесте с 1 элементами, ои Х гтв л.
Пзн стоп в отлн ве от рвссмотрвнного ренее онуче» в нашем случае н Гор но»мне. жесте в резо»сиен не явшш ся взор»леченным (т. е. нотялок подмножеств в резоне»ни «е вшжешн сгшеотвееныы), Твк, нвпрвмер, ревбненн» швжп- ство Х (!,да,4,5) внлэ (Щ, (4), (2,5); (4), (2 5), (1,3); (З,о), (4), (1,3) счете»лев олн»в»овин». Обоэнечвы число уквзевныв негногвлоченныв рвз.
бневна множества Х через Л(т, ..., т ), Утверждение 3.9. Ф(ть . о т ) = жб...в~ 1(10 ' ... (»0 Заметим, что каждое пз неупорядоченных разбиений, рнс. смотренных прн определении вел»чины дг(шь ..., ш ), можно, нумеруя множества в этом разбиении, привести т,(,.,пы! спосо- бамн к упорядоченным разбиениям вваа Хь...,Х,Х„,+,,...,Х,+„,,...,Х,+ +ш,+, ..., Х,+ +, (3.6) где (Хв) =...=)Х,) =1, )Х,+1 ) =...=)Х,+, ) 2,...
..., )Хш+ + „,+, ,'=.=)Х,+ +,)=. 137) При этом объединение получаемых таким образом попарно непсресекаюшихсв множеств разбиеивй вида (З.б), (3.7) для всех рассматриваемых неупорядоченных разбиений, очевидно, даст совонунносгь всех разбиений вида (3.5), (3.7), а следоввтеаьно, ыо правилу суммы, используя утверждение 3.7, имеем =Зтвй..ш 1=(У(шь, т )пи!дш! 00 ' ...(лО (где суммирование производится по всем рассматриваемым неупорядочснныы разбиениям), откуда н следует справедливость доказываемого утверждения.
Пример ЗЛ 1. Сколькимн способами иэ группы в 25 человек можно сформировать 5 коалиций по 5 человеко Пусть Х вЂ” множество людей а группе, т! — число кбашпшй по ! человек, где 1=1, 2,... 25. Тогда по условиям задачи ) Х) =25, еле=5, пи О, (ш(1, 2, ..., 25)в(5), в следовательно, искомое число будет равно й((0, О, О, О, 5.
О, ..., 0), где в силу утверждении 3.9 Д((0, О, О, О, 5, О, ..., 0) тм эбз б1(бб (ы) Пример 3.12. Сколькими способамн можно задать отношение вквивалентности на множестве Х=(1, 2, ..., 25) с тремя классами эквивалентности? 1бб Исгцаьзу м фаь . «гс»вацвв вю е 9 е рвйе «ем ююк за Х авуч е», пе с«мсе ч о мри»«е а фсрву. з«д Х я(вь..., ) в + 2в + ... + 2Ы» Уб в+в+...+ а Х ,+2 .+... +Ив -ж 1" *188 '" (2 В " в, + в + ... + ь, 3 ом юд,+2а ч-...
+ю „-28,, +«ьа ... + ю,-а в в»юо р а па ур а ц р цзге » ч««* («р«ер. в, 1,,*-2, в, о, 1«ь1,1»ьж — вав»з у а) 3.1.8. Полнномиальмаа формула Овуеаали» внффац«мп с в фср у«е в+ ... + ь в юс ю аа. гле су» р«щв«з вил *»се р ше»ю урз«. «вв» «,+ ... +а, ю«п врвмт «ь .п ч»». УчасРжлеине 818. с С «""'ью Вводам обозна»сная для сомножителеб в (к +..,+кь)Д Обозначим а;= (х,+., +х„), 1=1, 3....ж Тогда (к,+...+ка)"=аь.. ...а . Пусгь А=-(аь ..., а„), Пересчитаем юе одначлены.
полученные в результате перемножения аь..а, в цоторых к, встречается л, раз, кз — л, раз н г. д., хь — в» раз, г. с. одночлены вида х,« ...х«ю. где в+...+»в=в (3.8) Рв р юкюа ю г»мг» а«авве«са Л ««»вага 1 (1, 2,..., 18 пь»юч р» А А «сч. ав и« е«алу «ег е» е», ю гв в,ю с» п «кве а, мичрмс юреч м» А,. 2« а й и вс «««ченцгс «ю св пп«чг у«зб»«вм (А 1 л„г 1,..., Д НА А.
А НА» ж р«1Ю~:, (Зл) Поннтно, что указанное жюгаегсгвие между олночленвмн (3.8) и разбиевнвмн вила (3.9) явлются взаимно одиозяачнын. Р)о тогда св «„(воли»ее»за одночлевов вида (3.8)) Равно „«„а1 1за Пример 3.13. Определим коэффициент с в олночлене гх,зк,'х,' многачлева (с приведенными подобнымн членами), получаемого нз вмражения (х«+хв+к,)'з. В силу угверждеззия 3.10 имеем с=С " ' — =ЕЗ)0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
