Basic Rules of Combinatorics
1. The Sum Rule:
If we have A number of ways of doing Task1 and B number of ways of doing Task2 then the total number of ways to choose one of the Task is equals to A+B.
So generally, if there are N tasks and i’th task can be done in a[i] ways then there are a1+ a2+ a3+… an ways to do one of the tasks.
Example:
Imagine you have 3 different Hats, 2 different shirts and 4 different pants. If you want to donate any one of the item what are the total number of ways to do say?
Answer: 3 + 2 + 4 = 9
2. The Product Rule:
If we have A number of ways of doing Task1 and B number of ways of doing Task2 then the total number of ways of doing both the tasks is equal to A*B.
So generally, if there are N tasks and i’th task can be done in a[i] ways then there are a1* a2* a3*… an ways to do all the task.
Example: Imagine you have 3 different Hats, 2 different shirts and 4 different pants. You want to get dressed and for that you have to wear 1 hat, 1 shirt and 1 pant. In how many ways you can do so?
Solution: 3 * 2 * 4 = 24
Basics of Combinatorics for Competitive Programming
Welcome to the world of competitive programming, where we’ll explore the ABCs of Combinatorics – a fancy term for counting and arranging things. Think of it like solving puzzles with numbers and patterns. In this article, we’re diving into the Basics of Combinatorics that every competitive programmer needs to know. We’ll learn how to count, arrange, and select things in clever ways. These skills are like secret weapons for solving problems quickly and efficiently. So, get ready to boost your problem-solving game with the magic of Combinatorics!
Table of Content
- What is Combinatorics?
- Basic Rules of Combinatorics
- Fundamental Concepts in Combinatorics
- Practice Problems on Combinatorics