1 Some Counting Problems

Each of these problems involves determining how many of something there are. For most, there will be too many to simply make a list and count them off, so you will need to “count without counting”. As you go along, make a list of important counting principles you are using.

  1. A new company with just two employees, Sanchez and Patel, rents a floor of a building with 12 offices. How many ways are there to assign different offices to these two employees?

  2. The chairs of an auditorium are labeled with a letter (indicating the row) and a positive integer not exceeding 100 (indicating the seat within the row). Give an upper bound on the number of seats in the auditorium.

  3. There are 32 microcomputers in a computer center. Each microcomputer has 24 ports. How many different ports to a microcomputer in the center are there?

  4. How many bitstrings of length 8 are there?

  5. How many bitstrings of length 8 either start with a 1 or end with a 1?

  1. A state issues license plates that consist of three letters followed by three numbers. How many such plates are there?

  2. A graph isomorphism is a 1-1 and onto function from the vertices in one graph to the vertices in another (that additionally preserves edges). You decide to write a little program that will check each 1-1 and onto function to see if it an isomorphism.

    If your graphs have \(n\) vertices, how many such functions must you check?

  3. Now you modify your graph isomorphism algorithm so that it only tries bijections (1-1 and onto functions) that respect the degrees of the vertices. If the degree sequences of two graphs are both \((5, 5, 4, 4, 4, 3, 3, 2)\), how many functions must you check? How much better is this than your previous algorithm (on these two graphs)?

  4. Let’s use the following coding scheme to describe possible telephone numbers.

    • let X denote a digit that can take on any integer value 0 – 9;
    • let N denote a digit that can take on values 2 – 9
    • let Y denote a digit that can only take on values 0 or 1.

     

    1. In the scheme used in the 1960’s, telephone numbers had to have the form NYX-NNX-XXXX. How many such phone numbers are there?

    2. A new scheme (The North American Numbering Plan) was introduced that required telephone numbers have the form NXX-NXX-XXXX. How many more phone numbers are available in the new scheme?

  1. How many password of length 6, 7, or 8 are there if the passwords must be alpha-numeric, capitalization doesn’t matter, and there must be at least one digit?
  1. In the previous example, how many passwords are there if the first character must be a letter?

  1. Professor Pruim puts the names of 30 students into a hat. He draws one out and gives that person a chocolate bar. Then he draws out another name, and gives that person a bag of M and M’s. Finally, he draws out a third name and gives that person a bag of Valentine hearts he picked up cheap on February 15.

    1. How many different ways can the prizes be distributed?

    2. If you are one of the 30 students, how many of those ways include you getting a prize?

Answers/Solutions

  1. 12 * 11 = 132.

  2. 26 * 100 = 2600

  3. 32 * 24 = 768.

  4. \(2^8 =\) 256

  5. Two ways:

    1. only bad thing is beginning AND ending with 0, so \(2^8 - 2^6\) = 192.

    2. Start with 1 or end with 1 but not both: \(2^7 + 2^7 - 2^6\) = 192

  6. \(10^3 \cdot 26^3 =\) 17576000

  7. \(n!\)

  8. \(2 \cdot 1 \cdot 3 \cdot 2 \cdot 1 \cdot 2 \cdot 1 \cdot 1\) = 24. (\(8!\) = 40320, so that’s a pretty big speed up.)

  9. See book.

  10. \(36^6 - 26^6 + 36^7 - 26^7 + 36^8 - 26^8 =\) 2684483063360

  11. 26 * (36^5 - 26^5) + 26 * (36^6 - 26^6) + 26 * (36^7 - 26^7) = 1878468937280

  12. a. `30 * 29 * 28` = 24360
b. `1 * 29 * 28 + 29 * 1 * 28 + 29 * 28 * 1` = `30 * 29 * 28 - 29 * 28 * 27`
2436