Combinatorial Principles

Scorching goIITian

Posted on
8 Jul 2012 21:40:48 IST

Posts: 256

8 Jul 2012 21:40:48 IST

Like 1 people liked this

331

Combinatorial Principles

JEE Main , BITSAT , IIIT , academic , Mathematics

Combinatorics is the branch of mathematics studying the enumeration, permutation and combination of sets of elements and the mathematical relations that characterize their properties.

Mathematicians sometimes use the terms "combinatorics" to refer to a large subset of discrete mathematics that include graph theory. In that case, what is called the combinatorics is then referred to as "ENUMERATION".

In proving results in combinatorics, several useful COMBINATORIAL RULES or COMBINATORIAL PRINCIPLES

are commonly recognized and used.

Some of the important principle in this are RAMSEY'S THEOREM, SPERNER THEOREM, VAN DER WAERDEN'S THEOREM, DIRICHLET'S BOX PRINCIPLE etc.

Short reviews of these theorems are:

1) RAMSEY'S THEOREM : Ramsey's theorem is a generalization of DILWORTH'S LEMMA which states for each pair of positive integers and there exists an integer (known as the Ramsey number) such that any graph with nodes contains a clique with at least nodes or an independent set with at least nodes.

2) DIRICHLET'S BOX PRINCIPLE : A.k.a. the pigeonhole principle. Given boxes and objects, at least one box must contain more than one object. This statement has important applications in number theory and was first stated by Dirichlet in 1834. In general, if objects are placed into boxes, then there exists at least one box containing at least objects, where is the ceiling function.

3) SPERNER'S THOREM : The maximum cardinality of a collection of subsets of a

-element set

, none of which contains another, is the binomial coefficient

, where

is the floor function.

These are very helpful while studying combinatorics.

Hope it will help in studying that.

SOURCE : Wolfram Mathsworld

Comments (2)

Anjali Goyal

New kid on the Block

Joined: 29 Sep 2011 16:25:58 IST

Posts: 18

9 Jul 2012 13:42:35 IST

Like 0 people liked this

A great explanation SUMIRAN...

Anjali Goyal

New kid on the Block

Joined: 29 Sep 2011 16:25:58 IST

Posts: 18

9 Jul 2012 13:43:39 IST

Like 0 people liked this

Good thing that you have mentioned the source.......

Quick Reply

Reply

	Some HTML allowed.
	Keep your comments above the belt or risk having them deleted.
	Signup for a avatar to have your pictures show up by your comment
	If Members see a thread that violates the Posting Rules, bring it to the attention of the Moderator Team

Free Sign Up!

Preparing for JEE?

Kickstart your preparation with new improved study material - Books & Online Test Series for JEE 2014/ 2015

@ INR 5,443/-

For Quick Info

Name

Mobile

E-mail

City

Class