Riaghailtean Permutation agus Measgachaidh
Ann am matamataig, gu h-àraidh ann an raointean coltachd agus staitistig, bidh sinn tric a’ tighinn tarsainn air a’ cheist “cia mheud dòigh” anns am faod tachartas tachairt. Mar eisimpleir: cia mheud suidheachadh suidhe a dh’ fhaodadh a bhith ann airson àireamh shònraichte de dhaoine? Cia mheud dòigh as urrainnear buill sgioba a thaghadh bho bhuidheann de dh’ oileanaich? Tha ceistean mar seo air am freagairt le bhith a’ cleachdadh riaghailtean permutation agus cothlamadh, dà bhun-bheachd chudromach ann an riaghailtean cunntaidh. Ged a tha an dà chuid a’ dèiligeadh ri “àireamh nan dòighean,” tha am prìomh eadar-dhealachadh na laighe anns an tèid òrdugh a thoirt fa-near.
1. Bun-bheachd Riaghailtean Àireamhachd
Mus tèid sinn a-steach do cho-mheasgachaidhean agus measgachaidhean, tha beachd bunaiteach ri thuigsinn: is e àireamhachadh am pròiseas a bhith a’ cunntadh an àireamh de thoraidhean a dh’ fhaodadh a bhith ann bho sheata sònraichte de shuidheachaidhean. Faodar àireamhachadh a dhèanamh le làimh airson cùisean beaga, ach airson cùisean nas motha, feumaidh sinn foirmle èifeachdach.
Is iad seo an dà phrionnsabal bhunasach ann an àireamhachadh:
1. Riaghailt an Toraidh
Ma tha grunn ìrean ann am pròiseas, agus ma tha grunn roghainnean aig gach ìre, is e an àireamh iomlan de dhòighean toradh an àireamh roghainnean aig gach ìre.
2. Riaghailt na Suim
Ma ghabhas roghainn a dhèanamh ann an grunn dhòighean a tha a’ cur às dha chèile (gun a bhith a’ dol thairis air a chèile), is e suim nan dòighean sin an àireamh iomlan de dhòighean.
Tha permutations agus measgachaidhean nan tagraidhean eile den phrionnsapal seo, gu h-àraidh nuair a thòisicheas nithean air an rèiteachadh no air an taghadh.
2. Iomlaid: Rèiteachadh le bhith a’ toirt aire do òrdugh
'S e dòigh air nithean a chur air dòigh no a thaghadh far a bheil an òrdugh cudromach a th' ann an permutation. Tha seo a' ciallachadh gu bheil an rèiteachadh AB eadar-dhealaichte bho BA.
a. Iomlaidean de n nithean eadar-dhealaichte (uile air an cur ann an òrdugh)
Ma tha n nithean eadar-dhealaichte ri chur air dòigh uile ann an sreath, is e seo an àireamh de rèiteachaidhean:
\[
n! = n uair (n-1) uair (n-2) uair 2 uair 1
\]
Canar factarail ris an t-soidhne “!”.
Contoh:
Tha 4 leabhraichean eadar-dhealaichte ann. Cia mheud dòigh as urrainnear an cur air sgeilp?
\[
4! = 4 \uairean 3 \uairean 2 \uairean 1 = 24
\]
Mar sin tha 24 rèiteachaidhean ann.
b. Pàirt-atharrachadh: a’ taghadh r bho n (thathar a’ toirt aire don òrdugh)
Ma thaghas sinn r nithean bho n nithean eadar-dhealaichte airson an cur air dòigh (chan eil iad uile gu riatanach), is e seo am foirmle permutation:
\[
P(n,r) = \frac{n!}{(nr)!}
\]
Contoh:
De na 6 oileanaich, thèid 3 oileanaich a thaghadh airson a bhith nan cathraiche, nan iar-chathraiche, agus nan rùnaire. Dè an iomadh dòigh anns an gabh seo a dhèanamh?
Leis gu bheil cathraiche-iar-rùnaire nan dreuchdan eadar-dhealaichte, tha an òrdugh cudromach.
\[
P(6,3) = \frac{6!}{(6-3)!} = \frac{6!}{3!} = 6 × 5 × 4 = 120
\]
Tha 120 dòigh ann.
c. Ath-aithris leis an aon nì (ath-aithris/co-ionann)
Uaireannan bidh nithean ann nach eil uile gun samhail. Mar eisimpleir, anns an fhacal "OIDHCHE" tha dà M agus dà A ann (no airson "OIDHCHE": tha 2 M ann, tha 2 A ann? Gu dearbh, "OIDHCHE" = OIDHCHE: M=2, A=2, L=1). Tha an àireamh de rèiteachaidhean eadar-dhealaichte air a thomhas le:
\[
\frac{n!}{n_1! \, n_2! \, \dotagan}
\]
far a bheil \(n\) an àireamh iomlan de nithean, agus \(n_1, n_2\) an àireamh de nithean co-ionann.
Contoh:
Cia mheud rèiteachadh eadar-dhealaichte a tha ann de na litrichean ann an “OIDHCHE”?
Àireamh litrichean \(n=5\), tha 2 aig M, tha 2 aig A, tha 1 aig L.
\[
\frac{5!}{2!\,2!} = \frac{120}{4} = 30
\]
Mar sin tha 30 rèiteachadh eadar-dhealaichte ann.
3. Measgachadh: Taghadh gun aire a thoirt don òrdugh
'S e dòigh a th' ann an cothlamadh nithean a thaghadh far nach eil an òrdugh cudromach. Tha taghadh A agus B mar an ceudna ri taghadh B agus A.
Bidh am foirmle cothlamadh a’ taghadh r bho n nithean:
\[
C(n,r) = \binom{n}{r} = \frac{n!}{r!(nr)!}
\]
a. Eisimpleir de chothlamadh sìmplidh
Contoh:
A-mach à 10 oileanaich, thèid 3 oileanaich a thaghadh airson a bhith nam buill den sgioba farpais (gun dreuchdan sònraichte). Dè an diofar dhòighean?
Leis nach eil rangan ann, chan eil an òrdugh cudromach.
\[
C(10,3) = \frac{10!}{3!\,7!} = \frac{10 × 9 × 8}{3 × 2 × 1} = 120
\]
Tha 120 dòigh ann.
b. Ceangal eadar permutations agus measgachaidhean
Thoir an aire gu bheil co-thuiteamas agus measgachadh co-cheangailte. Gus daoine r a thaghadh agus an cur ann an òrdugh, is urrainn dhuinn:
– tagh r daoine an toiseach: \(C(n,r)\)
– cuir air dòigh an neach sin: \(r!\)
Mar sin:
\[
P(n,r) = C(n,r) uair r!
\]
Tha seo a’ sealltainn gu bheil am permutation “nas motha” oir tha e a’ dèanamh eadar-dhealachadh air an òrdugh.
4. Mar a nì thu co-dhùnadh: Cleachd measgachadh no measgachadh?
Gus fuasgladh fhaighinn air duilgheadas, is e an ceum as cudromaiche aithneachadh a bheil an òrdugh air a ghabhail a-steach.
Cleachd permutations ma tha:
– tha dreuchd no tiotal ann (cathraiche, leas-chathraiche, 1-2-3mh àite),
- tha suidheachadh suidheachain ann,
– tha còd no sreath rèiteachaidh ann.
Cleachd measgachadh ma tha:
– dìreach buill buidhne taghte,
– chan eil òrdugh a’ dèanamh eadar-dhealachadh air na toraidhean,
– is e a tha cudromach cò a thèid a thaghadh, chan e an suidheachadh aca.
Eisimpleir luath:
– Tagh 5 a-mach à 12 neach airson a bhith air a’ chomataidh: measgachadh
– A’ dearbhadh buannaichean a’ chiad, an dàrna agus an treas àite a-mach à 12 com-pàirtiche: measgachadh
5. Eisimpleirean de Thagraidhean ann am Beatha Làitheil
Chan ann a-mhàin ann an leabhraichean matamataig a nochdas measgachadh agus measgachadh, ach ann an suidheachaidhean fìor cuideachd:
1. Tèarainteachd facal-faire (facal-faire/PIN)
Is e 104 an àireamh de PINan 4-dhigitach (0–9) a dh’ fhaodadh a bhith ann le ath-aithris. Tha seo co-cheangailte ris an riaghailt iomadachaidh agus a’ bheachd air atharrachaidhean le ath-aithris.
2. A’ cur clàran-ama no suidheachain air dòigh
A’ dearbhadh suidheachaidhean suidheachain ann an tachartasan foirmeil a’ cleachdadh atharrachaidhean mar thoradh air diofar shuidheachaidhean.
3. Taghadh sgioba no comataidh
'S e measgachadh a th' ann a bhith a' taghadh grunn dhaoine bho bhuidheann, oir chan eil an òrdugh cudromach.
4. Geamannan cairt
Bithear tric a’ cleachdadh measgachaidhean gus coltachd làmh sònraichte ann am poker no geamannan eile obrachadh a-mach.
6. Mearachdan Cumanta ri Sheachnadh
Seo cuid de mhearachdan a bhios tric a’ tachairt nuair a thathar ag obair air duilgheadasan permutation agus cothlamadh:
– A’ meas an òrdugh mar neo-chudromach ged a tha e cudromach, mar eisimpleir a’ taghadh a’ chathraiche agus an iar-chathraiche (bu chòir dha a bhith na mheasgachadh).
– A’ dìochuimhneachadh nithean co-ionann a roinn, leithid faclan a chur ri chèile anns a bheil litrichean a-rithist is a-rithist.
– Mearachd-àireamhachadh fhactaraidhean, gu h-àraidh nuair a thathar a’ sìmpleachadh an riochd \(\frac{n!}{(nr)!}\).
Is e aon dhòigh air seo a sheachnadh mìneachadh na ceiste a sgrìobhadh ann an seantansan sìmplidh: “An tagh mi no an cuir mi air dòigh?” agus “A bheil suidheachadh a’ dèanamh diofar anns a’ thoradh?”
Penutup
Tha riaghailtean an iom-fhillteachaidh agus an cothlamadh nan innealan riatanach airson àireamh nan cothroman ann an diofar shuidheachaidhean obrachadh a-mach. Bithear a’ cleachdadh iom-fhillteachaidhean nuair a tha òrdugh no suidheachadh cudromach, agus bithear a’ cleachdadh measgachaidhean nuair nach eil òrdugh cudromach. Le bhith a’ tuigsinn an eadar-dhealachaidh seo, a’ maighstireachd factaran, agus a’ cur an sàs na foirmlean iomchaidh, is urrainn dhuinn mòran dhuilgheadasan cunntaidh is coltachd fhuasgladh nas luaithe agus nas cruinne. Ann an cleachdadh, tha a’ chomas an dòigh cheart a thaghadh - iom-fhillteachadh no cothlamadh - gu tric nas cudromaiche na dìreach na foirmlean a chuimhneachadh.
