Discrete Mathematics I for SE - EMath 1105
45 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the total number of possible passwords of 6 to 8 characters that consist of upper case letters and digits, including at least one digit?

  • 3.4567 x 10^11
  • 2.6845 x 10^12 (correct)
  • 9.8765 x 10^13
  • 1.2345 x 10^12

The number of possibilities for selecting a wedding picture with the bride not present is 90,720.

False (B)

How many options are left for choosing the remaining five people after selecting the bride in the wedding picture scenario?

15120

The total number of passwords of length 7, which must contain at least one digit, is calculated as P7 = 36^7 - ______.

<p>26^7</p> Signup and view all the answers

Match the following password lengths with their corresponding formulas:

<p>P6 = 36^6 - 26^6 P7 = 36^7 - 26^7 P8 = 36^8 - 26^8</p> Signup and view all the answers

How many ways can we label a chair if each label consists of both a letter and a number between 1 and 50?

<p>1300 (B)</p> Signup and view all the answers

The sum rule can be used when the procedures are mutually exclusive.

<p>True (A)</p> Signup and view all the answers

If there are 31 flavors of ice cream, 4 sizes of serving, and a choice of cone or dish, how many different orders of ice cream can be placed?

<p>248</p> Signup and view all the answers

There are ___ candidates from UCLA and ___ candidates from Harvard.

<p>50, 20</p> Signup and view all the answers

Match the following examples with their corresponding counting rule:

<p>Labeling a chair = Product Rule Choosing dinner options = Sum Rule Ice cream order combinations = Product Rule Selecting an applicant from universities = Sum Rule</p> Signup and view all the answers

What is the total number of dinner options available at a restaurant with 18 meat dinners, 10 fish dinners, and 5 vegetarian dinners?

<p>33 (C)</p> Signup and view all the answers

If two procedures can occur simultaneously, the product rule should be used.

<p>True (A)</p> Signup and view all the answers

What does the product rule state in combinatorial counting?

<p>Multiply the number of ways to perform each procedure.</p> Signup and view all the answers

How many teachers are available to form a committee?

<p>8 (D)</p> Signup and view all the answers

The Pigeonhole Principle states that if there are more holes than pigeons, at least one hole will contain more than one pigeon.

<p>False (B)</p> Signup and view all the answers

What does the Generalized Pigeonhole Principle help to determine?

<p>It helps to determine the minimum number of balls in at least one box when dividing n balls among k boxes.</p> Signup and view all the answers

If we divide ___ balls among k boxes and n > k, at least one box contains at least ⌈n/k⌉ balls.

<p>n</p> Signup and view all the answers

Match the following concepts with their descriptions:

<p>Pigeonhole Principle = More than n items in n containers leads to at least one container with more than one item Generalized Pigeonhole Principle = Determines minimum items in one container when items exceed containers Tree Diagram = Visual representation of all possible outcomes of a sequence of events Committee formation = Choosing a subgroup from a larger group of individuals</p> Signup and view all the answers

How many ways can a committee of exactly three students be formed from four students and eight teachers?

<p>20 (B)</p> Signup and view all the answers

In a Tree Diagram, the number of choices can never be large.

<p>True (A)</p> Signup and view all the answers

What could be a disadvantage of using Tree Diagrams?

<p>They are only practical when the number of choices is small.</p> Signup and view all the answers

How many distinct ways can 6 people be seated around a table considering rotations?

<p>120 (C)</p> Signup and view all the answers

The Inclusion-Exclusion Principle states that to find the total number of ways to perform procedure 1 or procedure 2, you simply sum the ways without any adjustments.

<p>False (B)</p> Signup and view all the answers

What is the formula for the Inclusion-Exclusion Principle?

<p>|A ∪ B| = |A| + |B| - |A ∩ B|</p> Signup and view all the answers

The total number of bit strings of length eight that start with 1 is _____.

<p>128</p> Signup and view all the answers

Match the following terms with their corresponding numerical values:

<p>|A| = 128 |B| = 64 |A ∩ B| = 32 |A ∪ B| = 160</p> Signup and view all the answers

What is the value of |A ∪ B| for bit strings of length 8 that either start with 1 or end with 00?

<p>160 (D)</p> Signup and view all the answers

The calculation for seating arrangements around a table considers both linear and circular permutations equally.

<p>False (B)</p> Signup and view all the answers

The number of bit strings ending with 00 is _____ for length eight.

<p>64</p> Signup and view all the answers

How many total possibilities are there for a wedding picture that includes both the bride and groom?

<p>50,400 (B)</p> Signup and view all the answers

If only one of the bride and groom is included in the picture, what is the total number of possibilities?

<p>80,640 (B)</p> Signup and view all the answers

The bride can occupy 5 positions in the wedding picture.

<p>False (B)</p> Signup and view all the answers

What is the product rule used for in this context?

<p>To calculate the total number of arrangements by multiplying possibilities together.</p> Signup and view all the answers

If only the bride is included in the wedding picture, the total number of possibilities is _____.

<p>40,320</p> Signup and view all the answers

Match the following scenarios with their resulting possibilities:

<p>Both bride and groom included = 50,400 possibilities Only the bride included = 40,320 possibilities Only the groom included = 40,320 possibilities</p> Signup and view all the answers

How many people are there to choose from after placing the bride and groom when they are both included?

<p>8</p> Signup and view all the answers

The sum rule is used when calculating possibilities for a scenario involving only one of the bride or groom.

<p>True (A)</p> Signup and view all the answers

How many different arrangements are possible for the band of four boys if each can play all four instruments?

<p>24 (C)</p> Signup and view all the answers

When rolling a die four times, the number of possible outcome sequences is 1296.

<p>False (B)</p> Signup and view all the answers

How many area codes are possible in the US and Canada?

<p>640</p> Signup and view all the answers

The number of ways to arrange the letters in the word 'arrange' is _____

<p>420</p> Signup and view all the answers

Match each situation with the correct formula:

<p>No restrictions on seating = 8! A and B must sit next to each other = 7!2! 4 men and 4 women with restrictions = 2*4!4!</p> Signup and view all the answers

How many area codes can start with the digit 4?

<p>16 (C)</p> Signup and view all the answers

The number of arrangements of the word 'Mississippi' is less than 2000.

<p>False (B)</p> Signup and view all the answers

How many different letter arrangements can be made from the word 'propose'?

<p>105</p> Signup and view all the answers

Flashcards

Password Constraints

A password must be between 6 and 8 characters long, contain at least one digit, and each character is an uppercase letter or a digit.

Counting Possibilities: Product Rule

To count the number of ways to perform a task that involves multiple steps, multiply the number of possibilities at each step.

Exclusions in Counting

When counting possibilities with specific constraints, subtract the number of invalid possibilities from the total number of possibilities.

Calculating Password Combinations

To find the total number of possible passwords, calculate the combinations for each password length (6, 7, 8) and sum them.

Signup and view all the flashcards

Counting Wedding Picture Arrangements

When choosing a group of individuals for a photo with specific conditions, use the product rule to find the number of possibilities.

Signup and view all the flashcards

Product Rule

Used when you have to perform two or more procedures sequentially (AND). The total number of ways is the product of the ways to perform each individual procedure.

Signup and view all the flashcards

Sum Rule

Used when you have to perform one procedure or another (OR). The total number of ways is the sum of the ways to perform each individual procedure.

Signup and view all the flashcards

How many different ways are there to choose a letter and a number?

You have to select a letter AND a number. Use the product rule. Multiply the number of possibilities for each step (letter choices * number choices).

Signup and view all the flashcards

How many different dinner combinations are possible?

You can choose a meat dinner OR a fish dinner OR a vegetarian dinner. Use the sum rule. Add up the number of each type of dinner.

Signup and view all the flashcards

How many ways are there to order ice cream?

You have to choose a flavor AND a size AND a serving style. Use the product rule. Multiply the number of possibilities for each step (flavor choices * size choices * serving style choices).

Signup and view all the flashcards

What is the total number of candidates for a faculty position?

The candidate must be from Harvard OR UCLA. Use the sum rule. Add up the number of candidates from each university.

Signup and view all the flashcards

How many different ways are there to perform a procedure when you have to make multiple choices?

If you're performing multiple choices sequentially, use the product rule and multiply the possibilities for each step. If you're choosing one option out of several, use the sum rule and add the possibilities for each option.

Signup and view all the flashcards

How can you calculate the total number of possibilities when it involves multiple steps?

The product rule helps you calculate the total number of possibilities when you have to perform multiple steps sequentially (AND). The sum rule helps you calculate the total number of possibilities when you have to make a choice between different options (OR).

Signup and view all the flashcards

Applying the Product Rule in Counting Picture Possibilities

When arranging people in a picture, each person's placement affects the choices for the next. The product rule calculates the total possibilities by multiplying the number of choices for each position.

Signup and view all the flashcards

Applying the Sum Rule in Counting Picture Possibilities

When choosing which person to include in a picture (e.g., bride OR groom), the possibilities are separate. The sum rule adds the possibilities for each scenario.

Signup and view all the flashcards

Calculating Possibilities with Constraints

When there are specific conditions (like the bride and groom must be in the photo), the product rule calculates the possibilities for the restricted arrangement, then multiplies by the possibilities for the remaining positions.

Signup and view all the flashcards

Counting Possibilities with Exclusion

When one person cannot be chosen (e.g., the groom cannot be placed if only the bride is in the picture), the product rule calculates the number of possibilities for the restricted arrangement, then multiplies by the number of possible positions for the restricted person.

Signup and view all the flashcards

Calculating Total Possibilities with Alternatives

When there are multiple alternative arrangements (e.g., bride in the picture OR groom in the picture), the sum rule adds the total possibilities calculated for each alternative scenario.

Signup and view all the flashcards

Combining Product and Sum Rules in Counting

Complex counting problems may need both the product and sum rules. Use the product rule for sequential events within a scenario and the sum rule to combine the results of different scenarios.

Signup and view all the flashcards

Pigeonhole Principle

If you have more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon.

Signup and view all the flashcards

Generalized Pigeonhole Principle

If you have more balls than boxes, at least one box will contain at least the ceiling of the number of balls divided by the number of boxes.

Signup and view all the flashcards

Tree Diagram

A visual tool that shows all the possible outcomes of a series of events.

Signup and view all the flashcards

Committee Formation (Exact Number of Students)

Calculating the number of ways to form a committee with a specific number of students from a pool of students and teachers.

Signup and view all the flashcards

Committee Formation (At Least)

Calculating the number of ways to form a committee with at least a certain number of students, considering all possible combinations.

Signup and view all the flashcards

Counting: Pigeonhole Principles

A set of principles that helps to understand the distribution of items into categories.

Signup and view all the flashcards

Tree Diagram Advantage

A visual and intuitive way to list all possible outcomes of multiple choices.

Signup and view all the flashcards

Tree Diagram Disadvantage

Less effective when dealing with a large number of choices because the diagram becomes complex.

Signup and view all the flashcards

Outcome Sequences

The different possible results when an event happens multiple times.

Signup and view all the flashcards

Arrangements

The different ways objects can be ordered or placed.

Signup and view all the flashcards

Permutations

Arrangements where the order of objects matters.

Signup and view all the flashcards

Combinations

Selections where the order of objects doesn't matter.

Signup and view all the flashcards

Factorial (!)

The product of all positive integers less than or equal to a given number.

Signup and view all the flashcards

Restricted Arrangements

Arrangements where certain objects must be placed in specific positions.

Signup and view all the flashcards

Area Code Possibilities

The number of different area codes that can be created given specific rules.

Signup and view all the flashcards

Letter Arrangements

The number of different ways the letters in a word can be arranged.

Signup and view all the flashcards

Circular Permutation

A circular permutation is an arrangement of objects around a circle where the starting point is not considered. The number of circular permutations of n objects is (n-1)!.

Signup and view all the flashcards

Inclusion-Exclusion Principle

The inclusion-exclusion principle is a counting technique that helps to compute the number of elements in the union of two sets by adding the sizes of the two sets, then subtracting the size of their intersection.

Signup and view all the flashcards

Bit string

A bit string is a sequence of bits (0s and 1s). The length of a bit string is the number of bits in the string.

Signup and view all the flashcards

Counting bit strings

To count the number of bit strings that satisfy certain criteria, we can use principles like the product rule (multiplying the possibilities for each bit), and the inclusion-exclusion principle (handling overlapping cases).

Signup and view all the flashcards

Bit String Examples

Example 1: To count bit strings of length 8 starting with 1, we have one fixed bit (1) and 7 remaining bits, each with 2 possibilities, giving us 2^7 possibilities. Example 2: To count bit strings of length 8 that end with 00, 6 bits are free and 2 are fixed, giving us 2^6 possibilities. Example 3: To count bit strings of length 8 starting with 1 and ending with 00, 5 bits are free and 3 are fixed, giving 2^5 possibilities.

Signup and view all the flashcards

Application of the Inclusion-Exclusion Principle

The inclusion-exclusion principle helps in finding the total number of bit strings that meet at least one of the criteria (e.g., start with 1 or end with 00). It works by adding the number of bit strings meeting each criterion, then subtracting the number of bit strings that meet both criteria to avoid double counting.

Signup and view all the flashcards

Study Notes

Discrete Mathematics I for SE

  • Course title: EMath 1105
  • Course description: Discrete Mathematics I for students in the School of Engineering.
  • Topics covered in the course:
    • Combinatorial Analysis
    • The Basics of Counting, Permutations, and Combinations
    • Product rule:
      • Procedure 1 AND procedure 2.
      • n₁ ways to perform procedure 1
      • n₂ ways to perform procedure 2
      • Total ways: n₁ * n₂
    • Sum rule:
      • Procedure 1 OR procedure 2.
      • n₁ ways to perform procedure 1
      • n₂ ways to perform procedure 2
      • Total ways: n₁+n₂

Counting Examples

  • Example 1: How many ways can we label a chair if each label consists of both a letter and a number between 1 and 50, inclusive? Given 26 letters and 50 numbers.

    • Answer: 26 * 50 = 1300

  • Example 2: With 31 flavors of ice cream, 4 sizes of serving, and a choice of "cone" or "dish", how many different orders of ice cream are there?

    • Answer: 31 * 4 * 2 = 248

Counting Examples: More

  • Example 1: One position for a faculty job at CPU. The applicant must be from either Harvard (20 candidates) or UCLA (50 candidates).

    • Answer: Total candidates = 20 + 50 = 70

  • Example 2: A restaurant offers 18 dinners with meat, 10 with fish, and 5 vegetarian.

    • Answer: Total choices = 18+10+5 = 33

Counting Examples: Passwords

  • Passwords consist of character strings of 6 to 8 characters. Each character is either an upper case letter or a digit. Each password must contain at least one digit. How many passwords are possible

    • Find the total number of possible passwords by calculating the number of passwords with 6, 7 and 8 characters
    • Calculate P6, P7, and P8 if there is no constraint in each case.
    • Calculate the total number of possible outcomes without any digit restrictions.
    • Calculate the total number of passwords.
    • Calculate the difference between total # of possible options (without any digit constraint ) minus the total number of passwords without any digits.

  • Exclusions is #passwords without any digits

Counting Examples continued -

  • Example 1 (Rosen, section 4.1, question 38): There are 10 people (including the bride and groom). How many possibilities for a picture of 6 people if the bride must be in the picture?

    • Calculate the total number of possible positions the bride can be
    • Calculate the possibilities for the rest of the party via product rule considering available choices.
    • Find total possibilities using product rule.

  • Example 2 (Rosen, section 4.1, question 38). How many possibilities if bride and groom must both be in the picture?

    • Calculate the number of possibilities for bride and groom.
    • Calculate the possibilities for the remaining members using product rule
    • Find total possibilities using product rule.

  • Example 3 (Rosen, section 4.1, example 16): How many bit-strings of length 8 either begin with 1 or end with 00?

    • Count strings starting with 1.
    • Count strings ending with 00.
    • Count strings starting with 1 and ending with 00
    • Apply the inclusion-exclusion principle
    • Find the total number of bit strings.

Exercises, and Answers

  • Exercise and answers are also documented for exercises as outlined

Permutations

  • Formula: P(n,r) = n! / (n-r)!

Combination

  • Formula: C(n, r) = n! / (r! * (n-r)!)

Circular Seating

  • Number of ways to seat n people around a circular table = (n-1)!

Principle of Inclusion-Exclusion (PIE)

  • Formula: (n₁ + n₂ - m)
    • n₁: ways for procedure 1
    • n₂: ways for procedure 2
    • m: ways of doing both procedure 1 and procedure 2 equally.

Tree Diagrams

  • A systematic diagram showing all possible sequences of events in a branching format.

Probability

  • Example 1: How many possible outcomes can occur from rolling a six-sided die four times?

    • Answer: 1296
    • Possible outcomes by multiplication.

  • Example 2: How many possible arrangements are there of four instruments (John, Jim, Jay, Jack) if John and Jim can play all four, but Jay and Jack can only play piano and drums?

    • Answer: 24
    • Calculated using product rule and accounting for limited instruments per person

Additional problems:

  • Telephone area codes in the U.S. (digits 2-9, 0/1, 1-9)
  • Letter arrangements for words (fluke, propose, Mississippi, arrange)
  • Seating arrangements for 8 people (with and without constraints)
  • Handshakes between 20 people

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

Chapter 4 Combinatorial Analysis PDF

Description

Explore the foundational concepts of Discrete Mathematics as part of EMath 1105 for engineering students. This quiz covers topics such as combinatorial analysis, counting principles, permutations, and combinations through practical examples. Test your understanding of the product and sum rules in various counting scenarios.

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser