|

Combinatorial Principles

Scorching goIITian

Posted on
8 Jul 2012 21:40:48 IST
Posts: 256
8 Jul 2012 21:40:48 IST
1 people liked this
2
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

New kid on the Block

Joined: 29 Sep 2011 16:25:58 IST
Posts: 18
9 Jul 2012 13:42:35 IST
0 people liked this

A great explanation SUMIRAN...

New kid on the Block

Joined: 29 Sep 2011 16:25:58 IST
Posts: 18
9 Jul 2012 13:43:39 IST
0 people liked this

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

 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

## For Quick Info

Name

Mobile

E-mail

City

Class

Vertical Limit

Top Contributors
All Time This Month Last Week
1. Bipin Dubey
 Altitude - 16545 m Post - 7958
2. Himanshu
 Altitude - 10925 m Post - 3836
3. Hari Shankar
 Altitude - 9960 m Post - 2185
4. edison
 Altitude - 10815 m Post - 7797
5. Sagar Saxena
 Altitude - 8625 m Post - 8064