Difference between revisions of "Combinatorics"

m
m
 
(13 intermediate revisions by 8 users not shown)
Line 1: Line 1:
'''Combinatorics''' is the study of discrete structures in general, and enumeration on discrete structures in particular. For example, the number of three-[[cycle|cycles]] in a given [[graph]] is a combinatoric problem, as is the derivation of an [[analysis|analytic]] solution to the [[Fibonacci recurrence]], and so too methods of solving the [[Rubiks cube]]. Different kinds of counting problems can be approached by a variety of techniques, such as [[generating functions]] or the [[inclusion-exclusion principle]].
+
'''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''.
  
== Student Guides to Combinatorics ==
+
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.
* '''[[Combinatorics/Introduction | Introductory topics in combinatorics]]'''
 
* '''[[Combinatorics/Intermediate | Intermediate topics in combinatorics]]'''
 
* '''[[Combinatorics/Olympiad | Olympiad topics in combinatorics]]'''
 
  
== Resources ==
+
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.
Listed below are various combinatorics resources including books, classes, and websites.
 
  
=== Books ===
+
==Study Guides to Combinatorics==
 +
* [[Combinatorics/Introduction]]
 +
*[[Combinatorics/Intermediate]]
 +
*[[Combinatorics/Olympiad]]
  
* Introductory
 
** ''the Art of Problem Solving Introduction to Counting and Probability'' by David Patrick [http://www.artofproblemsolving.com/Books/AoPS_B_Item.php?item_id=202 (details)]
 
* Intermediate & Beyond
 
** ''the Art of Problem Solving Intermediate Counting and Probability'' by David Patrick [http://www.artofproblemsolving.com/Books/AoPS_B_Item.php?item_id=302 (details)]
 
* Undergraduate level
 
** ''Generatingfunctionology'' by Herbert S. Wilf. Free fulltext download here: [http://www.math.upenn.edu/~wilf/DownldGF.html]
 
  
== See also ==
 
  
* [[Probability]]
+
 
* [[:Category:Introductory Combinatorics Problems|Introductory Problems]]
+
[[Combinatorics Challenge Problems]]
* [[:Category:Intermediate Combinatorics Problems|Intermediate Problems]]
 
* [[:Category:Olympiad Combinatorics Problems|Olympiad Problems]]
 
[[Category:Combinatorics]] [[Category:Mathematics]]
 

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