permutations and combinations 0000000000

good ppt

1. 1
Permutations and
Combinations
CS/APMA 202
Epp section 6.4
Aaron Bloomfield

2. 2
Permutations vs. Combinations
•Botharewaystocountthepossibilities
•Thedifferencebetweenthemiswhetherorder
mattersornot
•Considerapokerhand:
–A♦,5♥,7♣,10♠,K♠
•Isthatthesamehandas:
–K♠,10♠,7♣,5♥,A♦
•Doestheorderthecardsarehandedout
matter?
–Ifyes,thenwearedealingwithpermutations
–Ifno,thenwearedealingwithcombinations

3. 3
Permutations
•Apermutationisanorderedarrangementofthe
elementsofsomesetS
–LetS={a,b,c}
–c,b,aisapermutationofS
–b,c,aisadifferentpermutationofS
•Anr-permutationisanorderedarrangementofr
elementsoftheset
–A♦,5♥,7♣,10♠,K♠isa5-permutationofthesetof
cards
•Thenotationforthenumberofr-permutations:
P(n,r)
–ThepokerhandisoneofP(52,5)permutations

4. 4
Permutations
•Numberofpokerhands(5cards):
–P(52,5)=52*51*50*49*48=311,875,200
•Numberof(initial)blackjackhands(2cards):
–P(52,2)=52*51=2,652
•r-permutationnotation:P(n,r)
–ThepokerhandisoneofP(52,5)permutations)1)...(2)(1(),(  rnnnnrnP )!(
!
rn
n

 


n
rni
i
1

5. 5
r-permutations example
•Howmanywaysaretherefor5peoplein
thisclasstogivepresentations?
•Thereare27studentsintheclass
–P(27,5)=27*26*25*24*23=9,687,600
–Notethattheordertheygoindoesmatterin
thisexample!

6. 6
Permutation formula proof
•Therearenwaystochoosethefirst
element
–n-1waystochoosethesecond
–n-2waystochoosethethird
–…
–n-r+1waystochoosether
th
element
•Bytheproductrule,thatgivesus:
P(n,r)=n(n-1)(n-2)…(n-r+1)

7. 7
Permutations vs. r-permutations
•r-permutations:Choosinganordered5
cardhandisP(52,5)
–Whenpeoplesay“permutations”,theyalmost
alwaysmeanr-permutations
•Butthenamecanrefertoboth
•Permutations:Choosinganorderforall52
cardsisP(52,52)=52!
–Thus,P(n,n)=n!

8. 8
Sample question
•Howmanypermutationsof{a,b,c,d,e,f,g}
endwitha?
–Notethatthesethas7elements
•Thelastcharactermustbea
–Therestcanbeinanyorder
•Thus,wewanta6-permutationontheset{b,c,
d,e,f,g}
•P(6,6)=6!=720
•WhyisitnotP(7,6)?

9. 10
Combinations
•Whatiforderdoesn’tmatter?
•Inpoker,thefollowingtwohandsareequivalent:
–A♦,5♥,7♣,10♠,K♠
–K♠,10♠,7♣,5♥,A♦
•Thenumberofr-combinationsofasetwithn
elements,wherenisnon-negativeand0≤r≤nis:)!(!
!
),(
rnr
n
rnC



10. 11
Combinations example
•Howmanydifferentpokerhandsarethere
(5cards)?
•Howmanydifferent(initial)blackjack
handsarethere?2,598,960
!47*1*2*3*4*5
!47*48*49*50*51*52
!47!5
!52
)!552(!5
!52
)5,52( 

C 1,326
1*2
51*52
!50!2
!52
)!252(!2
!52
)2,52( 

C

11. 12
Combination formula proof
•LetC(52,5)bethenumberofwaystogenerate
unorderedpokerhands
•ThenumberoforderedpokerhandsisP(52,5)=
311,875,200
•Thenumberofwaystoorderasinglepoker
handisP(5,5)=5!=120
•Thetotalnumberofunorderedpokerhandsis
thetotalnumberoforderedhandsdividedbythe
numberofwaystoordereachhand
•Thus,C(52,5)=P(52,5)/P(5,5)

12. 13
Combination formula proof
•LetC(n,r)bethenumberofwaystogenerate
unorderedcombinations
•Thenumberoforderedcombinations(i.e.r-
permutations)isP(n,r)
•Thenumberofwaystoorderasingleoneof
thoser-permutationsP(r,r)
•Thetotalnumberofunorderedcombinationsis
thetotalnumberoforderedcombinations(i.e.r-
permutations)dividedbythenumberofwaysto
ordereachcombination
•Thus,C(n,r)=P(n,r)/P(r,r)

13. 14
Combination formula proof)!(!
!
)!/(!
)!/(!
),(
),(
),(
rnr
n
rrr
rnn
rrP
rnP
rnC






14. 15
Bit strings
•Howmanybitstringsoflength10contain:
a)exactlyfour1’s?
Findthepositionsofthefour1’s
Doestheorderofthesepositionsmatter?
•Nope!
•Positions2,3,5,7isthesameaspositions7,5,3,2
Thus,theanswerisC(10,4)=210
b)atmostfour1’s?
Therecanbe0,1,2,3,or4occurrencesof1
Thus,theansweris:
•C(10,0)+C(10,1)+C(10,2)+C(10,3)+C(10,4)
•=1+10+45+120+210
•=386

15. 16
Bit strings
•Howmanybitstringsoflength10contain:
c)atleastfour1’s?
Therecanbe4,5,6,7,8,9,or10occurrencesof1
Thus,theansweris:
•C(10,4)+C(10,5)+C(10,6)+C(10,7)+C(10,8)+C(10,9)
+C(10,10)
•=210+252+210+120+45+10+1
•=848
Alternativeanswer:subtractfrom2
10
thenumberof
stringswith0,1,2,or3occurrencesof1
d)anequalnumberof1’sand0’s?
Thus,theremustbefive0’sandfive1’s
Findthepositionsofthefive1’s
Thus,theanswerisC(10,5)=252

16. 17 ! )()!(
!
),(
rnnrn
n
rnnC

 )!(!
!
rnr
n

 )!(!
!
),(
rnr
n
rnC


Corollary 1
•Letnandrbenon-negativeintegerswith
r≤n.ThenC(n,r)=C(n,n-r)
•Proof:

17. 18
Corollary example
•ThereareC(52,5)waystopicka5-cardpoker
hand
•ThereareC(52,47)waystopicka47-cardhand
•P(52,5)=2,598,960=P(52,47)
•Whendealing47cards,youarepicking5cards
tonotdeal
–Asopposedtopicking5cardtodeal
–Again,theorderthecardsaredealtindoesmatter

18. 19
Combinatorial proof
•Acombinatorialproofisaproofthatusescounting
argumentstoproveatheorem
–Ratherthansomeothermethodsuchasalgebraictechniques
•Essentially,showthatbothsidesoftheproofmanageto
countthesameobjects
•Mostofthequestionsinthissectionarephrasedas,
“findouthowmanypossibilitiesthereareif…”
–Instead,wecouldphraseeachquestionasatheorem:
–“Provetherearexpossibilitiesif…”
–Thesameanswercouldbemodifiedtobeacombinatorialproof
tothetheorem

19. 20
Circular seatings
•Howmanywaysaretheretosit6peoplearoundacirculartable,
whereseatingsareconsideredtobethesameiftheycanbe
obtainedfromeachotherbyrotatingthetable?
•First,placethefirstpersoninthenorth-mostchair
–Onlyonepossibility
•Thenplacetheother5people
–ThereareP(5,5)=5!=120waystodothat
•Bytheproductrule,weget1*120=120
•Alternativemeanstoanswerthis:
•ThereareP(6,6)=720waystoseatthe6peoplearoundthetable
•Foreachseating,thereare6“rotations”oftheseating
•Thus,thefinalansweris720/6=120

20. 21
Horse races
•Howmanywaysaretherefor4horsestofinishiftiesareallowed?
–Notethatorderdoesmatter!
•Solutionbycases
–Noties
•ThenumberofpermutationsisP(4,4)=4!=24
–Twohorsestie
•ThereareC(4,2)=6waystochoosethetwohorsesthattie
•ThereareP(3,3)=6waysforthe“groups”tofinish
–A“group”iseitherasinglehorseorthetwotyinghorses
•Bytheproductrule,thereare6*6=36possibilitiesforthiscase
–Twogroupsoftwohorsestie
•ThereareC(4,2)=6waystochoosethetwowinninghorses
•Theothertwohorsestieforsecondplace
–Threehorsestiewitheachother
•ThereareC(4,3)=4waystochoosethetwohorsesthattie
•ThereareP(2,2)=2waysforthe“groups”tofinish
•Bytheproductrule,thereare4*2=8possibilitiesforthiscase
–Allfourhorsestie
•Thereisonlyonecombinationforthis
–Bythesumrule,thetotalis24+36+6+8+1=75

21. 22
•Analternative(andmorecommon)wayto
denoteanr-combination:
•I’lluseC(n,r)wheneverpossible,asitis
easiertowriteinPowerPoint








r
n
rnC),(
A last note on combinations