commit 77a1eed4809c17647d0940c14f73052a7b66c5b4
parent e14f9061d8730b24cd32b04df92bce8e3255ffa6
Author: Andrew <andrewlaack1@gmail.com>
Date: Mon, 23 Sep 2024 20:27:16 -0500
Took notes on discrete
Diffstat:
4 files changed, 47 insertions(+), 2 deletions(-)
diff --git a/Algorithms.md b/Algorithms.md
@@ -37,6 +37,14 @@ Ch 3 (state analysis):
- [StateAnalysis](StateAnalysis.md)
- [StirlingsFormula](StirlingsFormula.md)
+Ch 4 (graphs):
+ - Graph
+ - Walk
+ - Path
+ - Cycle
+ - Connected
+ - Tree
+
#### Intro To Algorithms (MIT)
L1:
diff --git a/BijectiveProof.md b/BijectiveProof.md
@@ -0,0 +1,19 @@
+:proofs: :discrete:
+# Bijective Proof
+
+Ch 6.3
+
+## Notes
+
+**Definition:** A bijective proof is a proof where we prove the compared sets can be represented as a bijective function and thus have the same cardinality.
+
+
+Example:
+
+Prove $\binom{n}{k} = \binom{n}{n-k}$
+
+Proof:
+
+$\binom{n}{k}$ describes all combinations of length k from a set of length n. Let's now defined a function upon these combinations. This function is f : X -> Y where X is the set of all combinations of length k made from the set with cardinality n. Let's also define Y as the complement of the input x with respect to the original set of length n. We know this function is a bijection because all combinations have a unique complement and all complements are mapped to, because of how we defined our function. $\blacksquare$
+
+I could improve upon this proof by stating Y is the set of all combinations of n with length n - k.
diff --git a/CombinatorialProof.md b/CombinatorialProof.md
@@ -0,0 +1,16 @@
+:logic: :discrete: :proofs:
+# Combinatorial (Counting) Proofs
+
+Ch 6.3
+
+## Notes
+
+**Definition:** A combinatorial proof is a proof that shows we are counting the same set and thus they are equivalent.
+
+Example:
+
+Prove That $\binom{n}{k} = \binom{n}{n-k}$
+
+Proof:
+
+Consider n choose k. This describes all combinations of length k of a set length n. This computation can be thought of inversely as well. Consider, each of these combinations has a complement where we have all elements not selected in the current combination. If we assume A is the current combination $\bar A$ is all elements of the set N (|N| = n), not in A. We know the set of all possible $\bar A$ is just all non-selected elements and thus has the same cardinality as the set A because we are describing the **same thing from two sides**. $\blacksquare$
diff --git a/DiscreteMath.md b/DiscreteMath.md
@@ -129,8 +129,8 @@ Unit 6.3 (Permutations and Combinations)
- [RPermutation](RPermutation.md)
- [Combination](Combination.md)
- [RCombination](RCombination.md)
- - CombinatorialProof
- - BijectiveProof
+ - [CombinatorialProof](CombinatorialProof.md)
+ - [BijectiveProof](BijectiveProof.md)
Unit 6.4 (Binomial Coefficient & Identities)
- [BinomialCoefficient](BinomialCoefficient.md)
@@ -139,3 +139,5 @@ Unit 6.4 (Binomial Coefficient & Identities)
- [Binomial](Binomial.md)
Unit 6.5 (Generalized Permutations & Combinations)
+ - Distinguishable
+ - Indistinguishable
