Permutations & Combinations

1. Permuatations
- 1.1. Loose Permutations
  - 1.1.1. Example
- 1.2. Regular Permutations
  - 1.2.1. Formula
  - 1.2.2. Example
2. Combinations

1. Permuatations

DEF - numbre of unique ways that objects can be selected or arranged.

“Loose Permuations” (multiple buckets or “with replacement”)
(Regular) Permuations (1 bucket or “without replacemnt”)
Combinations (1 bucket or “without replacement”)

1.1. Loose Permutations

Permutations where the possiblites are multiplied by each other

1.1.1. Example

        Mileage(M1, M2, M3), Price(P1, P2), Cost(C1, C2, C3)

        How many car types?

        Sample: M1 P1 C1


        Each car can have a range of mileage.
        Each mileage can have a range of prices.
        Each price can have a range of cost.

        18 branches -> 18 car types -> *18 permuations*

1.2. Regular Permutations

1.2.1. Formula

Order Does Matter (n!)/(n-r)! Permutations where it is usually n-1

Selecting r elements from the same group of n elements.

1.2.2. Example

        In how many different ways can a union local with
        a membership of 25 choose a vice president and then a president?

        A, B, C, D, E, ..., Y

        Some Perms: AB, AC, AD, ...

        n = 25
        r = 2

        vice president can be chosen in 25 ways AND the president in 24 ways.

        Thus, there are 25 * 24 different ways = 600.

2. Combinations

2.1. Formula

Have to establish order doesn’t matter first!

“n choose r”

n!/r!(n-r)!

2.2. Examples

        Let's say you have 4 friends (A, B, C, D),
        and you want to hang out with 3 of them only.
        How many possible groups of 3 friends can you form?

        Some Permutations: ABC, ADC, CBD

        n = 4
        r = 3

        4*3*2 = 24??

        No,

        6 ways of getting same 3 people.

        3*2*1 = 6

        6 ways of selecting the same r objects.

        So,

        divide the 24/6 = 4 total unique groups (combinations)

        Suppose there are 15 copy machines on campus.
        In how many ways can 5 of the 15 be selected for inspection?

        n = 15
        r = 5

        order doesnt matter.

        So,

        (15*14*13*12*11)/5! = 3003 ways.

        How many binary sequences (i.e., sequences of 0’s and 1’s)
        of length 10 with exactly four 1’s can be formed?

        n = 10
        r = 4

        Samples:
        1111000000
        0000001111
        0101010100

        Look at 4 positions to reframe them to select a 1.

        1111000000 (P1P2P3P4)
        0000001111 (P7P8P9P10)
        0101010100 (P2P4P6P8)

        (10*9*8*7) = 5024 permutations

        P1P2P3P4=P4P3P2P1
        However, posiiton does NOT MATTER.

        So,

        (10*9*8*7)/(4*3*2)= 210 sequences with four ones.