CSM 166 Lecture One: Counting Principles
70 Questions
0 Views

CSM 166 Lecture One: Counting Principles

Created by
@SpontaneousGnome

Podcast Beta

Play an AI-generated podcast conversation about this lesson

Questions and Answers

How many students at Prempeh College like neither mathematics, nor theology, nor accounting?

15

What is the recursive formula for the number of bit strings of length n with no adjacent 0s?

a_n = a_{n-1} + a_{n-2} for n ≥ 2

How many good bit strings exist for n=3?

5

How many policyholders are young, female, and single in the auto insurance company?

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

What defines a graph G?

<p>A graph G is defined as an ordered pair (V, E), where V is the set of vertices and E is the set of edges.</p> Signup and view all the answers

What is a loop in graph theory?

<p>An edge e is called a loop if both endpoints coincide.</p> Signup and view all the answers

What is a complete graph?

<p>A complete graph K_n is a graph with n vertices where every pair of distinct vertices is adjacent.</p> Signup and view all the answers

Describe a bipartite graph.

<p>A bipartite graph Km,n has vertices divided into two sets, and edges only connect vertices from different sets.</p> Signup and view all the answers

What is the adjacency matrix of a graph?

<p>The adjacency matrix A is an n × n matrix where a_ij represents the number of edges between vertices u_i and u_j.</p> Signup and view all the answers

How many ways can a student complete the test if every question must be answered?

Signup and view all the answers

How many ways can a student complete the test if questions can be left unanswered?

Signup and view all the answers

How many license plates can be made using either three digits followed by three uppercase English letters or three uppercase English letters followed by three digits?

Signup and view all the answers

In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people if the bride must be in the picture?

Signup and view all the answers

In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people if both the bride and groom must be in the picture?

Signup and view all the answers

In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people if exactly one of the bride and the groom is in the picture?

Signup and view all the answers

How many students are there in the discrete mathematics class if there are 38 computer science majors, 23 mathematics majors, and 7 joint majors?

Signup and view all the answers

How many balls must a woman select from a bowl containing 10 red balls and 10 blue balls to ensure she has at least three balls of the same color?

Signup and view all the answers

How many students must there be to guarantee that there are two students with the same professor who earned the same final examination score?

Signup and view all the answers

How many different permutations of the letters from the word SUCCESS can be formed?

Signup and view all the answers

How many four-letter passwords can be made from the capital letters A to Z if a letter can be repeated?

Signup and view all the answers

How many ways can six professors give a final exam score between 0 and 100 such that at least one student has the same score as another?

Signup and view all the answers

What is the fundamental counting principle concerned with?

<p>Determining the number of different ways of arranging objects in patterns or carrying out sequences of tasks.</p> Signup and view all the answers

How many different bit strings of length two can be formed?

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

What does the sum rule state?

<p>If sets A and B are disjoint, then the number of ways to do one of the tasks is A + B.</p> Signup and view all the answers

In how many ways can you select either a queen or a six from a deck of 52 cards?

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

In the extended sum rule, what does it indicate?

<p>If A1, A2, A3, ..., An are pairwise disjoint sets, then A1 ∪ A2 ∪ A3 ∪ ... ∪ An = A1 + A2 + A3 + ... + An.</p> Signup and view all the answers

How many ordered pairs of integers (x, y) are there such that 0 < xy ≤ 5?

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

What does the product rule state?

<p>The product rule states that the number of ways to perform n tasks is A1 ⋅ A2 ⋅ ... ⋅ An.</p> Signup and view all the answers

How many different two-digit numbers can be formed using the digits 1 to 9 without repetition?

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

How many different bit strings of length five can start with three 0's or two 1's?

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

What is the formula used in the subtraction rule?

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

Using the generalized pigeonhole principle, how many students are needed to ensure at least six receive the same grade?

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

What is the minimum number of socks to guarantee a matching pair from three colors?

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

How many cards must be selected to guarantee at least three cards of the same suit?

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

How many ways can a student select one course to meet the science requirement from 5 biology, 4 physics, or 6 chemistry courses?

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

In a multiple choice test with 10 questions and four possible answers for each, how many total answer combinations exist?

<p>4^10 or 1,048,576</p> Signup and view all the answers

What is the degree of vertex a?

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

What is the degree of vertex b?

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

What is the degree of vertex c?

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

What is the degree of vertex d?

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

What is the degree of vertex e?

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

What is the degree of vertex f?

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

What is the degree of vertex g?

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

A bipartite graph can contain cycles of odd length.

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

Match the following terms with their definitions:

<p>Graph Isomorphism = A bijection between the vertex sets of two graphs that preserves adjacency. Bipartite Graph = A graph whose vertex set can be divided into two disjoint sets. Trail = A walk in which all edges are distinct. Path = A walk in which all vertices are distinct.</p> Signup and view all the answers

Define a walk in the context of graph theory.

<p>An alternating sequence of vertices and edges.</p> Signup and view all the answers

What is a closed walk?

<p>A walk W is called closed if v0 = vk.</p> Signup and view all the answers

What defines a trail in graph theory?

<p>A trail is defined as having pairwise distinct edges.</p> Signup and view all the answers

What is a path in graph theory?

<p>A path is defined as having pairwise distinct vertices.</p> Signup and view all the answers

What characterizes a cycle in graph theory?

<p>A cycle is a closed walk where its internal vertices are pairwise distinct.</p> Signup and view all the answers

A graph G is disconnected if it is possible to find a (x, y)-walk for any pairs x, y of vertices.

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

What is a tree in graph theory?

<p>A tree is a connected acyclic graph.</p> Signup and view all the answers

What is a rooted tree?

<p>A rooted tree has a vertex designated as the root.</p> Signup and view all the answers

What is Boolean Algebra primarily used for?

<p>Describing relationships between inputs and outputs</p> Signup and view all the answers

What does the AND gate do?

<p>The AND gate gives a high output only if all its inputs are high.</p> Signup and view all the answers

How is the output of the OR gate determined?

<p>The OR gate gives a high output if one or more of its inputs are high.</p> Signup and view all the answers

What does a NOT gate do?

<p>The NOT gate inverts the value of its input.</p> Signup and view all the answers

What is the identity element for the operation + in Boolean algebra?

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

What is a truth table?

<p>A truth table is a table that contains all possible values of logical variables in a Boolean expression.</p> Signup and view all the answers

The set B must contain only one element.

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

What is a tautology in Boolean logic?

<p>An expression that is always true</p> Signup and view all the answers

What characterizes an acyclic graph?

<p>An acyclic graph contains no cycles.</p> Signup and view all the answers

What operation does the '+' symbol represent in Boolean algebra?

<p>Boolean sum</p> Signup and view all the answers

Define the dual of a Boolean expression.

<p>The dual is obtained by interchanging Boolean sums and Boolean products and interchanging 0s and 1s.</p> Signup and view all the answers

The null element for the operation * in Boolean algebra is _____.

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

Match the following Boolean laws with their descriptions:

<p>Complementarity = a + a' = 1 Idempotent = a + a = a Involution = (a')' = a Distributive = a + (b * c) = (a + b) * (a + c)</p> Signup and view all the answers

What is the absorption theorem in Boolean algebra?

<p>X + X*Y = X</p> Signup and view all the answers

How many different Boolean functions of degree 3 are there?

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

De Morgan's laws state that (a + b)' = a' * b'.

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

What are the values of the XOR operation for true and false?

<p>1, 1 for true and false; 0 for true and true or false and false</p> Signup and view all the answers

Study Notes

Counting Principles

  • Counting is the process of determining arrangements of objects or sequences of tasks.
  • For small cases like bit strings of length two, enumeration can be used (00, 01, 10, 11), resulting in four arrangements.
  • For larger cases, such as bit strings of length fifty, more efficient counting methods are necessary: the Sum Rule and the Product Rule.

The Sum Rule

  • If sets A and B are disjoint, the total number of ways to choose from either set is given by A ∪ B = A + B.
  • Example: Selecting either a queen or a six from a standard deck of cards allows for 4 ways for a queen and 4 for a six, totaling 8 ways.
  • In cases with overlapping elements, the calculation is adjusted by subtracting the intersection.

Extended Sum Rule

  • For multiple disjoint sets A1, A2, ..., An, the number of ways to choose is A1 ∪ A2 ∪ ... ∪ An = A1 + A2 + ... + An.
  • Example: Counting ordered pairs (x, y) such that 0 < xy ≤ 5 involves computing combinations for respective values of k from 1 to 5.

The Product Rule

  • The product rule states that for A choices for one task combined with B for another, the total arrangements are A × B.
  • Example: A car purchasing scenario with 5 exterior color choices and 3 interior options leads to 15 combinations (5 × 3).

Application of Both Rules

  • Example: Counting bit strings of length five starting with three 0's or two 1's reveals 12 total configurations through addition of potential combinations.
  • Example: For license plates consisting of letters and digits, the sum of possible configurations for two formats is calculated (A and B method).

Subtraction and Division Rules

  • The Subtraction Rule defines the overlap between two tasks as |A∪B| = |A| + |B| - |A∩B| to account for shared outcomes.
  • The Division Rule applies when dividing multiple options into equal groups, yielding n/d possible outcomes.

The Pigeonhole Principle

  • States that if there are more items than containers, at least one container must contain more than one item.
  • Generalized version states that if n objects are distributed among k boxes, at least one box has at least ⌈n/k⌉ items.

Pigeonhole Principle Examples

  • Minimum students in a class to ensure at least six receive the same grade is calculated as n = k(r - 1) + 1 where k=5 and r=6, yielding 26.
  • For socks of three colors, taking four socks guarantees at least one matching pair due to pigeonhole application.

Exercises

  • Various counting problems are presented, including selections of courses and arrangements of students, highlighting practical applications of the counting principles discussed.
  • Specific scenarios challenge students to apply the Sum Rule, Product Rule, and Pigeonhole Principle in different contexts.### Fundamental Counting Principles: Permutations and Combinations
  • Permutations refer to ordered arrangements of a set of distinct objects.
  • The total number of permutations of an n-set is given by n! (n factorial), which equals n × (n-1) × (n-2) × ... × 2 × 1.
  • An r-permutation of a set with n distinct elements can be calculated using the formula: P(n, r) = n(n - 1)(n - 2)...(n - r + 1).
  • Example: For a saleswoman starting a trip in a specified city visiting 7 others, the number of arrangements is 7! = 5040.
  • Example: Selecting officers (president, vice, secretary, treasurer) from 20 people involves permutations without replacement: P(20, 4) = 20!/(20-4)! = 116280.
  • Example: In a race with 8 runners, the number of ways to award gold, silver, and bronze medals is given by P(8, 3) = 336.

Combinations

  • Combinations represent unordered selections of r objects from a set of n distinct objects, calculated using the formula: C(n, r) = n!/(r!(n - r)!).
  • Example: From 22 soccer players, the number of ways to select 11 for the starting lineup is C(22, 11) = 705,432.
  • Example: Formulating a committee with 3 from mathematics and 4 from computer science departments (9 math and 11 CS faculty) yields 27,720 combinations (C(9, 3) × C(11, 4)).

Counting with and without Replacement

  • When repetition is allowed in arrangements, the total number of ways increases.
  • Permutations with replacement: If n objects are taken k at a time, the formula is n^k.
  • Combinations with replacement: The formula is C(n + k - 1, k) = (n+k-1)!/(k!(n-1)!).
  • Example: Finding the number of solutions for x1 + x2 + x3 = 11 with non-negative integers equals the combinations with repetition: C(13, 11) = 78.

Indistinguishable Objects

  • Theorem for permutations of indistinguishable objects: Total permutations of n objects comprising n1 of one type, n2 of another type, etc., is n!/(n1!n2!...nk!).
  • Example: The arrangements of 'SUCCESS' have 420 distinct strings calculated as 7!/(3!2!1!1!) due to indistinguishable letters.

Binomial Theorem

  • The Binomial Theorem expresses (x + y)^n as the sum of terms involving binomial coefficients: (n choose k) x^(n-k) y^k.
  • Example: Expanding (4x + 5)^3 gives coefficients derived from binomial formula resulting in the simplified polynomial.

Inclusion-Exclusion Principle

  • The principle calculates the size of union sets accounting for overlap: |A ∪ B| = |A| + |B| - |A ∩ B|.
  • For three sets, the formula adjusts for their intersections: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |C ∩ A| + |A ∩ B ∩ C|.
  • Example: For 40 students sampled regarding subjects liked, the number of students liking at least one subject was derived using provided counts and the inclusion-exclusion formula.

Recurrence Relations

  • Sequences satisfy specific recurrence relations and are defined by initial conditions.
  • Example: For counting bit strings with no adjacent 0's, the relation is defined as a0 = 1, a1 = 2, a2 = 3, and for n ≥ 2, an = an-1 + an-2, resembling Fibonacci sequence growth.

Exercises

  • Formulate counts relating to specific characteristics in a set of insurance policyholders.
  • Utilize polynomial expansions for practice with binomial expressions and apply the patterns observed in inclusion-exclusion scenarios.### Graph Theory Basics
  • A graph ( G ) is defined as an ordered pair ( (V, E) ) where ( V ) represents the vertices and ( E ) represents the edges.
  • The vertex set ( V(G) ) must be a non-empty set, while the edge set ( E(G) ) can contain various connections among those vertices.
  • An incidence function ( f_G : E \to {{u,v} : u,v \in V} ) assigns each edge an unordered pair of its endpoints.

Example of a Graph

  • In a graph with vertices ( V = {a, b, c, d, e, f, g} ) and edges ( E = {e_1, e_2, \ldots, e_8} ):
    • The incidence function illustrates various connections, e.g., ( f(e_1) = {a, b} ).

Types of Edges

  • An edge is a loop if both endpoints are the same (( f_G(e) = {u} )).
  • An edge is a link if endpoints are distinct (( f_G(e) = {u, v} )).
  • Parallel edges share the same endpoints, meaning ( f_G(e_1) = f_G(e_2) ) for distinct edges.

Simple Graph

  • A simple graph contains no loops or parallel edges, ensuring each connection between vertices is unique.

Directed Graph (Digraph)

  • A digraph ( D ) is represented as ( (V, A) ) where ( A ) consists of directed edges (arcs).
  • Each arc relates to an ordered pair of its endpoints via an incidence function ( f_D ), distinguishing initial and terminal vertices.

Terminology in Graph Theory

  • Adjacent vertices: Vertices ( u ) and ( v ) are adjacent if an edge between them exists.
  • Incident edges: An edge ( uv ) is said to be incident to its endpoints ( u ) and ( v ).
  • Degree: The degree ( \text{deg}_G(u) ) counts the incident edges at vertex ( u ), with loops counted twice. Isolated vertices have a degree of 0, and a pendant/leaf vertex has a degree of 1.

Special Graph Types

  • A complete graph ( K_n ) has ( n ) vertices where every pair of vertices is connected.
  • A complete bipartite graph ( K_{m,n} ) splits its vertex set into two disjoint subsets, connecting every vertex in one subset to every vertex in the other.

Cycles and Paths

  • A cycle ( C_n ) consists of ( n ) vertices connected in a circular manner, forming ( n ) edges.
  • A path ( P_n ) consists of ( n+1 ) vertices linked in a linear sequence, forming ( n ) edges.

Subgraphs

  • A graph ( H ) is a subgraph of ( G ) if it includes a subset of the vertices and edges of ( G ).

Matrix Representations

  • Incidence matrix: An ( n \times m ) matrix representation defines relationships between vertices and edges based on incidence.
  • Adjacency matrix: An ( n \times n ) matrix counts the edges between each pair of vertices.

Degree Sequence

  • The degree sequence lists the degrees of all vertices in non-decreasing order, revealing the connectivity of the graph.

Bipartite Graphs and 2-Colorability

  • A graph is bipartite if its vertices can be split into two sets with no edges connecting vertices within the same set.
  • A proper 2-vertex-coloring allows vertices to be colored with two colors so that no two adjacent vertices share the same color.
  • Bipartiteness ensures that the graph contains no odd-length cycles.

Studying That Suits You

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

Quiz Team

Related Documents

Discrete Maths II Lecture Notes PDF

Description

Explore the Fundamental Counting Principles in this CSM 166 lecture. Learn how to determine the number of different arrangements of objects and the sequences of tasks. This foundational topic is crucial for understanding more advanced combinatorial concepts.

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser