Combinatorics Discrete Mathematics Study Notes (Part-2)

By Mukesh Kumar|Updated : August 25th, 2021

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.

byjusexamprep

  • 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

byjusexamprep

Counting Principle [Inclusion-Exclusion]

byjusexamprep

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.

byjusexamprep

byjusexamprep

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

Comments

write a comment

Follow us for latest updates