Project 4 Combintorics

Multiplication Rule Problem 1.)

1. A computer installation has 6 input/output units (I/O) and 4 central processing units (CPUs). I/O units can be paired in any way with CPUs: in how many ways can this be done?

To approach this problem I took into consideration the multiplication rule;

Suppose an operation has n steps. Also suppose that:

    • the first operation can be carried out in k_1 ways;
    • independently, the second operation can be carried out in k_2 ways;
    • independently, the third operation can be carried out in k_3 ways;

\ldots

    • independently, the n^{th} operation can be carried out in k_n ways;

then the entire operation can be carried out in k_1\times\ldots k_n ways.

With this in mind i realized there were 6 I/O ports and 4 central processing units which would mean each of those input output ports could be combined individually with one cpu. If we multiply the number of operations by the number of different combination the operation can be completed in we get that the maximum number of solutions is 24.

6(I/O ports) * 4 (CPU’s)= 24 possible solutions.

 

Multiplication Rule Problem 2.)

A PIN is made by choosing 4 symbols from the 26 letters of the alphabet and the ten digits 0, 1, 2, 3 , 4, 5, 6, 7, 8, 9.

    • How many different PINs are there?
    • How many different PINS are there in which repetition of a symbol is not allowed?
    • How many different PINs are there if a PIN cannot begin with any of the letters N through Z and must end in a digit

In reply to the first question, how many pins are there.There are 36 different combinations for each of the 4 characters. If we think of a smaller example using binary code which allows you to input 2 different combination a 0 or 1. The two digits 2^2 is equal to 4 and there are four possible combinations 00, 01, 10, 11. This can be applied to our situation, by taking 36^4 would give us a resulting number of 1679616 possible combinations.

For the next question, we have to basically subtract 1 from the possible amount of symbols every time one is chosen as we do not want any duplicates. This can be represented as 36*35*34*33 = 1413720 possible combinations.

Last but not least for the final question we must restrict our chioces even further. The first possible symbol only has 23 choices (36 original – 13 the thirteen is n-z) then the second two characters have 36 possible combinations each, and the last character has 10 possible combinations. We can find all possbile combations as we did above by  using the multiplication rule  23*36*36*10 = 298080 possible solutions.

 

Multiplication Rule Problem 3.)

In a tech startup, a Chief Executive Office (CEO), Chief Financial Officer (CFO) and a Chief Technical Officer (CTO) are to be chosen from the five founders: Alice, Bob, Carol, Dave and Ed. Ann cannot be CFO, and the CTO must be either Carol or Dave. In how many ways is it possible to fill the positions of CEO, CFO and CTO?

    • First answer this question by choosing the CEO, then the CFO and then the CTO.
    • Then answer the question by first choosing the CTO, then the CEO, and then the CFO.

In the above problem there is a typo, Ann is nonexistent, Alice should be in the place of Ann.

 

When the CEO, CFO, and CTO are chosen in that order and assuming no person can hold two positions, there are 16 possible combinations (6 for A first, 4 for B first, 2 for C and D first, and 4 for E first).

For the next question  question we are choosing CTO >CEO > CFO. There are two possible combinations for the CTO, carol and dave. Then we must choose the CEO, we also have to take into account that this is a very special case because if Alice is picked as the CEO there will not be the same type of options avaliable to us as there would be if anyone else were to get picked. This can be solved by adding the two possibilities we have in case 1, we have two possibilities for CTO, 3 for CEO (ignoring alice for now), and then two possible combinations for CFO. For case 2 we again have two possible combinations for CTO, then one (just considering Alice). Then we have three combinations for CFO at the end. After taking all these different combinations that can come about i used the multiplication rule in order to figure out the number of possible combinations including Alice in the mix.

Multiplication rule : (2*3*2 + 2*1*3) = 18 possible combinations.

Multiplication Rule Problem 4.)

What fraction of 4-digit numbers are odd and have all digits different?

An odd number with four digits has a pretty big range to work with. This range includes numbers from 1000 to 9999. This means that the first number can be from 1-9 which is 9 characters. There are then 9 possibilities to be a different number for the second digit (include 0 this time so 0-10 then subtract the digit used first since there can be not repeating digits) then the third has one less option than the second, which would be 8 options. Since the number must be odd, there are in the best case 5 odd numbers, in the worst case there are only two odd numbers left.

Addition Rule Problem 1.)

1. A password can be formed using the 26 letters of the alphabet and the ten digits 0, 1, 2, 3 , 4, 5, 6, 7, 8, 9. The password must be 8 to 12 characters in length. How many such passwords are there?

This problem can be represented as a sum formula. It can be represented as the sum from 8 to 12 of 36^n. We use this formula because

26 letters A…Z     +     10 digits 0…9     =     36 possible characters

For a password of length 8, each character in the password can have 1 of 36 possibilities. Therefore there are 36^8 possible combinations.

For a password of length n, there are 36^n possible combinations.

Given the boundaries that the password must be 8-12 characters long would gave us the bounds for our summation shown below.

Seen here:

CodeCogsEqn = 4.8 * 10^18 possibilities

 

Addition Rule Problem 2.)

How many 4-digit positive integers are divisible by 5?

The only numbers that are divisible by 5 have to end in either a 0 or 5. There are 10 possibilities for each of the first three digits (0-9). We can then multiply all of these together to get the number of possibilities. 10 * 10 * 10 * 2 – 2000. There are 2000 4 digit numbers divisible by 5. To get this formula you realize there are 10 different combinations that can be achieved for the first three numbers but when you get to the least significant number there are only two possible combinations.

Addition Rule Problem 3.)

In the Python language, identifiers must start with either a lower or upper case letter of the alphabet, or an underscore (53 choices in all). The beginning character of the identifier may be followed by any of the initial characters plus any of the ten digits 0, 1, 2, 3 , 4, 5, 6, 7, 8, 9 (63 characters in all). In one implementation of Python there are 31 reserved words of length 1 through 8 characters, which may not be used as identifiers.

How many identifiers of length less than or equal to 8 are there?

The first needs to be one of the 53 characters. The following can also include (0-9) making a total of 63 characters because the addition of the other 10 possible characters. Because different lengths of words require different situations, we must get the sum from 2 to 8 (the maximum number). Finally we can subtract the 31 reserved words from these possibilities.

CodeCogsEqn-1 =

[(53)+(63^2)+(63^3)+(63^4)+(63^5)+(63^6)+(63^7)+(63^8)]-31 = 252158292852439

 

 

 

 

Leave a comment