DISCRETE STRUCTURES FINALSSSSS

Probability

A measure of the likelihood that an event will occur.

Discrete Probability

A branch of probability that deals with countable outcomes such as coin tosses, dice rolls, and card draws.

Experiment

A process that produces one or more outcomes.

Outcome

The result of a probability experiment.

Sample Space (S)

The set of all possible outcomes of an experiment.

Event

A subset of the sample space.

Probability Formula

P(A) = n(A) / n(S), where n(A) is the number of favorable outcomes and n(S) is the total number of outcomes.

Simple Event

An event that consists of only one outcome.

Compound Event

An event that consists of more than one outcome.

Complement of an Event

The event that an event A does not occur.

Complement Formula

P(A') = 1 − P(A)

Union of Events

The probability that event A or event B (or both) occurs.

Intersection of Events

The probability that both event A and event B occur.

Venn Diagram

A diagram used to visually represent events and their relationships

Independent Events

Events where the occurrence of one does not affect the occurrence of the other.

Formula for Independent Events

P(A ∩ B) = P(A) × P(B

Conditional Probability

The probability of an event A occurring given that event B has already occurred

Conditional Probability Formula

P(A|B) = P(A ∩ B) / P(B)

Probability Tree

A diagram used to represent all possible outcomes of a multi-step experiment.

Applications in Computer Science

Uses of probability in areas such as network reliability, machine learning, cryptography, and algorithm analysis

Applications in Business and Daily Life

Uses of probability in risk analysis, quality control, insurance, and forecasting.

Recursive Definition

A way of defining something using itself, in a step-by-step manner.

Recursion

A process or rule that is repeated.

A process or rule that is repeated.

The initial value or starting point in a recursive definition.

Recursive Rule

A rule that defines subsequent terms using previous terms.

Counting Numbers (Recursive Example)

Numbers that can be defined recursively starting from a base case and building upward.

Even Numbers

Numbers that can be defined recursively by adding 2 to the previous term.

Factorial

A function defined recursively as n! = n(n−1)!

Fibonacci Sequence

A sequence where each term is the sum of the two preceding terms.

Recursive Sequence Example

Given a₁ = 3 and aₙ = aₙ₋₁ + 4, each term is found by adding 4 to the previous term.

Key Rule in Recursion

Always start with the base case before applying the recursive rule.

Permutation

The number of ways to arrange $n$ distinct objects where the order matters.

Combination

The number of ways to choose $r$ objects from $n$ where the order does not matter.

Base Case

The first known value or the starting point in a recursive definition that stops the recursion.

Recurrence Relation / Recursive Formula

A formula used in math and computer science to define each term of a sequence based on its preceding term(s).

Previous Term(s)

The specific value or values needed from the sequence to compute the next term in a recursive process.

Product Rule (Multiplication Rule)

Sum Rule (Addition Rule)

Permutation Formula (nPr) =

The specific mathematical formula used to calculate the permutations of $n$ objects taken $r$ at a time.

Negation

A logical operation (often represented by "NOT") that reverses the truth value of a given proposition.

Undefined Sequence

The logical result or error that occurs when a recursive definition does not have a base case to stop it.

0! = 1

Base case of factorial

Increasing nonlinear sequence

Recursive rule of factorial

720

Arranging 3 students from 10

120

Selecting 3 students from 10

6

Ways to arrange "ABC"

120

Arranging 5 people in a row

1 and 1

Fibonacci sequence starts with

Undefined Sequence

Missing base case results in

24

4!