# Combinatorial Mathematics:How to Count Without Counting

This site is a part of the JavaScript E-labs learning objects for decision making. Other JavaScript in this series are categorized under different areas of applications in the MENU section on this page.

Professor Hossein Arsham

The following is a collection of JavaScript for computing permutations and combinations counting with or without repetitions.

Many disciplines and sciences require the answer to the question: How Many? In finite probability theory we need to know how many outcomes there would be for a particular event, and we need to know the total number of outcomes in the sample space.

Combinatorics, also referred to as Combinatorial Mathematics, is the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system. Its objective is: How to count without counting. Therefore, One of the basic problems of combinatorics is to determine the number of possible configurations of objects of a given type.

You may ask, why combinatorics? If a sample spaces contains a finite set of outcomes, determining the probability of an event often is a counting problem. But often the numbers are just too large to count in the 1, 2, 3, 4 ordinary ways.

A Fundamental Result: If an operation consists of two steps, of which the first can be done in n1ways and for each of these the second can be done in n2 ways, then the entire operation can be done in a total of n1× n2 ways.

This simple rule can be generalized as follow: If an operation consists of k steps, of which the first can be done in n1 ways and for each of these the second step can be done in n2 ways, for each of these the third step can be done in n3 ways and so forth, then the whole operation can be done in n1 × n2 × n3 × n4 ×.. × nk ways.

Numerical Example: A quality control inspector wishes to select one part for inspection from each of four different bins containing 4, 3, 5 and 4 parts respectively. The total number of ways that the parts can be selected is 4×3×5×4 or 240 ways.

Factorial Notation: the notation n! (read as, n factorial) means by definition the product:

n! = (n)(n-1)(n-2)(n-3)...(3)(2)(1).

Notice that by convention, 0! = 1, (i.e., 0! º 1) . For example, 6! = 6×5×4×3×2×1 = 720

Permutations versus Combination: A permutation is an arrangement of objects from a set of objects. That is, the objects are chosen from a particular set and listed in a particular order. A combination is a selection of objects from a set of objects, that is objects are chosen from a particular set and listed, but the order in which the objects are listed is immaterial.

The number of ways of lining up k objects at a time from n distinct objects is denoted by n P k, and by the preceding we have:

n P k = (n)(n-1)(n-2)(n-3)......(n-k+1)

Therfore, The number of permutations of n distinct objects taken k at a time can be written as:

n P k = n! / (n - k) !

Combinations: There are many problems in which we are interested in determining the number of ways in which k objects can be selected from n distinct objects without regard to the order in which they are selected. Such selections are called combinations or k-sets. It may help to think of combinations as a committee. The key here is without regard for order.

The number of combinations of k objects from a set with n objects is n C k. For example, the combinations of {1,2,3,4} taken k=2 at a time are {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, for a total of 6 = 4! / [(2!)(4-2) !] subsets.

The general formula is:

n C k = n! / [k! (n-k) !].

Permutation with Repetitions: How many different letter arrangements can be formed using the letters P E P P E R?

In general, there are multinomial coefficients:

n! / (n1! n2! n3! ... nr!)

different permutations of n objects, of which n1 are alike, n2, are alike, n3 are alike,..... nr are alike. Therefore, the answer is 6! /(3! 2! 1!) = 60 possible arrangements of the letters P E P P E R.

Enter positive integer values for both n and k, and then click on the Calculate. Permutation of n objects in a group of size k, k £ n
 n k Permutation of n objects in a group of size k, repetitions allowed
 n k Combination of n objects in a group of size k, k £ n
 n k Combination of n objects in a group of size k, repetitions allowed
 n k

For Technical Details, Back to:
Statistical Thinking for Decision Making

Professor Hossein Arsham

The Copyright Statement: The fair use, according to the 1996 Fair Use Guidelines for Educational Multimedia, of materials presented on this Web site is permitted for non-commercial and classroom purposes only.
This site may be translated and/or mirrored intact (including these notices), on any server with public access. All files are available at http://home.ubalt.edu/ntsbarsh/Business-stat for mirroring.