Discrete Math - Counting Techniques

chat am i cooked

Product Rule

USED TO COUNT THE UMBER OF WAYS TO PERFORM A SERIES OR TASK

• M ways to do the first task

• N ways to do the second task

• M * N ways to do the procedure

Look for an implied AND!!

Sum Rule

USED TO COUNT THE NUMBER OF WAYS TO PERFORM A SINGLE TASK

• Task can be done in M ways

  • OR

• Task can be done N ways

Look for an implied OR!!

M and N DONT SHARE TASKS!!

Inclusion-Exclusion Principle

USED TO COUNT THE NUMBER OF ELEMENTS BELONGING TO A SET A OR B

• Task can be done in M ways

  OR

• Task can be done in N ways

Look for an implied OR, except this time M & N SHARE TASKS!!

Permutations with INDISTINGUISHABLE Objects

MULTIPLE TYPES OF OBJECTS, OBJECTS ARE INDISTINGUISHABLE

n! / n1! *…..n^k! IF U GET MAH DRIFTFTTFT

The Pigeonhole Principle

NUMBER OF OBJ’S DISTRIBUTED IN A BOX TO GUARANTEE AT LEAST ONE BOX HAS ONE OBJECT

k = boxes

k+1 = # of objects to distribute

The GENERALIZED Pigeonhole Principal

MINIMUM NUMBER OF OBJ’S GUARANTEED IN A BOX

N = objects

k = boxes

The Ceiling of N/k