hamburger

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.

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 Syllabus 2022

GATE CSE Exam Pattern 2022

GATE CSE Question Papers

GATE CSE Books 2022

GATE CSE Study Plan

GATE CSE Exam Analysis 2022

GATE CSE Answer Key 2022

GATE CSE Result 2021

GATE CSE Counselling

BARC CS Syllabus

BARC CS Study Plan

BARC CS Exam Analysis

Thanks

Sahi Prep Hai Toh Life Set Hai!!

Download BYJU’S Exam Prep, Best gate exam app for Preparation

Our Apps Playstore
POPULAR EXAMS
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com
Home Practice Test Series Premium