Difference between revisions of "Combinatorics"

(Olympiad Topics)
m
 
(26 intermediate revisions by 15 users not shown)
Line 1: Line 1:
'''Combinatorics''' is the study of counting. Different kinds of counting problems can be approached by a variety of techniques.
+
'''Combinatorics''' is the study of [[discrete]] structures broadly speaking. Most notably, combinatorics involves studying the enumeration (counting) of said structures. For example, the number of three-[[cycle|cycles]] in a given [[graph]] is a combinatorial problem, as is the derivation of a non-[[recursive]] formula for the [[Fibonacci numbers]], and so too methods of solving the [[Rubiks cube]]. Mathematicians who spend their careers studying combinatorics are known as ''combinatorialists''.
  
 +
Combinatorial problems often make up a good portion of problems found in mathematics competitions and can be approached by a variety of techniques, such as [[generating functions]] or the [[Principle of Inclusion-Exclusion|principle of inclusion-exclusion]]. Combinatorics also has many applications outside of pure mathematics, notably in [[theoretical computer science]], [[statistics]], and various fields of science.
  
== Introductory combinatorics ==
+
People who encounter the term combinatorics for the first time often discredit it as "easy" because they "already know how to count." While this is true in the sense that people know how to count lists of numbers, enumeration problems are (typically) not nearly as simple as counting a list of numbers. One must first determine ''what'' and ''how'' something must be counted, both of which are often difficult to do.
=== Lists -- the beginning ===
 
Consider the task of counting the number of integers between 14 and 103 inclusive.  We could simply list those [[integers]] and count them. However, we can renumber those integers so that they correspond to the [[counting numbers]] (positive integers), starting with 1.  In this [[correspondence]], 14 corresponds to 1 (for the 1st integer in the list), 15 with 2, 16 with 3, etc. The relationship between the members of each pair is that the second is 13 less than the first.  So, we know that 103 corresponds to the 103 - 13 = 90th integer in the list.  Thus, the list is 90 integers long.
 
  
Note that <math>13 = 14 - 1</math>, or 1 less than the first integer in the list.  If we start our list with <math>n</math> and end with <math>m</math> (i.e. m and n inclusive), the number of integers in the list is
+
==Study Guides to Combinatorics==
 +
* [[Combinatorics/Introduction]]
 +
*[[Combinatorics/Intermediate]]
 +
*[[Combinatorics/Olympiad]]
  
<math>\displaystyle m - (n -1) = m - n + 1.</math>
 
  
  
== Introductory Topics ==
 
The following topics help shape an introduction to counting techniques:
 
* [[Venn diagram]]
 
* [[Combinations]]
 
* [[Permutations]]
 
* [[Overcounting]]
 
* [[Complementary counting]]
 
* [[Casework]]
 
* [[Constructive counting]]
 
* [[Committee forming]]
 
* [[Pascal's Triangle]]
 
* [[Combinatorial identities]]
 
* [[Binomial Theorem]]
 
  
== Intermediate Topics ==
+
[[Combinatorics Challenge Problems]]
 
 
* [[Principle of Inclusion-Exclusion]]
 
* [[Conditional Probability]]
 
* [[Recursion]]
 
* [[Correspondence]]
 
* [[Generating functions]]
 
* [[Partitions]]
 
* [[Geometric probability]]
 
 
 
== Olympiad Topics ==
 
 
 
* [[Combinatorial geometry]]
 
* [[Graph theory]]
 
* [[Stirling numbers]]
 
* [[Ramsey numbers]]
 
* [[Catalan Numbers]]
 
 
 
== See also ==
 
 
 
* [[Probability]]
 

Latest revision as of 01:12, 4 October 2020

Combinatorics is the study of discrete structures broadly speaking. Most notably, combinatorics involves studying the enumeration (counting) of said structures. For example, the number of three-cycles in a given graph is a combinatorial problem, as is the derivation of a non-recursive formula for the Fibonacci numbers, and so too methods of solving the Rubiks cube. Mathematicians who spend their careers studying combinatorics are known as combinatorialists.

Combinatorial problems often make up a good portion of problems found in mathematics competitions and can be approached by a variety of techniques, such as generating functions or the principle of inclusion-exclusion. Combinatorics also has many applications outside of pure mathematics, notably in theoretical computer science, statistics, and various fields of science.

People who encounter the term combinatorics for the first time often discredit it as "easy" because they "already know how to count." While this is true in the sense that people know how to count lists of numbers, enumeration problems are (typically) not nearly as simple as counting a list of numbers. One must first determine what and how something must be counted, both of which are often difficult to do.

Study Guides to Combinatorics



Combinatorics Challenge Problems