====== Permutation and Combination ======
순열과 조합
====== Permutation ======

세마리 말이 들어오는 순서의 경우의 수
{{:b:head_first_statistics:pasted:20191015-073815.png}}
===== So what if there are n horses? =====
팩토리얼 (n!)
{{:b:head_first_statistics:pasted:20191015-073918.png}}
{{:b:head_first_statistics:pasted:20191015-073945.png}}
----
Arranging in a circle: 말한마리를 고정해 놓고 다른 말들을 배치한다고 할 때, 그 조합은?
{{:b:head_first_statistics:pasted:20191015-074325.png}}
{{:b:head_first_statistics:pasted:20191015-074423.png}}
----
<WRAP box>
__<fc #ff0000><fs xx-large>Q:</fs></fc>__ Paula wants to telephone the Statsville Health Club, but she has a very poor memory. She knows that the telephone number contains the numbers 1,2,3,4,5,6 and 7, but she can’t remember the order. What’s the probability of getting the right number at random?
</WRAP>
A: 
<code>
factorial(7) 
</code>

<code>
> factorial(7)
[1] 5040
</code>

<WRAP box>
__<fc #ff0000><fs xx-large>Q:</fs></fc>__ Paula has just been reminded that the first three numbers is some arrangement of the numbers 1, 2 and 3, and the last four numbers is some arrangement of the numbers 4, 5, 6, and 7. She can't remember the order of each set of numbers though. What's the probability of getting the right telephone number now? 
</WRAP>

<code>
factorial(3)*factorial(4)
</code>

<code>
> factorial(3)*factorial(4)
[1] 144
</code>

<WRAP box>
__<fc #ff0000><fs xx-large>Q:</fs></fc>__ The Statsville Derby is organizing a parade for the end of the season. 10 horses are taking part, and they will parade round the race track in a circle. The exact horse order will be chosen at random, and if you guess the horse order correctly, you win a prize. What’s the probability that if you make a guess on the exact horse order, you’ll win the prize?
</WRAP>

<code>
n <- 10
factorial(n-1)
</code> 

<code>
> n <- 10
> factorial(n-1)
[1] 362880
>
</code> 

===== Arranging by individuals is different than arranging by type  =====
by type . . . .

a, a, b  =>
aab
aba
baa

a1, a2, b =>
a1, a2, b
a2, a1, b
a1, b, a2
a2, b, a1
b, a1, a2
b, a2, a1

$$ \frac {n!} {p! * q!} $$

<BOOKMARK:arranging_group>
{{:b:head_first_statistics:pasted:20191015-075959.png}}

6 horses
2 groups 3 horses per each group

{{:b:head_first_statistics:pasted:combination.arranging.duplicates.png}}

<code>
factorial(6)/(factorial(3)*factorial(3))
</code>

<code>
> factorial(6)/(factorial(3)*factorial(3))
[1] 20
> 
</code>

{{:b:head_first_statistics:pasted:20191015-080318.png}}
{{:b:head_first_statistics:pasted:20191015-081850.png}}

<WRAP box>
X = {a a b c c c} 라면?
n(X) = 6 이므로 총 6! 
a가 둘, c가 셋으로 묶이므로
6! / (2! * 3!)
= 6*5*2 = 60


</WRAP>

<WRAP box>
__<fc #ff0000><fs xx-large>Q:</fs></fc>__ The Statsville Derby have decided to experiment with their races. They've decided to hold a race between <fc #ff0000>3 horses, 2 zebras and 5 camels</fc>, where all the animals are equally likely to finish the race first.

1. How many ways are there of finishing the race if we’re interested in individual animals?

2. How many ways are there of finishing the race if we’re just interested in the species of animal in each position?

3. What's the probability that all 5 camels finish the race consecutively if each animal has an equal chance of
winning? (Assume we’re interested in the species in each position, not the individual animals themselves.)
</WRAP>

<code>
## for Q1, there are ten animals 
factorial(10)
## 
factorial(10)/(factorial(3)*factorial(2)*factorial(5))
## 3, 2, 1 type (5 camels as one)
factorial(6)/(factorial(3)*factorial(2))
</code>
<code>> factorial(10)
[1] 3628800
> factorial(10)/(factorial(3)*factorial(2)*factorial(5))
[1] 2520
> factorial(6)/(factorial(3)*factorial(2))
[1] 60
> 
</code>
====== Combination ======
===== How many ways can we fill the top three positions? =====
20 horses
{{:b:head_first_statistics:pasted:20191015-082956.png}}


<code>
ans <- 20*19*18
ans

factorial(20)/factorial(17)
</code>
<code>
> ans <- 20*19*18
> ans
[1] 6840
> 
> factorial(20)/factorial(17)
[1] 6840
> 
> 
</code>

{{:b:head_first_statistics:pasted:20191015-083059.png}}
$ {}{}_{n}\mathrm{P}_{r} $ 

===== What if horse order doesn’t matter =====
A B C 
1 head 1 sub-head
A B
B A
B C
C B
A C
C A

\begin{eqnarray*}
_{3}P_{2} & = & \frac{3!}{(3-2)!} \\
 & = & \frac {3!}{(3-2)!} = 6
\end{eqnarray*}

Among the two, the order doesn't matter. Then, we follow the same logic as [[#arranging_group|the above]]
2 representatives
A B | B A
B C | C B
A C | C A

\begin{eqnarray*}
\text{Answer we want} & = & \frac {_{3}P_{2}}{2!} \\
\text{We call this} & = &  _{3}C_{2}  \\
_{3}C_{2} & = & \frac {\frac{3!}{(3-2)!}} {\frac {2!} {1}} \\
_{3}C_{2} & = & \frac {3!}{2! * (3-2)!} = 3
\end{eqnarray*}

{{:b:head_first_statistics:pasted:20191015-083531.png}}

<code>
factorial(20)/(factorial(17)*factorial(3))
</code>

<code>
> factorial(20)/(factorial(17)*factorial(3))
[1] 1140
> 
</code>

{{:b:head_first_statistics:pasted:20191015-083826.png}}

{{:b:head_first_statistics:pasted:20191015-084051.png}}

\begin{eqnarray*}
\displaystyle ^{n} P_{r} = \displaystyle \dfrac {n!} {(n-r)!} \\
\end{eqnarray*}

A **permutation** is the number of ways in which you can choose objects from a pool, and **where the order in which you choose them counts**. It’s a lot more specific than a combination as you want to count the number of ways in which you fill each position.

\begin{eqnarray*}
\displaystyle ^{n} C_{r} & = & \displaystyle \dfrac {^{n} P_{r}} {r!} \\
& = & \displaystyle \frac {n!} {r! \cdot (n-r)!} \\
\end{eqnarray*}
A **combination** is the number of ways in which you can choose objects from a pool, **without caring about the exact order in which you choose them**. It’s a lot more general than a permutation as you don’t need to know how each position has been filled. It’s enough to know which objects have been chosen.

===== e.g. =====
<WRAP box>
The Statsville All Stars are due to play a basketball match. There are 12 players in the roster, and 5 are allowed on the court at any one time.

1. How many different arrangements are there for choosing who’s on the court at the same time?

2. The coach classes 3 of the players as expert shooters. What’s the probability that all 3 of these players will be on the court at the same time, if they’re chosen at random?
</WRAP>

<WRAP box>
$ {}_{52} P _{5} $
<code>
# only combination function is available in r, choose
# for permutation
> choose(52,5)
[1] 2598960
> permute <- function(n,r) { 
>   choose(n,r) * factorial(r) 
> }
> permute(52, 5)
> [1] 311875200
> # or 
> factorial(52)/factorial(52-5)
[1] 311875200
> 
</code>
</WRAP>
답. 12명 중에서 순서는 상관없는 5명이므로 
${}_{12} C _{5} $
<code>
## n! / r!(n-r)!
factorial(12)/(factorial(5)*factorial(12-5))
## 3명은 같이 뛰게 되니, 2명에 대한 조합만 생각하기로 한다
## 3명이 빠진 9명중 2명의 조합이니
## n! / r!(n-r)!
factorial(9)/(factorial(2)*factorial(9-2))
a <- factorial(12)/(factorial(5)*factorial(12-5))
b <- factorial(9)/(factorial(2)*factorial(9-2))
a 
b
</code>
<code>
> factorial(12)/(factorial(5)*factorial(12-5))
[1] 792
> factorial(9)/(factorial(2)*factorial(9-2))
[1] 36
> a <- factorial(12)/(factorial(5)*factorial(12-5))
> b <- factorial(9)/(factorial(2)*factorial(9-2))
> a 
[1] 792
> b
[1] 36
> 
</code>

<WRAP box help>
It’s time for you to work out some poker probabilities. See how you get on. A poker hand consists of 5 cards and there are 52 cards in a pack. How many different arrangements are there? 

A royal flush is a hand that consists of a 10, Jack, Queen, King and Ace, all of the same suit. What’s the probability of getting this combination of cards? Use your answer above to help you. 

Four of a kind is when you have four cards of the same denomination. Any extra card makes up the hand. What’s the probability of getting this combination?

A flush is where all 5 cards belong to the same suit. What’s the probability of getting this?
</WRAP>
{{https://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Piatnikcards.jpg/1920px-Piatnikcards.jpg?800}}
see [[wp>List_of_poker_hands]]
{{https://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/A_studio_image_of_a_hand_of_playing_cards._MOD_45148377.jpg/1024px-A_studio_image_of_a_hand_of_playing_cards._MOD_45148377.jpg?400}}
<code>
## 52장의 카드 중에서 5장 고를 조합은
factorial(52)/(factorial(5)*factorial(52-5))
all2 <- factorial(52)/(factorial(5)*factorial(52-5))
all2
# or 
all <- choose(52, 5)
all
## royal flush = 10, 11, 12, 13, 1 각 문양
## 즉, 4가지. 따라서 전체 조합 중 4가지만 해당됨
4 / all

## four cards = 13 가지
## {1,1,1,1} {2,2,2,2} . . . . {13,13,13,13} = 13 가지
## 그리고 나머지 한장은 4장을 제외한 48장에서 조합되는 것이니
13 * (52-4) 
## 위의 숫자가 four of a kinds에 해당되는 경우의 수
## 따라서 그 확률은 four cards out of five cards
(13 * (52-4)) / all

## 13 개 같은 모양 중에서 5개가 나올 조합은 13C5
## 그리고, 모양이 4 종류가 있으니 * 4를 하면
4 * (factorial(13)/(factorial(5)*factorial(13-5)))
## 그 확률은
(4 * (factorial(13)/(factorial(5)*factorial(13-5)))) / all

</code>

<code>
> ## 52장의 카드 중에서 5장 고를 조합은
> factorial(52)/(factorial(5)*factorial(52-5))
[1] 2598960
> all <- factorial(52)/(factorial(5)*factorial(52-5))
> ## royal flush = 10, 11, 12, 13, 1 각 문양
> ## 즉, 4가지. 따라서 전체 조합 중 4가지만 해당됨
> 4 / all
[1] 1.539077e-06
> 
> ## four cards = 13 가지
> ## {1,1,1,1} {2,2,2,2} . . . . {13,13,13,13} = 13 가지
> ## 그리고 나머지 한장은 4장을 제외한 48장에서 조합되는 것이니
> 13 * (52-4) 
[1] 624
> ## 위의 숫자가 four of a kinds에 해당되는 경우의 수
> ## 따라서 그 확률은 four cards out of five cards
> (13 * (52-4)) / all
[1] 0.000240096
> 
> ## 13 개 같은 모양 중에서 5개가 나올 조합은 13C5
> ## 그리고, 모양이 4 종류가 있으니 * 4를 하면
> 4 * (factorial(13)/(factorial(5)*factorial(13-5)))
[1] 5148
> ## 그 확률은
> (4 * (factorial(13)/(factorial(5)*factorial(13-5)))) / all
[1] 0.001980792
> 
</code>

===== exercises =====
말 3마리, 얼룩말 4마리, 그리고 낙타 6마리 중에서 낙타 4마리와 얼룩말 3마리를 뽑아서 일렬로 앉히는 경우의 수를 구하시오. 
<code>
> # 6C4 * 4C3 * 7!
> choose(6,4) * choose(4,3) * factorial(4+3)
[1] 311875200
> 
</code>

tennessee 를 서로 다른 방법으로 배치할 수 있는 경우의 수는?
<code>
> # t
> # eeee
> # nn
> # ss
> # 9 letters
> # 9!/4!*2!*2!
> factorial(9)/(factorial(4)*factorial(2)*factorial(2))
[1] 3780
> 
</code>

AGAIN이라는 단어가 있다. 이 단어를 알파벳 순으로 조합하여 나열한다면 49번째 오는 단어는 어떤 것일까?

처음 A 로 시작하게 되는 단어는 G A I N 의 단어를 조합하여 나오는 수 4! = 24 단어
다음에는 G 로 시작하는 단어 A A I N 의 단어의 조합은 4!/2! = 12 단어
I 로 시작하는 단어는 A G A N 의 조합은 4!/2! = 12 단어
그렇다면 N으로 시작하는 첫단어가 답
N A A G I 

S M I L E 이라는 단어의 문자에서 3 개를 뽑아서 나열하는 경우의 수는?

$ _{5}P_{3} = \dfrac {5!}{2!} = 60 $

AJOU UNIVERSITY 단어에서 AJOU 네 단어가 서로 이웃해서 모든 단어가 나열되는 경우의 수는?
X U N I V E R S I  T  Y
1 2 3 4 5 6 7 8 9 10 11
11 글자의 조합은 11! / 2!
A J O U 의 조합도 신경을 써야 하므로 4! 을 곱해준다.

POWERFUL 라는 단어의 글자들을 나열하려고 한다. 모음이 앞이나 뒤에 적어도 한번은 들어가도록 나열하는 경우의 수는? W는 자음
이다.
모 . . . . 모
모 . . . . 자
자 . . . . 모
자 . . . . 자
의 경우라고 생각해야 할 듯 
모음은 O E U 
자음은 P W R F L 
전체 글자는 8 글자   8!
양쪽에 자음이 오는 경우는 5P2 = 20


\begin{eqnarray*}
{n \choose x} \\
\binom{n}{r} \\
_{n}C_{r} \\
^{n}P_{r} \\
_{n}P_{r} \\

\end{eqnarray*}