Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ѕерестановки з повторенн€ми




ѕоставимо таке питанн€. —к≥лькома способами можна розкласти множину ј, що складаЇтьс€ з n елемент≥в, на суму m п≥дмножин так, щоб , де Ч дан≥ числа ? ћножини не повинн≥ мати сп≥льних елемент≥в.

¬с≥ описан≥ вище розбитт€ множини ј на m груп можна д≥стати так: в≥зьмемо дов≥льну -елементну п≥дмножину ¬1, множини ј (це можна зробити способами); серед елемент≥в, що залишились, в≥зьмемо -елементну п≥дмножину (це можна зробити способами) ≥ т.д. «агальне число способ≥в вибору р≥зних множин за правилом множенн€ дор≥внюЇ

“≈ќ–≈ћј 1.8. „исло р≥зних перестановок, €к≥ можна утворити з n елемент≥в, серед €ких Ї елемент≥в першого типу, елемент≥в другого типу, Е, елемент≥в m- го типу, дор≥внюЇ

(1.6)

„исла називають пол≥номними коеф≥ц≥Їнтами.

1.4.5. ¬«ј™ћЌќ ќƒЌќ«Ќј„Ќј ¬≤ƒѕќ¬≤ƒЌ≤—“№.

ѕрипустимо, що задано дв≥ множини ј ≥ B. ¬важатимемо, що м≥ж цими множинами встановлено в≥дпов≥дн≥сть, €кщо кожному елементу а з ј в≥дпов≥даЇ де€кий елемент b з ¬ ≥ дл€ кожного елемента b з ¬ ≥снуЇ такий елемент а з ј, що b в≥дпов≥даЇ а. ÷€ в≥дпов≥дн≥сть буде взаЇмно однозначною, €кщо кожному елементу з ј в≥дпов≥даЇ лише один елемент з ¬ ≥ р≥зним елементам множини ј в≥дпов≥дають р≥зн≥ елементи ¬.

ѕриклад 1-17. ј Ч множина учн≥в класу, ¬ Ч множина парт, кожному учнев≥ в≥дпов≥даЇ парта, за €кою в≥н сидить (це не взаЇмно однозначна в≥дпов≥дн≥сть).
ѕриклад 1-18. ѕрикладом взаЇмно однозначноњ в≥дпов≥дност≥ може бути в≥дпов≥дн≥сть м≥ж елементами впор€дкованоњ множини з n елементами ≥ числами 1,2,...,n; кожному елементу в≥дпов≥даЇ його номер.

ћножини, дл€ €ких ≥снуЇ взаЇмно однозначна в≥дпов≥дн≥сть, називаютьс€ екв≥валентними.

“≈ќ–≈ћј 1.9. ƒл€ того, щоб дв≥ множини були екв≥валентними, необх≥дно ≥ достатньо, щоб вони мали однакову к≥льк≥сть елемент≥в.

ƒоведенн€. якщо множини ј ≥ ¬ мають однакову к≥льк≥сть елемент≥в n, то, впор€дковуючи кожну з них певним чином ≥ ставл€чи у в≥дпов≥дн≥сть k-му елементу множини k-й елемент множини , д≥станемо взаЇмно однозначну в≥дпов≥дн≥сть м≥ж множинами ј ≥ ¬, тобто ј \ ¬ екв≥валентн≥.

ѕрипустимо тепер, що ј маЇ n елемент≥в, ≥ ≥снуЇ взаЇмно однозначна в≥дпов≥дн≥сть м≥ж множинами ј ≥ ¬. ¬пор€дкуЇмо множину ј: нехай елементи ј Ч це ѕозначимо через той елемент B, €кий в≥дпов≥даЇ . ќск≥льки кожному елементу з ј в≥дпов≥даЇ елемент з B, р≥зним елементам ј в≥дпов≥дають р≥зн≥ елементи ¬ ≥ кожен елемент з ¬ в≥дпов≥даЇ де€кому елементу з A, то ¬ складаЇтьс€ з елемент≥в отже, ¬ маЇ n елемент≥в.

Ќј—Ћ≤ƒќ . якщо дв≥ множини екв≥валентн≥, то вони мають однакову к≥льк≥сть елемент≥в.

÷ю властив≥сть екв≥валентних множин дуже часто використовують дл€ обчисленн€ к≥лькост≥ елемент≥в р≥зних множин. ¬икористовуючи попередн≥й приклад, можемо сказати, що шукане число розм≥щень буде .

1.4.6.  ќћЅ≤Ќј÷≤ѓ « ѕќ¬“ќ–≈ЌЌяћ».

 омб≥нац≥€ми з m елемент≥в по n елемент≥в з повторенн€ми називаютьс€ групи, що м≥ст€ть n елемент≥в, причому кожен елемент належить до одного з m тип≥в.

ѕриклад 1-19. « трьох елемент≥в а, b, с можна утворити так≥ комб≥нац≥њ по два з повторенн€ми:

“≈ќ–≈ћј 1.10. „исло р≥зних комб≥нац≥й з m елемент≥в по n дор≥внюЇ

ƒоведенн€.  ожна комб≥нац≥€ повн≥стю визначаЇтьс€, €кщо вказати, ск≥льки елемент≥в кожного з m тип≥в в нењ входить. ѕоставимо у в≥дпов≥дн≥сть кожн≥й комб≥нац≥њ посл≥довн≥сть з нул≥в та одиниць, утворену за таким правилом: напишемо п≥др€д ст≥льки одиниць, ск≥льки елемент≥в першого типу входить в комб≥нац≥ю, дал≥ поставимо нуль ≥ п≥сл€ нього напишемо ст≥льки одиниць, ск≥льки елемент≥в другого типу м≥стить ц€ комб≥нац≥€, ≥ т. д. Ќаприклад, написаним вище комб≥нац≥€м з трьох по два будуть в≥дпов≥дати так≥ посл≥довност≥:

“аким чином, кожн≥й комб≥нац≥њ з m по n в≥дпов≥даЇ посл≥довн≥сть з n одиниць та mЧ1 нул≥в ≥, навпаки, за кожною такою посл≥довн≥стю однозначно в≥дновлюЇтьс€ така комб≥нац≥€. “ому число комб≥нац≥й з m по n з повторенн€ми дор≥внюЇ числу посл≥довностей з n одиниць та m Ч 1 нул≥в, тобто дор≥внюЇ .

ѕриклад 1-20.  ост≥ дом≥но можна розгл€дати €к комб≥нац≥њ з повторенн€ми по два з семи цифр 0, 1,2, 3, 4, 5, 6. „исло вс≥х таких комб≥нац≥й дор≥внюЇ

ѕриклад 1-21. —к≥льки ц≥лих нев≥д'Їмних розв'€зк≥в маЇ р≥вн€нн€

≤снуЇ т≥сний зв'€зок м≥ж розв'€зками вказаного р≥вн€нн€ та комб≥нац≥€ми з m елемент≥в по n. якщо маЇмо нев≥д'Їмн≥ ц≥л≥ числа так≥, що , то можемо утворити комб≥нац≥ю з m елемент≥в по n, вз€вши елемент≥в першого типу, Ч другого,..., Ч m -го типу. Ќавпаки, маючи комб≥нац≥ю з m елемент≥в по n, д≥станемо розв'€зок р≥вн€нн€ ( елемент≥в першого типу, Ч другого,..., Ч m -го типу) в ц≥лих нев≥д'Їмних числах. ќтже, м≥ж множиною вс≥х комб≥нац≥й з m елемент≥в по n з повторенн€ми та множиною вс≥х нев≥д'Їмних ц≥лих розв'€зк≥в р≥вн€нн€ встановлюЇтьс€ взаЇмно однозначна в≥дпов≥дн≥сть. “ому число розв'€зк≥в дор≥внюЇ .

1.4.7. Ѕ≤Ќќћ Ќ№ё“ќЌј.

¬≥домо, що

(1.7)

як розкрити дужки при обчисленн≥ виразу ? ¬≥дпов≥дь на це питанн€ даЇ така теорема.

“≈ќ–≈ћј 1.11. ћаЇ м≥сце р≥вн≥сть:

(1.8)

÷ю теорему ≥нод≥ називають б≥номною теоремою, а числа б≥номними коеф≥ц≥Їнтами. –≥вн≥сть (1.8) називають часто б≥номом Ќьютона, причому ц€ назва з точки зору ≥стор≥њ не Ї справедливою, бо формулу дл€ знали ще середньоаз≥атськ≥ математики ќмар ’ай€м, √≥€сед≥н. ¬ «ах≥дн≥й ™вроп≥ до Ќьютона њњ знав ѕаскаль (1623Ч1662). «аслуга Ќьютона в тому, що в≥н узагальнив формулу (1) дл€ нец≥лого показника n. ЌагадаЇмо, що Ї число k-елементних п≥дмножин у множин≥ з n елемент≥в. ‘ормулу (1) можна записати у вигл€д≥:

ƒоведенн€. ѕеремножимо посл≥довно раз. “од≥ одержимо суму 2n доданк≥в виду де () дор≥внюЇ або a, або b. –оз≥б'Їмо вс≥ доданки на (n + 1) групу в≥дн≥сши до вс≥ т≥ доданки, в €ких b зустр≥чаЇтьс€ множником k раз, а a Ч (n-k), раз. „исло доданк≥в у дор≥внюЇ, очевидно, (таким числом способ≥в серед n множник≥в можна вибрати k множник≥в, €к≥ дор≥внюватимуть b), а кожен доданок в дор≥внюЇ . “ому

“еорему доведено.

ЌагадаЇмо таку важливу властив≥сть б≥номних коеф≥ц≥Їнт≥в

, (1.9)

–≥вн≥сть (2) показуЇ, що б≥номн≥ коеф≥ц≥Їнти можна посл≥довно виписувати у вигл€д≥ трикутноњ таблиц≥, €ка називаЇтьс€ трикутником ѕаскал€:

¬ n-му р€дку трикутника ѕаскал€ сто€ть коеф≥ц≥Їнти розкладу , причому кожен коеф≥ц≥Їнт, кр≥м крайн≥х двох, €к≥ дор≥внюють √, дор≥внюЇ сум≥ в≥дпов≥дних коеф≥ц≥Їнт≥в з попереднього р€дка.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-02-12; ћы поможем в написании ваших работ!; просмотров: 669 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќеосмысленна€ жизнь не стоит того, чтобы жить. © —ократ
==> читать все изречени€...

523 - | 458 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.013 с.