Пермутация срещу комбинация: Каква е разликата между формулата за пермутация и формулата за комбинация?

Ето кратката версия.

Да вземем за пример биещи камбани в църква.

Пермутацията е подреждане на камбаните. Измисляте най-добрата поръчка да ги позвъните.

Комбинацията е изборът на камбани. Вие избирате камбаните да звънят. Ако имате твърде много камбани, първо трябва да ги изберете и след това да помислите за тяхната поръчка.

Това поражда познатата идентичност: (n P r) = (n C r) * r!

Начинът да поръчате rартикули от, nе първо да изберете rартикули от nи след това да поръчате rартикулите ( r!)

И това означава (n P r) = n! / (n-r)!и(n C r) = n! / ( (n-r)! * r! )

Но искате ли да знаете как да запомните това завинаги?

Аз съм голям фен на първоначалното мислене. За да разберете даден проблем, стигнете до същността му и разсъждавайте нагоре.

Това, което не се прави обикновено е причина за объркване: ако не разбирам как работят нещата, не знам къде да закача концепциите. Моята ментална рамка не е пълна, затова решавам просто да я запомня.

Както можете да си представите, това не е идеално. И така, от време на време се отдавам на упражнение за извличане на нещата от източника и изграждане на интуиция за това как работят нещата.

Този път изграждаме интуиция за пермутации и комбинации.

Например, знаете ли защо формулата за комбинация е (n C r)? Откъде дойде това? И защо тук се използват факториали?

Нека започнем от източника. Фактори, пермутации и комбинации са родени от математиците, които играят заедно, подобно на това как Стив Джобс и Стив Возняк основават Apple, играейки заедно в техния гараж.

Подобно на това как Apple се превърна в пълноценна печеливша компания, простият факториал се !превърна в атом на цяла област на математиката: комбинаторика.

Забравете всичко, нека започнем да мислим отдолу нагоре.

Първият известен интересен случай на употреба идва от църквите през 17 век.

Чудили ли сте се как бият камбаните в църквите? Има машина, която ги „звъни“ в ред. Преминахме към машини, защото камбаните са твърде големи. Също така има тонове камбани.

Как хората измислиха най-добрата последователност, в която да ги позвънят? Ами ако искат да сменят нещата? Как биха могли да намерят най-добрия звук? Всяка камбанария имаше до 16 камбани!

Не можехте да промените колко бързо бихте могли да звъните - машините биеха само по един звънец всяка секунда. Единственото нещо, което можете да направите, е да промените реда на камбаните. И така, това предизвикателство беше свързано с намирането на най-добрия ред.

Бихме ли могли по пътя да разберем и всички възможни поръчки? Искаме да знаем всички възможни поръчки, за да разберем дали си струва да ги изпробваме всички.

Звънец, Фабиан Стедман прие това предизвикателство.

Започна с 2 камбани. Какви са различните поръчки, в които той би могъл да бие тези камбани? [1]

1 и 2.

или

2 и 1.

Това имаше смисъл. Нямаше друг начин.

Какво ще кажете за 3 камбани?

1, 2 и 3.

1, 3 и 2.

След това започвайки с втората камбана,

2, 1 и 3.

2, 3 и 1.

След това започвайки с третата камбана,

3, 1 и 2.

3, 2 и 1.

Общо, 6.

Тогава той осъзна, че това е много подобно на две камбани!

Ако той фиксира първата камбана, тогава броят на начините да се поръчат останалите две камбани винаги е бил два.

По колко начина би могъл да поправи първата камбана? Всяка от 3-те камбани може да е тази!

Добре, продължи той. След това стигна до 5 камбани.

Това е, когато той осъзнава, че да правиш нещата на ръка е тромаво. Имате само толкова много време през деня, трябва да биете камбани, не можете да останете да изтегляте всички възможни камбани. Имаше ли начин да разбера бързо това?

Той се върна към прозрението си.

Ако имаше 5 камбани и той оправи първата камбана, всичко, което трябваше да направи, беше да измисли как да поръча 4 камбани.

За 4 камбани? Е, ако имаше 4 камбани и той поправи първата камбана, всичко, което трябваше да направи, беше да измисли как да поръча 3 камбани.

И той знаеше как да направи това!

И така, поръчка на 5 камбани = 5 * поръчка на 4 камбани.

Поръчка на 4 камбани = 4 * поръчка на 3 камбани

Поръчка на 3 камбани = 3 * поръчка на 2 камбани.

.. Виждате модела, нали?

Забавен факт: Това е ключът към техниката на програмиране, наречена рекурсия.

Той също го направи. Въпреки това му отне много повече време, тъй като никой от него вече не беше открил това. [2]

По този начин той разбра, че подреждането на 5 камбани = 5 * 4 * 3 * 2 * 1.

Тази формула за подреждане през 1808 г. стана известна като факториал.

Мислим за факториалната нотация като основа, но идеята е съществувала много преди тя да има име. Едва когато френският математик Кристиан Крамп забеляза, че се използва на няколко места, той го нарече факториал.

Това подреждане на камбани се нарича пермутация.

Пермутацията е подреждане на елементи.

Когато уча нещо, мисля, че помага да се разглеждат нещата от всеки различен ъгъл, да се затвърди разбирането.

Ами ако се опитаме директно да извлечем горната формула, без да се опитваме да намалим проблема до по-малък брой камбани?

Имаме 5 интервала, нали?

Колко начина можем да изберем първата камбана? 5, защото това е броят на камбаните, които имаме.

Втората камбана? Е, използвахме една камбана, когато я поставихме на първо място, така че остават 4 камбани.

Третата камбана? Е, ние избрахме първите две, така че остават само 3 камбани, от които да избирате.

Четвъртата камбана? Остават само 2 камбани, така че 2 варианта.

Петата камбана? Остава само 1, така че 1 вариант.

И там го имаме, общият брой поръчки е 5 * 4 * 3 * 2 * 1

По този начин имаме първата си обща формула.

Броят на начините за поръчка на Nартикули еN!

Пермутацията

Сега сме изправени пред различен проблем. Царят заповяда да се направят нови камбани за всяка църква. Някои са приятни, други са добре, други ще ви направят глухи. Но всеки е уникален. Всеки издава свой собствен звук. Оглушителна камбана, заобиколена от хубави камбани, може да звучи величествено.

Но нашата камбанария все още държи 5 камбани, така че трябва да намерим най-добрата поръчка от 8 камбани, които квалифицираните производители на камбани направиха.

Използвайки горната логика, можем да продължим.

За първата камбана можем да изберем някоя от 8-те камбани.

За втората камбана можем да изберем някоя от останалите 7 камбани ... и така нататък.

В крайна сметка получаваме 8 * 7 * 6 * 5 * 4възможни поръчки от 8 камбани в 5 пространства.

Ако сте запознати с версията на формулата на (n P r), която е n! / (n-r)!, не се притеснявайте, ще извлечем и това достатъчно скоро!

Един лош начин да се извлече е умножаването на числителя и знаменателя по 3! в нашия пример по-горе -

получаваме 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1= 8! / 3!.

Но това не ни помага да разберем защо тази формула работи. Преди да стигнем там, нека да разгледаме избора на неща или комбинацията.

Комбинацията

Сега, когато знаем как да поръчваме нещата, можем да разберем как да изберем нещата!

Нека разгледаме същия проблем. Има камбанария с 5 камбани, а вие имате 8 камбани. В момента обаче не искате да разберете реда на камбаните (не забравяйте, че това е пермутация).

Вместо това искате да изберете 5-те най-добри камбани и да оставите някой друг с по-добър музикален вкус да разбере поръчката. Всъщност разбиваме проблема на части: Първо, измисляме кои камбани да изберем. След това измисляме как да поръчаме избраните камбани.

Как избирате камбаните? Това е "комбинацията" от пермутации и комбинация.

Комбинацията е селекция. Вие сте избирателни. Избирате 5 камбани от 8, които са изработили вашите майстори.

Тъй като знаем как да поръчваме камбани, ще използваме тази информация, за да разберем как да изберем камбани. Звучи невъзможно? Изчакайте, докато видите красивата математика.

Нека си представим, че всички камбани са в една линия.

Преди да намерим всички начини за избор на камбани, нека се съсредоточим върху един начин за избор на камбани.

Единият начин е да изберете произволно 5. Това не ни помага много да разрешим проблема, така че нека опитаме по друг начин.

Поставяме камбаните в една линия и избираме първите 5. Това е един от начините да изберете камбаните.

Забележете, че дори да сменим позициите на първите 5 камбани, изборът не се променя. Те все още са един и същ начин да изберат 5 уникални камбани.

Това важи и за последните три камбани.

Сега, красивият математически трик - за този един начин да изберем 5 камбани, какви са всички подреждания на 8 камбани, където избираме точно тези 5 камбани? От изображението по-горе това са всички подреждания на 5 камбани ( 5!) и всички подреждания на останалите три камбани ( 3!).

По този начин, за всеки един начин за избор на 5 камбани, имаме ( 5! * 3!) поръчки от 8 камбани.

Какви са общите възможни поръчки на 8 камбани? 8!.

Не забравяйте, че за всеки избор от първите 5 камбани имаме ( 5! * 3!) поръчки от 8 камбани, които дават същия избор.

След това, ако умножим броя на начините за избор на първите 5 камбани с всички възможни поръчки от един избор, трябва да получим общия брой поръчки.

Ways to choose 5 bells * orderings of one choice = Total orderings 

Така,

Ways to choose 5 bells = the total possible orderings / total orderings of one choice. 

В математиката това става:

(8 C 5) = 8! / ( 5! * 3!) 

Ето и ето, намерихме интуитивно обяснение как да изберем 5 неща от 8.

Сега можем да обобщим това. Ако имаме N неща и искаме да изберем R от тях, това означава, че чертаем линия в R.

Което означава, че останалите елементи ще бъдат N-R. И така, за един избор на Rартикули имаме R! * (N-R)!поръчки, които дават едни и същи Rартикули.

RИмаме N! / (R! * (N-R)!)възможности за всички начини за избор на артикули .

Броят на начините за избор на rартикули от nе(n C r) = n! / (r! * (n-r)!)

В разговорно изражение също се произнася (n C r) n choose r, което помага да се затвърди идеята, че комбинациите са за избор на предмети.

Пермутацията - преразгледана

С направената и обезпрашена комбинация, нека се върнем към Част 2 от нашата работа. Нашият скъп приятел избра най-добрите 5 камбани, като измисли всички възможни комбинации от 5 камбани.

Нашата работа сега е да намерим перфектната мелодия, като измислим броя на поръчките.

Но това е лесното. Вече знаем как да поръчаме 5 артикула. Това е 5!и готово.

Така че, за да пермутираме (поръчаме) 5 елемента от 8, първо избираме 5 елемента, след което поръчваме 5 елемента.

С други думи,

(8 P 5) = (8 C 5) * 5! 

И ако разширим формулата, (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!.

И стигнахме до пълния кръг до нашата оригинална формула, изведена правилно.

Броят на начините за поръчване на rартикули от nе(n P r) = n! / (n-r)!

Разлика между пермутация и комбинация

Надявам се това да направи кристално ясна разликата между пермутации и комбинации.

Пермутациите са подреждания, докато комбинациите са избор.

За да поръчаме N елемента, намерихме два интуитивни начина да разберем отговора. И двете водят до отговора N!,.

За да пермутирате 5 от 8 елемента, първо трябва да изберете 5 елемента, след което да ги подредите. Вие избирате да използвате (8 C 5), след което поръчате 5, като използвате 5!.

А интуицията за избора Rот Nсе разберете всички подредбите ( N!) и се дели на подредбите, където първият Rи последният N-Rостане същият ( R!и (N-R)!).

И това е всичко, което има за пермутации и комбинации.

Всяка разширена пермутация и комбинация използва това като основа. Комбинация с подмяна? Същата идея. Пермутация с идентични елементи? Същата идея, само броят на поръчките се променя, тъй като някои артикули са идентични.

Ако се интересувате, можем да разгледаме сложните случаи в друг пример. Кажете ми в Twitter.

Разгледайте още публикации в моя блог и се присъединете към седмичния пощенски списък.

Крайни бележки

  1. Ето как си представям, че е разбрал нещата. Не го приемайте като урок по история.
  2. През 12 век индианците са имали 400 години преди него.