Discrete Math. For students of technical specialties

1.23. The principle of duality

In Boolean algebras, there are dual statements; they are either true or false at the same time. Namely, if in a formula that is true in some Boolean algebra, change all conjunctions to disjunctions, 0 to 1, ≤ to ≥ and vice versa, then we get a formula that is also true in this Boolean algebra. f (x1,x2,…,xn) ∈ Pn

f (x1,x2,…,xn) = f (x1,x2,…,xn) is the dual function f.

Theorem: duality is foreign-valued: (f*) *=f

Proof: f* = f (x1,x2,…,xn)

(f*) *=f (x1,x2,…,xn) def= f (x1,x2,…,xn)

THEOREM IS PROVED.

A function is called self-dual if f*=f.

Theorem: let φ (x1,x2,…,xn) be realized by the formula:

f (f1 (x1,x2,…,xn),…,fn (x1,x2,…,xn))

then the formula :

f* (f1* (x1,x2,…,xn),…,fn* (x1,x2,…,xn))

implements the function:

φ (x1,x2,…,xn)

Proof: φ* (x1,…,xn) =φ (x1,…,xn) =φ (x1,…,xn) =f (f1 (x1,…,xn),…,fn (x1,…,xn)) =f (f1 (x1,…,xn),…,fn (x1,…,xn)) = f (f1* (x1,…,xn),…,fn* (x1,…,xn)) =f* (f1* (x1,…,xn),…,fn* (x1,…,xn))

THEOREM IS PROVEN.

Corollary: Ф1=Ф2⇒ Ф1*=Ф2*.

Further, proving a theorem, by the principle of duality we immediately get a dual theorem: x1 ∨ x2= x1 ∧ x2

x1 ∧ x2= x1 ∨ x2

By normal form we mean a syntactically unique way of writing a formula. We introduce a special kind of entry: xy=x ≡ y, if x = y, xy=1, if x ≠ y, xy=0

The decomposition theorem of a Boolean function can be represented as a disjunctive conjunction of conjunction: f (x1,x2,…,xm, xm+1,…,xn) =||= δ1, δ2,…,δmx1δ ∧ x2δ ∧…∧ xmδm ∧ f (δ1, δ2,…,δm, xm+1,…,xm)

where disjunctions are taken over all possible δ.

Proof: in order to prove that a given formula implements a function, it is enough to take an arbitrary set of argument values, calculate the values of formulas on this set and, if it turns out to be equal to the value of the function, then the formula really implements the function:

(δ1, δ2,…,δmx1δ ∧ …∧ xmδm ∧ f (δ1,…,δm, xm+1,…,xn)) (a1,a2,…,an) =δ1, δ2,…,δma1δ1 ∧ …∧ amδm ∧ f (δ1,…,δm, am+1,…,an) = aa1 ∧ a2a2 ∧ …∧ amam∧ f (a1,a2,…,an) = f (a1,a2,…,an)

THEOREM IS PROVED.

1.24. Perfect normal forms

All algebraic terms of a formula include all variables. It is said that a certain class of formulas K has a normal form if there is another class of formulas K», which are called normal forms, such that any formula of the class K has a unique equivalent formula from the class K»: ∃K! ∀Ф∈K∃!Г∈K»∨Ф=Г

1.24.1. Perfect Disjunctive Normal Form

Representation of a Boolean function in the form (a disjunction is a union sign):

f (x1,x2,…,xn) =δ1, δ2,…,δmx1δ1 ∧ x2δ2 ∧ …∧ xnδn

is called a perfect disjunctive normal form (SDNF).

Theorem: ∀f ∈Pn ∨ {0} ∃ the only representation in the form of SDNF.

Proof: we use the decomposition theorem for a Boolean function:

f (x1,x2,…,xn) =δ1, δ2,…,δnx1δ1 ∧ …∧ xnδn ∧ f (δ1,…,δn)) =f (δ1, δ2,…,δn) =1x1δ ∧ …∧ xnδn ∧ f (δ1,…,δn)) =f (δ1, δ2,…,δn) =1x1δ ∧ …∧ xnδn

THEOREM IS PROVED.

Theorem: every Boolean function can be expressed in terms of disjunction, conjunction and negation: ∀f ∈Pn∃Ф {¬, ∨, ∧} |funcФ=f

Proof:0=x ∧ x. In other cases, see the theorem above.

THEOREM IS PROVEN.

1.24.2. Perfect conjunctive normal forms

Theorem: every Boolean function can be represented in the form:

f (x1,…,xn) =f (δ1, …,δ2) =1x1δ ∨ … ∨ xnδn

Proof: by the duality principle from the SDNF theorem, it can be argued that every Boolean function has an SKNF.

Q.E.D.

1.25. Closed classes of Boolean functions

Let F be the set of Boolean functions: F= {f1,f2,…,fn},∀ifi∈ Pn

The closure of the set F is the set of Boolean functions realized by formulas over F: [F] = {f∈ Pn | f=func Ф [F]}

We introduce a special type of classes of Boolean functions.

– T0= {f|f (0,0,…,0) =0} – a class of functions that preserves 0;

– T1= {f|f (1,1,…,1) =1} – a class of functions that preserves 1;

– T*= {f|f =f*} is the class of self-dual functions;

– T≤= {f|α≤β⇒f (α) ≤f (β),α= (α1,α2,…,αn),β= (β1,β2,…,βn) ∀iai, bi∈ E2,α≤β ⇔ ∀iai ≤ bi is the class of monotonic functions;

– TL= {f|f=x0+C1x1+C2x2+…+Cnxn} is the class of linear functions.

Theorem: classes: T0,T1,T*,T≤,TL – closed.

Proof: in order to prove that some class is closed, it is enough to prove that if a function is implemented as a formula over this class, then it belongs to this class. The proof of the isolation of classes 4 and 5 is provided to readers as an exercise.

It can be proved that an arbitrary formula has this property by induction on the structure of formulas. The basis of each such induction is obvious. Functions from F are realized as trivial formulas over F. Thus, only inductive transitions need to be proved.

f0,f1,…,fn ∈ T0, Ф= f0 (f1 (x1,…,xn),…, fn (x1,…,xn)) = f0 (0,…,0) =0 ⇒ Ф ∈ T0

f0,f1,…,fn ∈ T1,, Ф= f0 (f1 (x1,…,xn),…, fn (x1,…,xn)) = f0 (1,…,1) =1 ⇒ Ф ∈ T1

f0,f1,…,fn ∈ T*,, Ф*= f0* (f1* (x1,…,xn),…, fn* (x1,…,xn)) = f0 (f1 (x1,…,xn),…, fn (x1,…,xn)) ⇒ Ф* ∈ T*,,

Q.E.D.

1.26. Completeness of a system of Boolean functions

As already mentioned, a Booleanis an arbitrary n-function place function f (x1,x2,…,xn), where xi ∈ {0,1}. The complete system of Boolean functions is denoted by E and has the following form: f1 (x1,x2,…,xk1) f2 (x1,x2,…,xk2) … fe (x1,x2,…,xke)

A system of functions Eis called complete if any of its Boolean functions can be expressed using f1, f2, … fe through superposition.

A superposition is a function f*, which is obtained from a function f using the following transformations:

– change of variable: f (x1,x2, xj, …,xn) f* = f (x1,x2, xj-1,y, xj+1, …,xn);

– substitution instead of xj of some function from the system.

f* = fi (x1,x2, xj-1, fe (x1,x2,…,xke),xj+1, …,xki)

Example: system of functions {¬, ∪, ⋂} =E1 is always complete, because each function of this system can be represented as SDNF, therefore, SDNF is a superposition through which any of the functions of the system can be expressed.

Example: the system of functions {¬, ∪} =E2 is also complete, since the missing function ∩ can be expressed in terms of the other two by the de Morgan rule and double negation:

x1 ⋂ x2= ¬ (¬ x1 ∪ ¬ x2)

Example: prove the completeness of the system: X → Y,0.

For clarity, this system can be written as follows: {→,0}. That is, we are given a system consisting of a Boolean function (implication) and a constant 0. With their help we can express the negation operation, for this we substitute the constant 0 instead of one of the variables:

X → 0= ¬ X ∪ 0 = ¬ X

Therefore, this system is complete.

Consider alternative definitions.

The set of Boolean functions of B= {f 1, f2,fm,…,…} is called a full system if any Boolean function can be implemented by the formula above B.

Theorem (on completeness): let two systems of functions frombe given P2: B1= {f1,f2,…} and B2= {g1,g2,…}. Then, if the system B1 is complete and each of its functions can be realized by a formula over B2, then the system B2 is also complete.

Proof: let h be an arbitrary function from P2. We show that it can be realized by the formula over B2.

Due to the completeness of B1 h is realized by the formula over B1, i.e. h= [ff1,f2,…]. In addition, by condition f1,f2,… are realized by formulas over B2, i.e. fi=Фi [g1,g2,…]. Therefore, in the formula Ф we can exclude the occurrence of symbols of functions f1,f2,…, replacing them with the corresponding formulas: Ф [Ф1 [g1,g2,…], Ф2 [g1,g2,…],…], (1.26.5)

The resulting expression defines a formula over B2that implements h.

THEOREM IS PROVEN

Example: the system {x,x ∧ y} is complete. Indeed, consider the systems B1= {x,x ∧ y, x ∨ y} and B2= {x,x ∧ y}. The system B1 is complete and, since x ∨ y= x ∧ y, then each function of this system is expressed by a formula over B2. Thus, the conditions of the completeness theorem are satisfied and, therefore, the system B2= {x,x ∧ y} is a complete system.

Example: the system {x|y} is complete. Indeed, consider the systems B1= {x,x ∧ y} and B2= {x|y}. We have: x|y= x ∨ y =xy. Therefore:

x|x=xx=x and xy=x|y= (y) | (x|y), (1.26.6)

Thus, each function of the system B1 is realized by a formula over B2. In addition, system B1 is complete. Therefore, the conditions of the completeness theorem are fulfilled and, therefore, B2= {x|y} is a complete system.

2. COMBINATORY

2.1. The basic principles of combinatorics

Theorem (principle of multiplication): if some action can be performed in k stages, and the number of possible ways of i-thstage is equal to ni (i=1,2,…,k),then the total number Nk of all possible ways of performing said action is calculated according to the formula:

Nk=n1*n2*…*nk=∏i=1kni, (2.1.1)

Proof: we use induction on the number of stages. If k = 1 then, obviously, N1 = n1 and, therefore, formula (2.1.1) is valid for k = 1.

Further, let k = 2. Then, since each of the n1 methods for implementing the first stage can take place with each of the n2 methods for implementing the second stage, then N2=n1*n2, i.e. formula (2.1.1) is also valid for k = 2.

Now suppose that formula (2.1.1) is valid for k = m – 1, i.e. the formula holds:

Nm-1=∏i=1m-1ni, (2.1.2)

Then, if k = m then, considering the first m – 1 stages as the first stage with the total number of implementation methods defined by the formula (2.1.2), and applying a result similar to the second step of induction, we obtain:

Nm=Nm-1*nm=∏i=1mni,

i.e. formula (2.1.1) is also valid for k = m.

THEOREM IS PROVEN.

Theorem: the number of elements of the Cartesian product is equal to the product of the numbers of the elements of the set participating in this Cartesian product:

|X×Y|=|X|*|Y|

Proof: Consider an action consisting of 2 stages. The first stage is the choice of the 1st element of an ordered pair. The second stage – the choice of the 2nd element of an ordered pair.

Then the 1st stage can be completed in |X| steps, the 2nd stage in |Y| steps. By the principle of multiplication,

THEOREM IS PROVED.

Theorem: the number of all possible functions from M to N, where the number of elements |M|=n, the number of elements |N|=m, is mn.

Proof: the first element from the set M can be mapped to m elements, the second element from the set M can be mapped to m elements, the third n etc. We get: m*m*…*m=∏i=1nmi=mn, where ∀i mi = m.

THEOREM IS PROVEN.

Theorem (addition principle): if object a can be obtained in n ways, object b – in m ways, then object «a or b» can be obtained in n + m – k ways, where k is the number of repeated methods. Set theoretic wording. If A ⋂ B ≠ ∅,then| ∪ || || || AB=A+B-A ⋂ |

Lemma: If A ⋂ B=∅,then |A ⋂ B|= 0,then |A ∪ |=|A|+|B|B.

Proof of the lemma: let A and B be finite sets such that A ⋂ B=∅, |A|=m, |B|=n. If the element a ∈ A can be selected in m ways, and the element b ∈ B – n ways, then the elementselected in x ∈ A ∪ B can be m + n ways. Let X1,X2,…,Xk be pairwise disjoint sets, Xi ⋂ Xj =∅, where i ≠ j. Then, obviously, the equality holds:

| ∪i=1kXi|= ∑i=1k|Xi|

The lemma is proved.

Proof of the principle: if we consider the union of two sets A and B, then we will not change anything if we consider a union of this kind:

A ∪ B=A ∪ (B\A)

It can be opened:

A ∪ B=A ∪ (B ⋂ A)

Now the number of union elements is:

|A ∪ B|=|A ∪ (B\A) |

Next we consider A ⋂ (B\A), which is equal to ∅. Accordingly, you can open the difference of the sets:

A ⋂ B ⋂ A= ∅ ⋂ B= ∅

We have the intersection of two sets, it is empty and there are the number of elements combining these sets. We use the lemma. We get:

|A ∪ B|=|A| + |B\A|

Further we consider the set B, it is:

B= (A ⋂ B) ∪ (B\A)

Moreover, if we take the intersection of these sets, we get:

(A ⋂ B) ⋂ (B\A) = ∅

Once again we return to the lemma and get: |B|= |A ⋂ B| ∪ |B\A|. Let us express from here: |B\A|, |B\A|= |B| – |A ⋂ B|

Substitute it in: |A ∪ B| =|A ∪ (B\A) | and get: |A ∪ B| =|A| + |B| – |A ⋂ B|

PRINCIPLE PROVED.

2.2. Placements

A placement with repetitions is the function f: {x1,x2,…,xm} → {y1,y2,…,yn}. Elements xi are called objects, and yj – drawers.

Placements with repetitions – combinatorial compounds made up of n elements of m. Moreover, each of the n elements may be contained as many times as desired or absent altogether.

Theorem: the number of all arrangements with repetitions is equal to the number of sequences {a1,a2,…,am} of numbers 1 ≤ ai ≤ n and, therefore, it is equal to nm.

Non-repetitive placements are combinatorial compounds made up of n elements of m each. In this case, two compounds are considered different if they either differ from each other by at least one element, or consist of the same elements, but located in different order.

Theorem: the number of placements without repetition is:

Anm= ((n!) / (nm)!)

Proof: the first item can be placed in n ways, the second – (n – 1), ⋅⋅⋅, mth– (n – m +1). We get: Anm=n (n-1) … (n-m+1) = ((n!) / (nm)!)

THEOREM IS PROVEN.

2.3. Combinations

Of a combination of elements of the set X is a subset of a finite set A ⊆ X. If |A|=k,|X|=n, then the subset A is called a combination of n in k, denoted by: Cnk. For example, combinations of the three colors of a seven-color rainbow will be described by subsets of three elements.

The combination can be interpreted as the placement of indistinguishable objects. Combinations are a k-element subset of a given set.

Theorem: the number of combinations of n over k is equal to:

Cnk= ((n!) / (k! (nk)!))

Proof 1: from the formulas: Akn=Ckn*k! and Ank= ((n!) / ((nk)!) – we get the necessary formula.

THEOREM IS PROVEN.

Proof 2: we consider an action consisting of two stages.

Stage I: n1=Cnk-1

Stage II: n2= (n-k+1) / (k), Cnk=Cnk-1* ((n-k+1) / (k))

Using this formula, we get: Cnk= ((n!) / (k! (nk)!))

THEOREM IS PROVEN.

Property 1: Cnk= Cn-1k-1+ Cn-2k-1 +…+Ck-1k-1

Proof (by induction): for n = 1, the induction basis holds.

For n = n +1: Cn+1k=Cnk-1+Cnk

Cn+1k=Cnk-1+Cn-1k-1+Cn-2k-1 +…+Ck-1k-1

((n+1)!) / (k! (n+1-k)!) = (n!) / ((k-1)! ((n-k+1)!)) + (n!) / (k! (n-k)!)

(n!* (n+1)!) / ((k-1)!*k (n-k)!* (n-k+1)) = (n!) / ((k-1)! (n-k)!* (n-k+1)) + (n!) / ((k-1)!*k (n-k)!)

(n+1) / (k (n-k+1)) = (1) / (n-k+1) + (1) / (k)

(n+1) / (k (n-k+1)) = (k+n-k+1) / (k* (n-k+1))

1 = 1 (true). Thus, the statement is true for any n.

PROPERTY PROVED

Proof (combinatorial):

Cnk=Cn-1k-1+Cn-2k-1 +…+Ckk-1+ CK-1k-1

Cn+1k=Cnk-1+Cnk

Cn-1k=Cn-1k-1+Cn-1k

Cn-1k=Cn-2k-1+Cn-2k

Cn-2k=Cn-3k-1+Cn-3k

…

Ck+1k=Ckk-1+Ckk

PROPERTY PROVED.

Property 2: Cnk=Cn-1k+Cn-1k-1

Proof:

((n-1)!) / (k! (n-1-k)!) + ((n-1)!) / ((k-1)! ((n-1-k+1)!)) = ((n-1)!) / (k! (n-1-k)!) + ((n-1)!) / ((n-1)! (n-k)!)) = ((n-1)! (n-k)) / (k! (n-k)!) + ((n-1)!k) / (k! (n-k)!) = ((n-1)! (n-k+k)) / (k! (n-k)!) + (n!) / (k! (n-k)!)

PROPERTY IS PROVED.

Property 3: Blaise Pascal suggested to consider and illustrate the properties associated with binomial coefficients, consider the Pascal triangle.

Fig. 2.1 – Pascal Triangle

Theorem:∑k=0n Cnk=2n

Proof (combinatorial): on the left side of the equality is the number of all possible subsets of the set – by the Boolean theorem this number is 2n.

THEOREM IS PROVEN

Proof (by induction):

– For k = 0: ∑k=00 C0k=C00=1=20 the ⇒ equality is true.

– Assume that the equality holds for k = n, we prove the equality for k = n +1, i.e. we prove the equality: ∑k=0n+1 Cn+1k=2n+1=2* ∑k=0nCnk, or: Cn+10+Cn+11+Cn+12+Cn+13+…+Cn+1n-1+Cn+1n+Cn+1n+1=2 (Cn0+Cn1+Cn2+Cnn-2+Cnn-1+Cnn), (2.3.1)

To prove equality (2.3.1), we use: Cn+1k=Cnk-1+Cnk, (2.3.2)

Let us prove this equality: (n! (N+1)) / (k! (nk)! (n-k+1)) = (n!k) / (k! (nk)! (n-k+1)) + (n!) / (k! (nk)!)

(n+1) / (n-k+1) = (k) / (n-k+1) +1 ⇔ (n+1) / (n-k+1) = (n+1) / (n-k+1) the ⇒ equality (2.3.2) is proved. We return to the proof of (2.3.1): using equality (2.3.2) we obtain that: Cn+11=Cn0+Cn1;Cn+12=Cn1+Cn2

…

Cn+1n-1=Cnn-2+Cnn-1;Cn+1n=Cnn-1+Cnn

i.e. equality (2.3.1) takes the form: Cn+10+Cn+1n+1=Cn0+Cnn;1+1=1+1⇒

THEOREM IS PROVED.

Property 4: Cmn=Cmmn is the symmetry of the Pascal triangle.

Proof: (m!) / (n! (m-n)!) = (m!) / ((m-n)! (m-m+n)!)

PROPERTY PROVED.

Property 5: CniCim=CnmCnmim

Proof: (n!) / (i! (n-i)!) * (i!) / (m! (i-m)!) = (n!) / (m! (n-m)!) * ((n-m)!) / ((i-m)! (n-m-i+m)!)

PROPERTY PROVED.

Suppose there are objects of n different kinds, and from them are made up sets containing k elements. Such samples are called repeat combinations. Their number is denoted by Cnk.

Theorem: The number of combinations with repetitions can be calculated by the formula: Cmn=Cn+m-1n= ((n+m-1)!) / (n! (m-1)!), (2.3.3)

Example (cake problem): let it be required in the store to buy 7 cakes. The store has cakes of one of the types: eclairs, sand, puff, Napoleon. How many choices?

With each purchase we put in correspondence a sequence consisting of seven units and three delimiters 0. A total of 4 types of cakes, then zeros – 3.

Option table Table 2.1

Summarize the previous problem. The number of purchase options is equal to the number of permutations of n type I elements (units (cakes)) and m type II objects (zeros (delimiters)). Thus, rearranging by all means n units and (m – 1) zeros, we get the desired number:

P (n,m-1) = ((n+m-1)!) / (n! (m-1)!) =Cmn

The solution to the generalized purchase problem is a proof of (2.3.3).

2.4. Number of permutations

Letbe given n1 elements of the first type, n2 – the second type, …, nk – thek-th type, total n elements. Ways to place them in n different places are called repetitive permutations. Their number is denoted by:

Pn (n1,n2,…,nk)

Theorem: the number of permutations without repetition is:

Pn (k1,k2,…,km) = (n!) / (k1!k2!…,km!)

Proof: a subset of A1 can be chosen Cnk1 in ways. A subset of A2 is selected from the remaining (n – k1) elements, it can be selected in Cn-k1k2 ways. A subset of A3 – Cn-k1-k2k3 ways, etc. Select a subset Am defined by previous subsets. From here we get: P(k1,k2,…,km)=Cnk1Cn-k1k2…Cn-k1-… -km-2km-1= (n!) / (k1! (n-k1)!) * ((n-k1)!) / (k2! (n-k1-k2)!) … ((n-k1-… -km-2)!) / (km-1! (n-k1-… -km-2-km-1)!)

Since n-k1-… -km-1= km, then after reducing the fraction we get the desired equality.

THEOREM IS PROVEN.

The number of one-to-one functions, or the number of permutations of n objects, is denoted by P (n).

Theorem: the number of permutations of elements is n! or n elements can be rearranged n! way, i.e. P (n) =n!

Proof: we can put the first item in one of n positions, the second in (n – 1), etc., the last item can only be put in one place, and this is the definition of n!:

P (n) =Ann=n* (n-1) *…* (n-n+1) =n* (n-1) *…*1=n!, (2.4.4)

THEOREM IS PROVED.

Comment. Fair recurrence formula: P (n) =n*Pn-1

2.5. Inclusion and exclusion formula (main theorem)

The formulas and algorithms given in the previous sections give methods for calculating combinatorial numbers for some common combinatorial configurations. Practical tasks are not always directly reduced to known combinatorial configurations. In this case, various methods are used to reduce some combinatorial configurations to others.

Consider the principle of inclusion and exclusion.

The rule (principle) of inclusion / exclusion allows you to calculate the power of the union of sets if their powers and powers of all intersections are known.

Theorem:|i=1nAi|=∑i=1n|Ai|-∑I≤i1≤i2≤n|Ai1 ⋂ Ai2 |+…+ (-1) k+1∑I≤i1≤…≤i2≤n|Ai1 ⋂ Ai2 ⋂…⋂ Aik |+ …+ (-1) n+1|Ai1 ⋂ Ai2 ⋂…⋂ Ain |

Proof: by induction, for n = 1, the statement is obvious.

For n = 2, we obtain the addition theorem, i.e. if A ⋂ B=∅,then|∪|| || ||AB=A+B-A⋂|

Let it be true for n – 1, we prove for n. Note that the relation holds: (i=1n-1Ai) ⋂ An= i=1n-1 (Ai ⋂ An)

and for (n – 1) it holds.

Let us prove for n: |i=1nAi|=| (i=1n-1Ai) ∪ An|=|i=1n-1Ai|+|An|-| (i=1n-1Ai) ⋂ An|= ∑i=1n-1|Ai|-∑I≤i 

Therefore, the statement is true for n sets.

Q.E.D.

Formulation using Euler-Venn diagrams: 3 setsare marked on the diagram A, B, C:

Fig. 2.2 – Illustration to the inclusion-exclusion formula

Then the area of the union A ∪ B ∪ C is equal to the sum of the areas A, B, C minus the twice-covered areas A ⋂ B,A ⋂ C,B ⋂ C, but with the addition of the three-times covered area A ⋂ B ⋂ C: S (A ∪ B ∪ C) =S (A) +S (B) +S (C) -S (A⋂B) -S (A⋂C) -S (B⋂C) +S (A⋂B⋂C)

In a similar way, it is generalized to the union of n sets.

2.5.1. A special case of the theorem on inclusions and exceptions

In some cases, the number of objects that have a certain set of properties depends only on the number of these properties. Then the formula for counting the number of objects that do not have any of the selected properties is simplified.

For arbitrary n we have: N (n) =n! -Cn1*N (1) +Cn2*N (2) -…+ (-1) nN (n)

In the general case, when rearranging n objects, the number of arrangements in which no object is located on in its place: N (n) =n! -Cn1* (n-1)! +Cn2* (n-2)! -…+ (-1) n0!=Dn

The resulting value of Dn is sometimes called a complete disorder formula or sub-factor. The subfactorial Dn can also be represented as follows: Dn=n! [1- (1) / (1!) + (1) / (2!) – (1) / (3!) +…+ (-1) n/ (n!)]

where the expression in […] tends to e-1 with an unlimited increase in n.

A subfactorial has properties similar to those of a regular factorial. For example:

– n!= (N-1) [(n-1)!+ (N-2)!] – for a regular factorial;

– Dn= (n-1) [Dn-1+Dn-2] – for the sub-factorial.

Subfactorials are calculated by the formula: Dn=nDn-1+ (-1) n

2.5.2. Caravan

Problem Let us consider a problem in which a solution can be obtained using the main combinatorics theorem.