Combinatorics Formulas

Basic Permutations

Variations

Combinations

Partitions

10 formulas

Basic Permutations

(3 formulas)

Permutation (Full)

P_n^n = n!

See details

Explanation

P n^n

n

!

ExampleUse CasesOther NotationsLearn More

This formula calculates the total number of ways to arrange n distinct items in n places.
It's a fundamental concept in combinatorics that quantifies all possible orderings of a set of objects.
The factorial grows rapidly as n increases, reflecting the explosive growth in possibilities as more items are added. This concept is crucial in probability theory, statistical mechanics, and many areas of discrete mathematics. It forms the basis for more complex permutation formulas and is a building block for understanding combinations and other combinatorial structures.

Permutation with Repetition

P_{n1,n2,...nx} =\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}

See details

Explanation

P {n1,n2,...nx}

n

n1, n2, ..., nx

x

!

ExampleUse Case

This formula calculates the number of unique arrangements when some items are identical. It's an extension of the basic permutation concept that accounts for repeated elements. By dividing the total number of permutations by the permutations of each repeated group, it eliminates overcounting. This formula is crucial in situations involving multisets or in probability calculations where events can occur multiple times. It's widely used in combinatorial optimization, group theory, and in generating functions in advanced combinatorics.

Circular Permutation

Pcirc(n) = (n-1)!

See details

Explanation

Pcirc

n

!

ExampleUse Case

This formula calculates the number of unique ways to arrange n different items in a circle. It's a special case of permutation that takes into account the rotational symmetry of circular arrangements. The formula is derived by fixing one element and permuting the rest, as rotations of the same arrangement are considered identical. Circular permutations are fundamental in group theory, particularly in the study of cyclic groups. They have applications in chemistry for molecular structures, in computer science for round-robin scheduling, and in mathematics for necklace problems. This concept is crucial in solving problems related to cyclic structures, in the analysis of cyclic codes in coding theory, and in certain areas of graph theory.

Variations

(2 formulas)

Permutation of Subset (Variations without Repetitions)

P^n_r​ = n! / (n-r)!

See details

Explanation

P^n r

n

r

!ExampleUse Case

This formula calculates the number of ways to arrange r items out of n items where order matters. It's a powerful tool in combinatorics that bridges the gap between full permutations and combinations. The formula effectively 'cancels out' the arrangements of the items not chosen, focusing only on the selected subset. This concept is fundamental in probability theory, particularly in calculating odds for complex events. It's extensively used in statistical sampling, experimental design, and in algorithms for generating random permutations.

Distribution into Cells (Variations with Repetition)

V_r^n = n^r

See details

Explanation

V r^n

n

r

n^r

This formula calculates the number of ways to distribute n different items into r numbered cells, where each item independently chooses one of the r cells. Each cell can potentially hold any number of items, from none to all n items. The formula is based on the multiplication principle, where each of the n items has r choices, leading to a total of

n^r

possible distributions. This concept is crucial in understanding the structure of sample spaces in probability theory, especially in scenarios with multiple independent choices per trial. It's also widely used in fields like computer science, cryptography, and statistical mechanics.

Combinations

(2 formulas)

Basic Combination

C^n_r = \frac{n!}{r! \cdot (n-r)!}

See details

Explanation

C^n r

n

r

!

ExampleUse Case

This formula calculates the number of ways to select r items from n items where order doesn't matter. It's a cornerstone of combinatorial mathematics, representing unordered selections. The formula can be derived from the permutation formula by dividing out the r! ways to arrange the chosen items. Combinations are essential in probability theory, forming the basis for the binomial distribution and Pascal's triangle. They're widely applied in statistical analysis, population genetics, and coding theory. In advanced mathematics, combinations play a crucial role in the study of finite sets, algebraic structures, and in the development of generating functions.

Combination Symmetry

C(n, r) = C(n, n-r)

, where

C(10, 3) = \frac{10!}{3! \cdot (10-3)!} = \frac{10!}{7! \cdot 3!} = C(10, 7)

See details

Explanation

C(n, r)

C(n, n-r)

n

r

ExampleUse Case

This formula expresses the symmetry in combinations, showing that the number of ways to choose r items from a set of n items is the same as the number of ways to choose n-r items. This property arises from the fact that choosing r items to include is equivalent to choosing n-r items to exclude, which is a fundamental aspect of the binomial coefficient. This symmetry is useful in simplifying calculations in probability theory, statistics, and various fields of mathematics.

Partitions

(3 formulas)

Partition into Groups

P(n,r) = S(n,r)

See details

ExplanationP(n,r)S(n,r)nrExampleUse Case

This formula, represented by the Stirling number of the second kind S(n,r), calculates the number of ways to partition n distinct items into r non-empty, distinguishable groups. It's a sophisticated combinatorial concept that bridges set theory and partition theory. Stirling numbers of the second kind are fundamental in analyzing set partitions and have deep connections to generating functions and Bell numbers. They arise naturally in problems involving distributing objects into containers, in the theory of distributions in statistics, and in the study of polynomials. These numbers have applications in computer science, particularly in analyzing the complexity of algorithms and data structures.

Weak Composition

W(n,r) = C(n+r-1, r-1)

See details

Explanation

W(n,r)

C(n+r-1, r-1)

n

r

ExampleUse Case

This formula calculates the number of ways to distribute n identical items into r cells, allowing empty cells. It's a key concept in combinatorics that deals with the distribution of indistinguishable objects. The formula is derived using the clever 'stars and bars' method, which transforms the problem into choosing positions for dividers. Weak compositions are fundamental in generating functions and partition theory. They have applications in various fields, including number theory, statistical physics, and computer science. This concept is crucial in solving problems related to integer partitions, in the analysis of algorithms dealing with distributions, and in combinatorial optimization.

Strong Composition

S(n,r) = C(n-1, r-1)

See details

explanation

S(n,r)

C(n-1, r-1)

n

r

ExampleUse Case

This formula calculates the number of ways to distribute n identical items into r cells, with no empty cells allowed. It's a variation of the weak composition that adds the constraint of non-empty cells. The formula is derived by considering the problem as placing r-1 dividers among n-1 spaces between items. Strong compositions are fundamental in partition theory and have deep connections to symmetric functions and representation theory. They are used extensively in analyzing algorithms, particularly those involving distributions and partitions. This concept is crucial in combinatorial number theory, in studying integer partitions, and in certain areas of statistical physics.

Basic Permutations

Permutation (Full)Permutation with Repetition Circular Permutation

Variations

Permutation of Subset (Variations without Repetitions)Distribution into Cells (Variations with Repetition)

Combinations

Basic Combination Combination Symmetry

Partitions

Partition into Groups Weak Composition Strong Composition