Combinatorics Website Links For
Combinatorics 		 

Information About

Combinatorics
  CATEGORIES ABOUT COMBINATORICS
   
combinatorics
   
discrete mathematicscombinatorics
   
discrete mathematics
   
discrete mathematics
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



Combinatorics is as much about problem solving as theory building, though it has developed powerful theoretical methods, especially since the later twentieth century (see the page List Of Combinatorics Topics for details of the more recent development of the subject). One of the oldest and most accessible parts of combinatorics is Graph Theory , which also has numerous natural connections to other areas.

A trivial example of a combinatorial question is the following: What is the number of possible orderings of a deck of 52 distinct playing cards? The answer is 52! (fifty-two Factorial ), which is equal to about 8.0658 × 1067.

Another example of a more difficult problem: Given a certain number ''n'' of people, is it possible to assign them to sets so that each person is in at least one set, each pair of people is in exactly one set together, every two sets have exactly one person in common, and no set contains everyone, all but one person, or exactly one person? The answer depends on ''n''. See " Design Theory " below.

A mathematician who studies combinatorics is often referred to as a ''combinatorialist'' or ''combinatorist''.


PERMUTATIONS

See Also: Permutations




Permutation with repetition


When order matters, and an object can be chosen more than once, the number of permutations is

: n^r \,\!

where ''n'' is the number of objects from which you can choose and ''r'' is the number to be chosen.

For example, if you have the letters A, B, C, and D and you wish to discover the number of ways to arrange them in three letter patterns ( Trigram s)
# order matters (e.g., A-B is different from B-A, both are included as possibilities)
# an object can be chosen more than once (A-A possible)

you find that there are 43 or 64 ways. This is because for the first slot you can choose any of the four values, for the second slot you can choose any of the four, and for the final slot you can choose any of the four letters. Multiplying them together gives the total.


Permutation without repetition

When the order matters and each object can be chosen only once, then the number of permutations is
: (n)_{r} = rac{n!}{(n-r)!} where ''n'' is the number of objects from which you can choose, ''r'' is the number to be chosen and "!" is the standard symbol meaning Factorial .
For example, if you have five people and are going to choose three out of these, you will have 5!/(5−3)! = 60 permutations.

Note that if ''n'' = ''r'' (meaning the number of chosen elements is equal to the number of elements to choose from; five people and pick all five) then the formula becomes
: rac{n!}{(n-n)!} = rac{n!}{0!} = n!
where 0! = 1.

For example, if you have the same five people and you want to find out how many ways you may arrange them, it would be 5! or 5 × 4 × 3 × 2 × 1 = 120 ways. The reason for this is because you can choose from 5 for the initial slot, then you are left with only 4 to choose from for the second slot etc. Multiplying them together gives the total of 120.

An alternative notation is ''nPr'' where ''n'' stands for the total number of objects, and the ''r'' stands for the number of objects that will be chosen. For example, if you have 10 shapes in a bag and you will pick 4 of them out, the notation would be: ''10 P 4''. This notation is often used on calculators.


COMBINATIONS

See Also: Combinations



Combination without repetition

When the order does not matter and each object can be chosen only once, the number of combinations is the Binomial Coefficient

:{n\choose r} =

where ''n'' is the number of objects from which you can choose and ''r'' is the number to be chosen.

For example, if you have ten numbers and wish to choose 5 you would have 10!/(5!(10−5)!) = 252 ways to choose.
Just as with permutations, there is an alternate notation used primarily on calculators, of the form ''nCr''.


Combination with repetition

See Also: Multiset#Multiset coefficients



When the order does not matter and an object can be chosen more than once, then the number of combinations is

: = =

where ''n'' is the number of objects from which you can choose and ''r'' is the number to be chosen.

For example, if you have ten types of donuts (''n'') on a menu to choose from and you want three donuts (''r'') there are (10 + 3 − 1)! / 3!(10 − 1)! = 220 ways to choose (see also Multiset ).


ENUMERATIVE COMBINATORICS

Counting the number of ways that certain patterns can be formed is the central problem of enumerative combinatorics.
Two examples of this type of problem are counting combinations and counting permutations (as discussed in the previous section).
More generally, given an infinite collection of finite sets {''S''''i''} indexed by the Natural Number s, enumerative combinatorics seeks to describe a ''counting function'' which counts the number of objects in ''S''''n'' for each ''n''. Although counting the number of elements in a set is a rather broad Mathematical Problem , many of the problems that arise in applications have a relatively simple combinatorial description.

The simplest such functions are '' Closed Formula s'', which can be expressed as a composition of elementary functions such as Factorial s, powers, and so on. For instance, as noted above, the number of different possible orderings of a deck of ''n'' cards is ''f''(''n'') = ''n''!. Often, no closed form is initially available. In these cases, we frequently first derive a recurrence relation, then solve the recurrence to arrive at the desired closed form. We demonstrate this method below.

For example, let ''f''(''n'') be the number of distinct subsets of the set S(n)=\{1,2,3, \ldots ,n \} that do not contain two consecutive integers. When ''n'' = 4, we have the sets {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, so ''f''(4) = 8. We count the desired subsets of S(n) by separately counting those subsets that contain element n and those that do not. If a subset contains n, then it does not contain element n-1. So there are exactly f(n-2) of the desired subsets that contain element n. The number of subsets that do not contain n is simply f(n-1). Adding these numbers together, we get the recurrence relation:

:f(n) = f(n-1) + f(n-2)\, ,

where f(1)=2 and f(2)=3.

As early as 1202, Leonardo Fibonacci studied these numbers. They are now called Fibonacci Number s; in particular, f(n) is known as the n+2nd Fibonacci number. Although the recurrence relation allows us to compute every Fibonacci number, the computation is inefficient. However, by using standard techniques to solve Recurrence Relation s, we can reach the Closed Form solution:

:f(n) = rac{\phi^{n+2}-(1-\phi)^{n+2}}{\sqrt{5}}

where \phi = (1 + \sqrt 5) / 2, the Golden Ratio .

Often, a complicated closed formula yields little insight into the behavior of the counting function as the number of counted objects grows.
In these cases, a simple asymptotic approximation may be preferable. A function g(n) is an asymptotic approximation to f(n) if f(n)/g(n) ightarrow 1 as n ightarrow Infinity . In this case, we write f(n) \sim g(n)\,.
In the above example, an asymptotic approximation to f(n) is:

:f(n) \sim rac{\phi^{n+2}}{\sqrt{5}}

as ''n'' becomes large.

Finally, ''f''(''n'') may be expressed by a Formal Power Series , called its '' Generating Function '', which is most commonly either the Ordinary Generating Function

:\sum_{n\ge 0} f(n) x^n

or the Exponential Generating Function

:\sum_{n \ge 0} f(n) rac{x^n}{n!}

Once determined, the generating function may allow one to extract all the information given by the previous approaches. In addition, the various natural operations on generating functions such as addition, multiplication, differentiation, etc., have a combinatorial significance; this allows one to extend results from one combinatorial problem in order to solve others.

Enumerative combinatorics is used frequently in Computer Science , because counting a set can closely correspond to computing the elements of a set.


Set sizes motivate a naming convention