Combinatorics Discrete Mathematics Study Notes (Part-2)
By BYJU'S Exam Prep
Updated on: September 25th, 2023
Combinatorics Discrete Mathematics Study Notes (Part-2)- Combinatorics topic comes under discrete mathematics is divided into 2 parts second part includes counting of the set, Fundamental Principle of Counting, Pigeonhole Principle, Generating Functions.
This topic is important for various competitive exams such as GATE CSE, SSC JE, ISRO, ESE, IES and other computer science exams.
Table of content
Combinatorics Discrete Mathematics Study Notes (Part-2)- Combinatorics topic comes under discrete mathematics is divided into 2 parts second part includes counting of the set, Fundamental Principle of Counting, Pigeonhole Principle, Generating Functions.
This topic is important for various competitive exams such as GATE CSE, SSC JE, ISRO, ESE, IES and other computer science exams.
Counting
- Countable sets: These sets have one to one corresponding mapping to some subset of natural numbers.
- Uncountable sets: These sets don’t have one to one corresponding mapping to some subset of natural numbers.
- Union of two countable sets in countable.
- Union of the countable number of countable sets is countable.
- Union of Uncountable sets is Uncountable.
- The set of real numbers is uncountable.
- The set of integers is countable.
- The set of lines through the origin is ‘uncountable’.
Fundamental Principle of Counting
If some event can occur in different ways, and if following this event, a second event occurs in different ways, …. Then the number of ways the event can occur in the order
Pigeonhole Principle
Only the name is complex, but the concept is very fundamental.
- If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.
- If N objects are placed into k boxes, then there is at least one box containing at least ceil(n/k) objects.
Some useful SUMMATION
Counting Principle [Inclusion-Exclusion]
Generating Functions
Generating Functions are one of the most surprising and useful inventions in Discrete Mathematics. Generating functions changes sequences problems into function problems. This is because we collectively have mathematical machinery for manipulating functions.
You can go with the detailed champion study plan for GATE CS 2022 from the given link:
Detailed GATE CSE 2022 Champion Study Plan
Candidates can also practice 110+ Mock tests for exams like GATE, ISRO, DRDO, BARC, NIELIT, etc. with the BYJU’S Exam Prep Test Series check the following link to avail:
Click Here to Avail GATE CSE Test Series! (100+ Mock Tests)
Get unlimited access to 21+ structured Live Courses all 112+ mock tests with the Online Classroom Program for GATE CS & PSU Exams:
Click here to avail Online Classroom Program for Computer Science Engineering
Related Links |
|
GATE CSE Exam Analysis 2022 | |
BARC CS Syllabus | |
BARC CS Exam Analysis |
Thanks
Sahi Prep Hai Toh Life Set Hai!!
Download BYJU’S Exam Prep, Best gate exam app for Preparation