vijayshukla's blog

  Permutations and Combinations Permutations and combinations are fundamental concepts in combinatorics that deal with arranging and selecting objects. 1. Permutations (Order Matters) A permutation is an arrangement of objects in a specific order. Formula for Permutations The number of ways to arrange r r r objects from a set of n n n distinct objects: P ( n , r ) = n ! ( n − r ) ! P(n, r) = \frac{n!}{(n-r)!} P ( n , r ) = ( n − r )! n ! ​ Example of Permutation How many ways can 3 people (A, B, and C) be arranged in 2 seats? P ( 3 , 2 ) = 3 ! ( 3 − 2 ) ! = 3 ! 1 ! = 3 × 2 × 1 1 = 6 P(3,2) = \frac{3!}{(3-2)!} = \frac{3!}{1!} = \frac{3 \times 2 \times 1}{1} = 6 P ( 3 , 2 ) = ( 3 − 2 )! 3 ! ​ = 1 ! 3 ! ​ = 1 3 × 2 × 1 ​ = 6 Arrangements: (AB, BA, AC, CA, BC, CB) 2. Combinations (Order Doesn’t Matter) A combination is a selection of objects where order does not matter. Formula for Combinations The number of ways to choose r r r objects from n n n distinct objects: C ( n , r ...

 

 Eulerian and Hamiltonian graphs are two important concepts in graph theory related to traversing graphs in specific ways. Eulerian Graphs A graph is Eulerian if it contains an Eulerian circuit —a closed path that visits every edge exactly once. Eulerian Circuit (or Eulerian Cycle) A cycle (closed path) that traverses every edge exactly once and returns to the starting vertex. Eulerian Path (or Eulerian Trail) A path that visits every edge exactly once but does not necessarily return to the starting vertex. Eulerian Graph Theorem A connected graph has an Eulerian Circuit if and only if all vertices have even degrees . A connected graph has an Eulerian Path if and only if exactly zero or two vertices have odd degrees . Example of Eulerian Graph A simple example is a cycle graph where each vertex has an even degree. Hamiltonian Graphs A graph is Hamiltonian if it contains a Hamiltonian cycle —a closed path that visits every vertex exactly once. Hamiltonian Cycle A cycle (closed p...

  Example of Planar Graphs A planar graph is a graph that can be drawn on a plane without any edges crossing each other. If a graph can be redrawn to remove all crossings, it is planar . Example 1: Triangle Graph ( K 3 K_3 K 3 ​ ) A simple triangle graph with three vertices A , B , C A, B, C A , B , C and three edges: Graph Representation css Copy Edit A / \ B - --C Since this graph can be drawn without edges crossing, it is planar . Example 2: Square with a Diagonal Consider a square with four vertices A, B, C, D , and an added diagonal AC : Graph Representation less Copy Edit A ----- B | \ | | \ | D ----- C This graph is still planar because no edges need to cross. Example 3: Complete Graph K 4 K_4 K 4 ​ (Planar Form) A complete graph on four vertices (A, B, C, D) with every vertex connected to every other vertex. Normally, K 4 K_4 K 4 ​ has a crossing, but it can be drawn without crossing edges by rearranging its layout: Planar Dr...

  Examples of Bipartite Graphs A bipartite graph is a graph whose vertices can be divided into two disjoint sets U U U and V V V such that every edge connects a vertex in U U U to a vertex in V V V . No two vertices within the same set are adjacent. Example 1: Simple Bipartite Graph Consider a graph with the following sets: Set U U U = {A, B, C} Set V V V = {1, 2, 3} Edges: (A,1), (A,2), (B,2), (B,3), (C,1), (C,3) Graph Representation less Copy Edit A B C | / \ | 1 2 3 Here, edges only exist between elements in U U U and V V V , making it bipartite. Example 2: Real-Life Application - Job Assignment Workers : W 1 , W 2 , W 3 W_1, W_2, W_3 W 1 ​ , W 2 ​ , W 3 ​ Tasks : T 1 , T 2 , T 3 , T 4 T_1, T_2, T_3, T_4 T 1 ​ , T 2 ​ , T 3 ​ , T 4 ​ Edges represent possible assignments (who can do which task): Graph Representation markdown Copy Edit W1 W2 W3 | / \ | T1 T2 T3 T4 Since edges only go between workers and tasks, t...

  Examples Related to Propositions A proposition is a declarative statement that is either true (T) or false (F) but not both. 1. Simple Propositions Example 1: "The sun rises in the east." ( True ) Example 2: "5 is a prime number." ( False ) 2. Compound Propositions Compound propositions are formed using logical connectives: AND (∧), OR (∨), NOT (¬), IMPLIES (→), BICONDITIONAL (↔) Example 1: Conjunction (AND, ∧) Statement: "It is raining AND it is cold." Symbolic Form: P ∧ Q P \wedge Q P ∧ Q Truth Table: P (Raining) Q (Cold) P ∧ Q P \wedge Q P ∧ Q T T T T F F F T F F F F Example 2: Disjunction (OR, ∨) Statement: "It is Monday OR it is Tuesday." Symbolic Form: P ∨ Q P \vee Q P ∨ Q Truth Table: P (Monday) Q (Tuesday) P ∨ Q P \vee Q P ∨ Q T T T T F T F T T F F F Example 3: Implication (→) Statement: "If it rains, then the ground is wet." Symbolic Form: P → Q P \rightarrow Q P → Q Truth Table: P (Rains) Q (Ground Wet) P → Q P \r...

  Example of Inference in Logic Scenario: Let’s say we have the following premises: Premise 1: If it rains, the ground will be wet. (Symbolically: P → Q P \rightarrow Q P → Q ) Premise 2: It is raining. (Symbolically: P P P ) Inference (Modus Ponens): From these premises, we can logically infer: Conclusion: The ground will be wet. (Symbolically: Q Q Q ) Explanation: This follows the Modus Ponens rule of inference, which states: If  P → Q  and  P  is true, then  Q  must also be true. \text{If } P \rightarrow Q \text{ and } P \text{ is true, then } Q \text{ must also be true.} If  P → Q  and  P  is true, then  Q  must also be true. Generalization: Inference in logic is the process of deriving new statements from given premises using valid rules such as: Modus Ponens : P → Q , P ⇒ Q P \rightarrow Q, P \Rightarrow Q P → Q , P ⇒ Q Modus Tollens : P → Q , ¬ Q ⇒ ¬ P P \rightar...

  Problem: Let L L L be a lattice with the elements a , b , c a, b, c a , b , c , where the meet ( ∧ \wedge ∧ ) and join ( ∨ \vee ∨ ) operations satisfy the following conditions: a ∨ b = b a \vee b = b a ∨ b = b a ∧ c = a a \wedge c = a a ∧ c = a b ∧ c = c b \wedge c = c b ∧ c = c Questions: Show that a ≤ b a \leq b a ≤ b in the lattice order. Show that c ≤ b c \leq b c ≤ b in the lattice order. Can you determine the greatest and least elements of this lattice, if they exist? Hints: Recall that in a lattice, x ≤ y x \leq y x ≤ y if and only if x ∨ y = y x \vee y = y x ∨ y = y (or equivalently x ∧ y = x x \wedge y = x x ∧ y = x ). Use the given conditions to derive relations between elements.