Combinatorial objects

Lecture

Definition:

Combinatorial objects (English combinatorial objects) — finite sets whose elements may be subject to certain restrictions, such as: distinguishability or indistinguishability of elements, the possibility of repeating identical elements, and so on.

Definition:

If two combinatorial objects that differ only in the order of the elements are considered different, then they are called ordered (English ordered).

Combinatorial objects - are objects or structures that are studied in combinatorics, a branch of mathematics concerned with counting, analyzing and investigating combinatorial structures and their properties. Combinatorics deals with the enumeration, classification and analysis of combinations, permutations, arrangements, partitions and other combinatorial objects.

Some of the frequently studied combinatorial objects include:

Subsets: Combinatorics deals with counting the number of subsets in a given set and studying their properties.
Permutations: These are ordered sequences of elements. The study of the various ways of ordering elements bears on combinatorial problems.
Combinations: These are unordered sets of elements from a set. Combinations study how many ways one can choose k elements out of n, without regard to order.
Partitions: These are ways of dividing a set of elements into disjoint subsets.
Graphs: Combinatorial graphs, such as trees, Cayley graphs, etc., play an important role in combinatorics.
Binary sequences: The study of binary strings and their properties, such as Hamming graphs and error-correcting codes.
Integer partitions: The study of ways of representing integers as sums of integers, for example, the decomposition of a number into a sum of primes (number theory).
Generating functions: A tool used in combinatorics for analyzing combinatorial sequences and objects.

The study of combinatorial objects has many applications in various fields, including number theory, graph theory, cryptography, statistics and many other areas of mathematics and science.

Examples of combinatorial objects

Bit vectors

Definition:

Bit vectors (English bit vectors) — a sequence of zeros and ones of a given length.

Permutations

Definition:

Permutations (English permutations) — an ordered set of numbers 1,2,…,n, usually treated as a bijection on the set {1,2,…,n} that assigns to the number i the i-th element of the set.

An example of a permutation can be the problem of seating n people at a table in n seats.

Permutations with repetitions

Definition:

Permutations with repetitions (English permutations with repetitions) — the same permutations, but some elements may occur several times.

As an example one can give the following problem: there is a set of books {a1,a2,…,an}, each of which is available in k1,k2,…,kn copies respectively. How many ways are there to arrange the books on a shelf?

Arrangements

Definition:

An arrangement (English arrangement) of n taken k at a time — an ordered set of k distinct elements of some n-element set.

An example of an arrangement can be the problem of seating k people at a table in n seats, where n>k.

Arrangements with repetitions

Definition:

An arrangement with repetitions (English arrangement with repetitions), formed from given n elements taken k at a time — a mapping of the set of the k first natural numbers 1,2,…,k into the given set {a1,a2,…,an}.

As an example one can give the following problem: there are n books, each in k copies. In how many ways can a selection of books be made from those given?

Combinations

Definition:

Combinations (English combinations) of n taken k at a time — a set of k elements chosen from the given n elements.

An example of a combination can be the problem of choosing k books out of n options.

Combinations with repetitions

Definition:

Combinations with repetitions (English combinations with repetitions) — the same combinations, only now there are n types of elements from which one must choose k elements, where the number of elements of each type is unlimited, and elements of the same type must stand consecutively one after another.

As an example one can give the following problem: there are n pastries. How many ways are there to buy k pastries?

Partition into unordered summands

Definition:

A partition of a number into unordered summands (English partition) — a representation of the number n as a sum of summands.

Partition into subsets

Definition:

A partition of a set X into subsets (English partition of a set) — a family of non-empty sets {Uα},α∈A, where A — is some index set, if:

Uα∩Uβ=∅ for any α,β∈A such that α≠β;
X=⋃α∈AUα.

The number of combinatorial objects

Type of object	Number of objects
Bit vectors
Permutations	Pn=n!
Permutations with repetitions
Arrangements
Arrangements with repetitions
Combinations
Combinations with repetitions
Partition into unordered summands	Finding the number of partitions of a number into summands
Partition into subsets	Stirling numbers of the second kind

Corresponding proofs

Theorem:

The number of distinct bit vectors of length n equals 2ⁿ^.

Proof:

▹

The number of bit vectors — is a special case of an arrangement with repetitions of 2 elements taken n at a time. Thus, the number of distinct bit vectors will equal 2ⁿ.

◃

Theorem:

The number of distinct permutations of n elements equals Pn=n!

Proof:

▹

A permutation — is a special case of an arrangement of n elements taken k at a time with k=n. Thus, the number of distinct permutations will equal n!

◃

Theorem:

The number of distinct permutations with repetitions of k elements with n groups of identical elements equals Combinatorial objects

, where ki — is the number of identical elements in the i-th group.

Proof:

▹

Suppose we need to find the number of permutations with repetitions on a set A of k elements. We take into account that this set has n groups of identical elements. The number of permutations of k elements, without taking into account the fact that elements may be identical, will equal k!.

In each resulting permutation the situations with identical elements will be counted several times, exactly as many times as the number of permutations of ki that can be obtained. Thus the number of permutations with the same first element will equal k1!, for the second element — k2!. The total number of identical permutations will equal the product of these factorials. In total, identical permutations k1!⋅k2!⋅…⋅kn!. The answer will be the quotient of the number of all permutations and the number of identical ones.

We obtain that the resulting number equals Combinatorial objects

◃

Theorem:

The number of distinct arrangements of n elements taken k at a time equals Combinatorial objects

Proof:

▹

Proof by induction. Base k=1, then the number of arrangements of n taken 1 at a time equals n.

For k≥2 we use the product rule. The first element can be chosen in n different ways. For each first element, what remains forms an arrangement of the remaining set, that is, of (n−1) elements, taken (k−1) at a time. Consequently we obtain the recurrence formula Combinatorial objects

. From this we obtain Combinatorial objects

◃

Theorem:

The number of distinct arrangements with repetitions of n elements taken k at a time equals Combinatorial objects

Proof:

▹

Let us prove by induction. Base: k=1. Then Combinatorial objects .

For k≥2 we use the product rule. The first element can be chosen in n different ways. For each first element, what remains forms an arrangement with repetitions from the same set, that is, of n elements, taken (k−1) at a time. Consequently we obtain the recurrence formula Combinatorial objects

. From this we obtain Akn¯¯¯¯¯¯=n⋅n…=nk Combinatorial objects

◃

Theorem:

The number of distinct combinations of n elements taken k at a time equals Combinatorial objects

Proof:

▹

The total number of arrangements of n elements taken k at a time equals Combinatorial objects In each arrangement k elements are chosen from the given set. If we ignore the order of these chosen k elements, we obtain some combinations of the given set taken k at a time. In other words, arrangements with the same set of chosen k elements define the same combination of k elements.

Since arrangements with the same set of chosen k elements differ only in the order of the elements, and the number of distinct permutations of k elements equals k!, the resulting formula will equal Combinatorial objects

◃

Theorem:

The number of distinct combinations with repetitions of n elements taken k at a time equals Combinatorial objects

Proof:

▹

Consider a binary vector of (n+k−1) coordinates, in which there are (n−1) zeros and k ones.

We will regard the zeros as separators that divide this vector into n parts.

Then suppose that the number of ones in the i-th block — is the number of elements ki in the combination with repetition that corresponds to this vector, where ki — is the element of the original set with number i.

Example: If we have the set of elements 1 1 2 2 3, then k2 = 2.

We obtain that to each combination with repetitions of n taken k at a time there corresponds some vector of zeros and ones with (n+k−1) coordinates, in which there are (n−1) zeros. Conversely, from each such vector the combination with repetition corresponding to it is uniquely recovered. Hence, the number of combinations with repetitions of n taken k at a time coincides with the number of such vectors.

There are as many such vectors as there are ways to choose the k coordinates on which the ones must stand out of (n+k−1). Thus, the answer will be the number of combinations of (n+k−1) taken k at a time. Then the number equals Combinatorial objects

◃

Combinatorial objects

Examples of combinatorial objects

Bit vectors

Permutations

Permutations with repetitions

Arrangements

Arrangements with repetitions

Combinations

Combinations with repetitions

Partition into unordered summands

Partition into subsets

The number of combinatorial objects

Corresponding proofs

See also

Comments

To leave a comment

Lectures and tutorial on "Discrete Math. Set theory. Graph theory. Combinatorics."

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.