Discrete Mathematics - Vol 2 | 22. Counting Using Principle of Inclusion-Exclusion by Abraham | Learn Smarter
K12 Students

Academics

AI-Powered learning for Grades 8–12, aligned with major Indian and international curricula.

Professionals

Professional Courses

Industry-relevant training in Business, Technology, and Design to help professionals and graduates upskill for real-world careers.

Games

Interactive Games

Fun, engaging games to boost memory, math fluency, typing speed, and English skills—perfect for learners of all ages.

Typing
Memory
Math
English Adventures
Knowledge
22. Counting Using Principle of Inclusion-Exclusion

The lecture discusses the principle of inclusion-exclusion, explaining its definition and applications in counting problems. It elaborates on how this principle can be extended to find the cardinality of the union of multiple sets and provides a proof of concept through examples. Additionally, it presents an alternate form of inclusion-exclusion useful for counting specific types of elements, followed by multiple real-world applications and exercises to illustrate the concepts more clearly.

Enroll to start learning

You’ve not yet enrolled in this course. Please enroll for free to listen to audio lessons, classroom podcasts and take practice test.

Sections

  • 22.1

    Counting Using Principle Of Inclusion-Exclusion

    The principle of inclusion-exclusion helps in calculating the cardinality of the union of multiple sets by considering overlaps and correcting for double counting.

    Learning Practice

  • 22.1.1

    Introduction To The Principle Of Inclusion-Exclusion

    The Principle of Inclusion-Exclusion provides a systematic method to calculate the size of the union of multiple sets while avoiding double-counting.

    Learning Practice

  • 22.1.2

    Extension To Three Sets

    This section introduces the principle of inclusion-exclusion as applied to three sets, providing a framework for calculating cardinalities in complex set interactions.

    Learning Practice

  • 22.1.3

    Generalization To N Sets

    This section introduces the principle of inclusion-exclusion for counting elements in the union of n sets and discusses its generalization.

    Learning Practice

  • 22.1.4

    Proof Of The General Formula

    This section discusses the principle of inclusion-exclusion, including its application in counting and the general formula for the cardinality of the union of n sets.

    Learning Practice

  • 22.1.5

    Alternate Form Of Inclusion-Exclusion

    This section introduces the alternate form of the principle of inclusion-exclusion, focusing on its application in counting elements without specific properties.

    Learning Practice

  • 22.1.6

    Applications Of The Alternate Form

    This section explores the principle of inclusion-exclusion and its applications in counting problems.

    Learning Practice

  • 22.2

    Example Problems

    This section introduces the principle of inclusion-exclusion as a method for counting the cardinality of sets and their combinations.

    Learning Practice

  • 22.2.1

    Counting Solutions To An Equation

    This section discusses the Principle of Inclusion-Exclusion and its applications to counting solutions for equations.

    Learning Practice

  • 22.2.2

    Finding Onto Functions

    The section discusses the principle of inclusion-exclusion and its application in counting onto functions.

    Learning Practice

  • 22.2.3

    Generalization For M And N Elements

    This section introduces the Principle of Inclusion-Exclusion (PIE) for counting the cardinality of union sets, extending from two sets to n sets.

    Learning Practice

  • 22.2.4

    Derangements

    The section discusses derangements, which are arrangements of objects such that none remain in their original positions, and introduces the principle of inclusion-exclusion for counting these arrangements.

    Learning Practice

References

ch43.pdf

Class Notes

Memorization

What we have learnt

  • The principle of inclusion-...
  • The formula can be generali...
  • The alternate form of inclu...

Final Test

Revision Tests