Discrete math Flashcards Set

Here are some notes on discrete math, based on the sources you provided:

• Discrete Math Overview

  • Discrete math is essential for computer science and everyday applications.

  • It involves counting/combinatorics to discover patterns and understand the complexity of objects.

• Graphs

  • Graphs represent pairwise relations with entities as vertices and relations as edges.

  • For planar graphs, Euler's formula applies: v - e + f = 2, where v is vertices, e is edges, and f is faces.

  • A face is an area you can move within without crossing any edge, specifically for planar graphs.

• Summation and Product Notations

  • Summation notation example: Σᵢ₌₀⁹ 2 = 2 + 2 + 2 + ... + 2.

  • General forms for summations and products are provided.

  • Distributive property: Σ cf(i) = c Σ f(i).

• Product Rule

  • The number of permutations on n objects is n!.

• Anagrams

  • To find the number of anagrams, consider that if some elements are identical, it leads to overcounting.

• Sets

  • A set is an unordered collection of distinct elements.

  • Sets can be finite or infinite.

  • The cardinality of a finite set S, denoted as |S|, is the number of elements in it. For example, if S = {x, y, z}, then |S| = 3.

  • Examples of infinite sets include the set of positive integers and the set of integers.

  • The number of subsets of a set S with n elements is 2ⁿ. This can be determined by considering each element and choosing whether or not it is in a subset, leading to 2 options for each element.

• Functions

  • A function f: X -> Y means that for every x in X, there exists exactly one y in Y such that f(x) = y.

  • A function is "onto" if for every y in Y, there exists an x in X such that f(x) = y.

  • A bijection is a function that is both one-to-one and onto; if f: X -> Y is a bijection, then |X| = |Y|.

• Counting with Bijections

  • Establishing a bijection can be useful for counting the number of elements in a set.

  • There are 2ⁿ n-bit words.

  • The number of subsets of a set S = {a₁, ..., aₙ} is 2ⁿ.

• Formulas

  • Number of permutations: n!

  • Number of k-permutations (n > k): n!/(n-k)!

  • Number of unordered pairs: (n choose 2)

  • Number of k-combinations (n > k): (n choose k)

  • Number of n-bit words: 2ⁿ

  • Number of subsets of S, where |S| = n: 2ⁿ

  • Number of subsets of size k: (n choose k)

  • Number of k letter words, alphabet size n: n^k

Here are additional notes on discrete math, based on the sources:

• Logic and Proofs

  • To prove a function is one-to-one, show that if f(x₁) = f(x₂), then x₁ = x₂.

  • This method relies on the logical equivalence of "A implies B" and "not B implies not A".

• Implication Properties

  • If P is true and (P implies Q) is true, then Q is true.

  • To prove (P implies Q), proving (¬Q implies ¬P) is true (contrapositive).

  • To prove P, show that (¬P implies False) (contradiction).

  • If (P implies Q) and (Q implies R), then (P implies R) (transitivity).

• Proof by Contradiction

  • An example of proof by contradiction is demonstrating that the square root of 2 is irrational. This involves assuming the opposite (that it is rational) and showing that this assumption leads to a contradiction.

  • Another proof by contradiction shows that there are infinite prime numbers.

• Pascal's Triangle

  • P(n, k) represents the number in row n, position k (both starting at 0).

  • P(n, k) = P(n - 1, k - 1) + P(n - 1, k).

  • P(n,k) is equivalent to (n choose k).

• Functions

  • Examples of functions include functions that are onto, one-to-one, and bijections.

  • Onto: For every y in Y, there exists an x in X such that f(x) = y.

  • One-to-one: No x₁ and x₂ exist where f(x₁) = f(x₂) unless x₁=x₂.

  • Bijection: If f: X -> Y is a bijection, then |X| = |Y|.

• Counting Techniques

  • When calculating the number of ways to perform tasks, consider whether order and repetition are relevant.

  • Bijections can be used for counting. For instance, the number of n-bit words is 2ⁿ, which relates to the number of subsets of a set with n elements.

• Discrete Math Themes

  • Discrete math and counting encourage a specific way of thinking and are essential for algorithms.

• Sets

  • If a set S is finite, the cardinality (size) of S is the number of elements in it, denoted by |S|. For example, S = {x, y, z}, |S| = 3.

  • The number of subsets of S, where |S| = m, is 2ᵐ.

• Summation and Product Notation

  • Σᵢ₌ₐᵇ f(i) = f(a) + f(a+1) + ... + f(b).

  • Πᵢ₌ₐᵇ f(i) = f(a) f(a+1) ... * f(b).

  • Σ cf(i) = c Σ f(i) (distributive property).

• Inclusion/Exclusion

  • When counting, be aware of potential overcounting, which can occur when elements are not distinct.