# 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.

## 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

Thanks

Sahi Prep Hai Toh Life Set Hai!!