Important Questions on Derangements

Duration: 10 min

This video lesson is available to enrolled students.

Return to /learn/UPPSC-POLYTECHNIC-LECTURER-2025-CS/paper-1-discrete-structures-and-theory-of-logic/permutation-and-combination/pigeonhole-principle-and-inclusionexclusion/asset-important-questions-on-derangements after enrolling

Inside: a video lesson and guided study material.

Module outline

  1. About Course: UPPSC Course Overview
  2. Interview Preparation & Guidance: Interview Preparation
  3. Paper 1 | General Hindi: हिन्दी की रूप रचना, वर्णमाला, समास, बहु-विषयक सामग्री (विभिन्न अवधारणाओं को जोड़ने वाली सामग्री), हिन्दी की ध्वनि और स्वनिम व्यवस्था, प्राचीन और मध्यकालीन भारतीय आर्यभाषाएँ, काव्य के लक्षण, हेतु और प्रयोजन, हिन्दी शब्द रचना, हिन्दी साहित्येतिहास दर्शन, भक्तिकालीन काव्यधाराएँ, भारतीय काव्यशास्त्र की परंपरा, भारतीय नवजागरण और स्वाधीनता आंदोलन, अन्य गद्य विधाएँ एवं प्रवासी साहित्य, निर्धारित उपन्यासों का तुलनात्मक अध्ययन, गोदान, हिन्दी कहानी का विकास, स्वातंत्र्योत्तर और नयी कहानी, हिन्दी निबंध का विकास, शुक्लोत्तर निबंध, द्विवेदी और शुक्ल युग के निबंध, हिन्दी की संवैधानिक स्थिति, आधुनिक भारतीय आर्यभाषाएँ और हिन्दी का उद्भव, हिन्दी भाषा प्रयोग के विविध रूप, रीतिकाल, जीवनी, द्विवेदी युग और छायावाद, रीति, वक्रोक्ति और औचित्य सिद्धान्त, शब्दशक्ति और ध्वनि सिद्धान्त, रस सिद्धान्त और साधारणीकरण, उत्तर आधुनिकतावाद, लोहिया दर्शन, हिन्दी उपन्यास का विकास, हिन्दी नवजागरण, अंबेडकर दर्शन, आदिकाल, प्रयोगवाद और नयी कविता, छायावादी काव्य: प्रसाद और निराला, प्रगतिवाद से समकालीन कविता, निर्गुण भक्ति काव्य, द्विवेदीयुगीन काव्य, रीतिकालीन काव्य, आरंभिक हिन्दी उपन्यास, स्वातंत्र्योत्तर उपन्यास, आत्मकथा, स्वाधीनता-पूर्व प्रेमचंदोत्तर उपन्यास, निर्धारित कहानियों का तुलनात्मक अध्ययन, साठोत्तरी नाटक, प्रसाद और प्रसादोत्तर युग के नाटक, भारतेन्दु युगीन नाटक, स्वातंत्र्योत्तर नाटक, भारतेन्दु युगीन निबंध, संस्मरण और रेखाचित्र, व्यंग्य, एक साहित्यिक की डायरी, संस्कृति के चार अध्याय, सगुण भक्ति काव्य, हिन्दी नाटक, एकांकी और रंगमंच, आधुनिक गद्य और हिन्दी नवजागरण, अलंकार सिद्धान्त, हिन्दी आलोचना का विकास, भक्ति आंदोलन, कल्पना, बिम्ब, प्रतीक, मिथक और फंतासी, नयी कविता का विस्तार और साठोत्तरी कविता, उत्तर-छायावादी और प्रगतिवादी काव्य, काव्यगुण और काव्यदोष, प्लेटो, अरस्तू और पाश्चात्य परंपरा, मार्क्सवाद, स्वच्छन्दतावादी काव्यशास्त्र, आधुनिक पाश्चात्य आलोचना, भाषा और भाषा परिवार, देवनागरी लिपि
  4. Paper 2 | General Studies: State Wise GK / राज्यवार सामान्य ज्ञान (GK), Polity / राजव्यवस्था, Geography / भूगोल, History / इतिहास, GK- Current Affairs / GK- समसामयिकी
  5. Paper 1 | Programming Language: Language Design, C Fundamentals, Control Flow, Functions, Arrays & Pointers, Storage Classes, Structures & Enums, DMA, Macros, Scoping & File Handling, OOPS with C++
  6. Paper 1 | Database Management Systems: Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Decomposition Properties & 4NF, File Organization & Indexing, Relational Algebra, SQL, Relational Calculus, Transaction Management, Concurrency Control, ORDBMS, NoSQL
  7. Paper 1 | Cyber Security: Computer Fundamentals and Hardware, Literal Comprehension, Computer Software, Inferential Comprehension, Critical Comprehension, Internet and World Wide Web, Email and Online Communication, Cyber Security, Waste Management / अपशिष्ट प्रबंधन, Digital Ethics, IPR and Society, Digital and New Media / डिजिटल एवं नव माध्यम, Research Ethics / शोध नैतिकता, Emerging Technologies, ICT in Education and Governance, Society, Law & Ethics, Cyber Threats and Malware Attacks, Role of Internet and Web Services, Security in Mobile and Wireless Computing, Electronic Data Interchange and E-Commerce, Physical Security and Cryptography Basics, Intrusion Detection Systems (IDS), Cyber Safety and Security, Ethical Hacking, Protection of Geographical Indications / भौगोलिक संकेतों का संरक्षण
  8. Paper 1 | Computer Organization and Architecture: Basics of COA, Programming the Basic Computer, Cache Memory Organization, Input Output Organisation, Instr Formats & Modes, Register Transfer and Microoperations, Control Unit Design
  9. Paper 1 | Computer Networks: Introduction to CN, Data Communication, DLL: Access Control, DLL: Flow Control, DLL: Error Control, DLL: Framing, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Net Layer:Routing Protocol, Transport Layer Services, TL: Congestion & UDP, Application Layer, Hardware basics, Network Security
  10. Paper 1 | Design and Analysis of Algorithms: Algorithm Analysis, Time Complexity Analysis, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Minimum Spanning Trees, Shortest Path Algos, Advanced Algorithms
  11. Paper 1 | Data Structures: Introduction to DS, Array, Linked List, Stack, Queue, Tree, Graphs, Hashing
  12. Paper 1 | Discrete Structures and Theory of Logic: Permutation, Combination and Probability / क्रमचय, संचय एवं प्रायिकता, Set Theory, Relations, Functions, Propositional and Predicate Logic, Graph Theory, Group Theory
  13. Paper 1 | Software Project Management: Software Project Management
  14. Paper 2 | Operating Systems: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Threads & Process Creation, Deadlock, Memory Management, Virtual Memory, Disc Scheduling, File Management, Unix OS, Linux OS, Security
  15. Paper 2 | Compiler Design: Intro to Compilers, Lexical Analysis, Grammar & CFG, Syntax Analysis: Top-Down, Syntax Analysis: Bottom-Up, Semantic Analysis & SDT, Intermediate Code Gen, Code Optimization, Run Time Environment, Introduction to TOC, Deterministic FA (DFA), Non-Deterministic FA, Regular Expressions, Pushdown Automata & CFG, Complexity Theory
  16. Paper 2 | Artificial Intelligence & High Performance Computing: Approaches to AI, Search Algorithms, Game Playing, Knowledge Representation, Planning, Multi Agent Systems, Natural Language Processing, Cloud and Distributed Computing
  17. Paper 2 | Image Processing: Digital Image Fundamentals, Image Enhancement, Image Restoration, Color Image Processing, Image Compression
  18. Paper 2 | Software Engineering: Fundamentals of Software Engineering, Software Requirements and Quality Assurance, Software Design, Estimation and Metrics, Software Testing, Software Maintenance and Configuration Management
  19. Paper 2 | Computer Graphics: Basics of Computer Graphics, 2-D Geometrical Transforms and Viewing, 3-D Object Representation, Geometric Transformations and Viewing
  20. Paper 2 | Web Technologies: Website, Browser & Services, Internet Fundamentals, Web Design & Development, Protocols & Services, Web Publishing & Hosting, Server Side & Security, Emerging Technologies, HTML Basics, JavaScript-Basics, Java
  21. Paper 2 | Soft Computing: Fuzzy Sets, Artificial Neural Networks, Genetic Algorithms
  22. Paper 2 | Distributed System: Distributed Systems
  23. UPPSC Live Class Recordings: UPPSC Polytechnic Lecturer 2025 (CS)
  24. Previous Year Papers:
  25. Mock Test:
AI summary & chapters

AI Summary

An AI-generated summary of this video lecture.

This educational video is a lecture on permutations and combinations, specifically focusing on derangements. The instructor begins by clarifying the difference between permutations and combinations using a visual metaphor of a detective trying to unlock a door, where the order of the combination matters. The core of the lecture is on derangements, which are permutations where no element appears in its original position. The instructor presents several problems to illustrate the concept. The first problem involves placing 5 gems into 5 boxes such that no gem is in its corresponding box, which is a classic derangement problem. The solution is derived by calculating the total number of permutations (5!) and subtracting the number of permutations where at least one gem is in the correct box, which is found using the principle of inclusion and exclusion. The second problem asks for the number of ways to place 4 letters into 4 envelopes so that at least one letter is in the correct envelope, which is solved by subtracting the number of derangements from the total permutations. The final problem is a trick question about a typist inserting 42 letters into 42 envelopes, asking for the number of ways to have exactly one letter in the wrong envelope. The instructor explains that this is impossible because if one letter is in the wrong envelope, another must also be misplaced to accommodate it, making the answer zero. The video uses a whiteboard for calculations and includes a brief, unrelated meme at the beginning.

Chapters

  1. 0:00 – 2:00 00:00-02:00

    The video opens with a four-panel graphic illustrating the concepts of permutation and combination. The top-left panel shows a craps table with dice, labeled 'PERMUTATION'. The top-right panel shows a basket of fruit, labeled 'COMBINATION'. The bottom-left panel shows a pizza, and the bottom-right shows two men in suits. The instructor then transitions to a slide with a meme and a picture of a man with yellow teeth, introducing the topic. The main content begins with a slide titled 'Confused' that asks, 'Should I unlock with Permutation or Combination?'. This slide features a cartoon detective with a magnifying glass, standing between two doors labeled 'Permutation' and 'Combination', each with a lock. The instructor explains that in a permutation, the order matters, while in a combination, it does not, using the example of a lock where the sequence of numbers is crucial.

  2. 2:00 – 5:00 02:00-05:00

    The lecture progresses to the core topic of derangements. A slide titled 'Derangements' is shown, displaying a table of permutations of the numbers 1, 2, 3, 4, with some highlighted as derangements (where no number is in its original position). The instructor then presents a problem: 'There are 5 gems {g1,g2,g3,g4,g5} and 5 boxes {b1,b2,b3,b4,b5}. We are supposed to place exactly one gem in each box. Find number of ways to do so such that gem g(i) is placed in box b(i) for all i={1,2,3,4,5)?'. The instructor explains that this is asking for the number of ways where all gems are in their correct boxes, which is only 1 way. He then changes the question to find the number of ways such that at least one gem is in an incorrect box. He writes the formula '# total - # all in correct box' and calculates 5! - 1 = 119. He then introduces the concept of derangements, which is a permutation where no element is in its original position, and writes the formula for the number of derangements of n objects as !n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!). He applies this to the 5-gem problem, calculating !5 = 5! * (1 - 1/1! + 1/2! - 1/3! + 1/4! - 1/5!) = 120 * (1 - 1 + 1/2 - 1/6 + 1/24 - 1/120) = 120 * (0 + 0.5 - 0.1667 + 0.04167 - 0.00833) = 120 * 0.36667 = 44.0004, which he rounds to 44.

  3. 5:00 – 9:43 05:00-09:43

    The instructor moves to a new problem: 'There are 4 different letters and 4 addressed envelopes. In how many ways can the letters be put in the envelopes so that at least one letter goes to the correct address?'. He explains that this is the total number of ways to arrange the letters minus the number of derangements. He writes the formula '# total - # all incorrect' and calculates 4! - !4. He calculates !4 = 4! * (1 - 1/1! + 1/2! - 1/3! + 1/4!) = 24 * (1 - 1 + 1/2 - 1/6 + 1/24) = 24 * (0 + 0.5 - 0.1667 + 0.04167) = 24 * 0.375 = 9. So, the answer is 24 - 9 = 15. He then presents a final, trick question: 'After a typist types 42 letters and addresses 42 envelopes, she inserts the letters randomly into envelopes (1 letter per envelope). In how many ways can she insert exactly one letter in an improper envelope?'. He explains that this is impossible because if one letter is in the wrong envelope, it must have taken the place of another letter, which means at least two letters are in the wrong envelopes. Therefore, the number of ways to have exactly one letter in the wrong envelope is 0. The video ends with a 'THANKS FOR WATCHING' screen.

The video provides a structured and clear explanation of permutations, combinations, and the specific concept of derangements. It begins by establishing the fundamental difference between permutations and combinations using a relatable analogy. The core of the lecture is dedicated to derangements, a topic in combinatorics where no element is in its original position. The instructor effectively uses the principle of inclusion and exclusion to solve problems involving derangements, demonstrating the calculation of the number of derangements for a set of n elements. The lecture progresses from a simple problem of placing gems in boxes to a more complex one involving letters and envelopes, and concludes with a clever trick question that reinforces the logical understanding of the concept. The use of a whiteboard for step-by-step calculations and clear, concise language makes the complex topic accessible to students.

Loading lesson…