Inclusion-Exclusion and Generating Function with Coefficient (and Integer Equation)

Problem 1: Suppose we wish to construct a password of length 20, which may include the following characters: 9 special characters, 10 numbers, 26 lowercase letters, and 26 uppercase letters. The password contains exactly 5 distinct special characters, and the first character is NOT a special character. Also, repetition of lowercase letters, numbers, and uppercase letters is allowed. Additionally we have the restrictions:
  • The password contains at least one number AND
  • At least two of the five special characters are consecutive
Find the total number of passwords possible with the (simultaneous) restrictions listed above by using the Principle of Inclusion-Exclusion and defining sets explicitly.

========================================================

Problem 2:
Suppose we want to assign 46 computer science students to work on teams to complete 12 projects. Note that it is possible for some projects to receive no qualified students to work on the project.

We have the following restrictions on the number of students on the teams:
  • Project teams 3 and 7 have exactly 8 students.
  • Project teams 1, 2, and 12 have no more than 5 students.
  • Project teams 4, 9, 10, and 11 have at least 3 students, but strictly less than 9 students.
  • Project teams 5, 6, and 8 have at least 4 students but strictly less than 16 students.
Find the total number of ways we can distribute 46 students to the 12 project teams by
  1. Modeling this combinatorial problem as an integer equation with restrictions
  2. Constructing a generating function
  3. Computing the relevant generating function coefficient

Answer

Answers can only be viewed under the following conditions:
  1. The questioner was satisfied with and accepted the answer, or
  2. The answer was evaluated as being 100% correct by the judge.
View the answer
  • Sorry, in problem 1 I obviously meant that S2 and S4 are the sets with no number, not the ones with at least a number, plus the remaining conditions.

  • Similarly, in S3 and S4 I meant that no two special characters are consecutive, not that no two special characters are consecutive. These are the sets that should be removed.

  • *not that of which at least two are consecutive.

  • Summarising: S1 counts the strings that have 5 special characters, one in first position; S2 counts the strings that have 5 special characters, one in first position, and no number; S3 counts the strings that have 5 special characters, one in first position, and of which no two are consecutive; S4 counts the strings that have 5 special characters, one in first position, of which no two are consecutive, and no number.

  • Olinix Olinix
    0

    Hi, thank you for your answers! Would you mind checking your answer to Problem 1 again? I'm computing both the "number of choices" solution and the inclusion-exclusion sets, and I'm getting two different answers. Also, where did the 9!/5! and \binom{49}{4} come from?

  • You're right, the 9!/5! should be 9!/4!, I copied it incorrectly. That comes from the choices of the 5 distinct special characters, in order in which they appear in the password (9 choices for the 1st, 8 for the 2nd, etc). The (19 choose 4) comes from the choices of the positions of the special characters: one is fixed (the 1st one should be in 1st position), so there are 19 positions left for the remaining 4 characters. Is it clear?

  • Ah, I actually wrote a (49 choose 4), missed it. It should obviously be (14 choose 4), that is a typo.

  • I'm sorry for the typos, but when one has to answer quicky, they inevitably happen, even if one double-checks everything. :/

The answer is accepted.
Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.