The Pigeonhole Principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. It is commonly called Dirichlet's box principle or Dirichlet's drawer principle and can be used to demonstrate unexpected results. The principle has a generalization for arbitrary n and m, which states that at least one of the sets will contain at least k + 1 objects. It can also be applied to infinite sets that cannot be put into one-to-one correspondence.
Carnegie Mellon University
Fall 2021
This course provides a comprehensive introduction to Discrete Mathematics, emphasizing the application of these concepts in Computer Science. Topics include counting, recurrence relations, combinatorial games, Polya theory, and more.
No concepts data
+ 13 more conceptsBrown University
Spring 2023
CSCI 0220 provides a foundation in discrete math and probability theory. Key topics include logic, set theory, number theory, combinatorics, graph theory, and probability. No prior math background assumed. Aims to develop problem solving, communication, and collaboration skills. Introduces new concepts and ways of thinking to enable analyzing problems arising in computer science. Beginner-friendly introduction to core mathematical concepts underlying many aspects of CS.
No concepts data
+ 26 more concepts