Discrete Math. For students of technical specialties

Task: 9 camels go in a bargain. How many combinations of camel rearrangements exist, in which no camel follows the one he followed earlier?

We distinguish the forbidden pairs: (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7),

(7, 8), (8, 9) To solve, we apply the main theorem of combinatorics.

To do this, we define what an object is and what properties are. By objects we mean various arrangements of camels. In total there will be N = 9!. By properties we mean the presence of a certain pair

in the permutation. Thus, the number of properties is 8. Then the number of permutations that do not have any of the 8 properties: N (8) =9! -C81*8!+C82*7! -C83*6!+C84*5! -C85*4!+C86*3! -C87*2!+C88*1!=142729=D9=D8

In the general case, for n camels, we have: Dn+Dn-1

2.5.3. Problem about disturbances

Set we denote all permutations by S, and the list of properties will consist of properties pi: property pi is the property of this or that substitution to leave elementin place i. It is clear that disorder is just such a permutation that does not have any properties from P= {p1,…,pn}. Following the inclusion-exclusion formula, we get: N=M-∑i=1nS(pi)+∑i,jS(pipj)-…+(-1)k∑pi1,pi2,…pik,S(pi1,pi2,…pik)+…+(-1)nS(p1,p2,…pn) =n! -Cn1 (n-1)!+Cn2 (n-2)! -…+ (-1) kCnk (n-k)!+…+ (-1) n=n! (1—1+ (1) / (2!) – (1) / (3!) +…+ (-1) k/ (k!) +…+ (-1) n/ (n!)) ≈ (n!) / (e).

2.6. The concept of a lattice, a distributive lattice

A lattice is a partially ordered set in which each two-element subset has both an exact upper (sup) and an exact lower (inf) face. This implies the existence of these faces for any nonempty finite subsets.

Any two elements in such a partially ordered set must be comparable: ∀a,b must be either a ≤ b ∨ b ≤ a.

Precision (smallest) of the upper edge (boundary) or supremum subset X ordered set (or class) M, is the smallest element M, which is equal to or more than all of the elements of X.In other words, the supremum is the smallest of all the upper faces.

More ∈ formally: SX= {yM | ∈ ≤

the set of upper bounds of X, that is, elements of M, equal to or greater than any element X.

s=sup sup X ⇔ ∈ s Sx ∧ ∀y ∈ Sx: s ≤ y)

H=sup sup (a,b) = ∧ – the exact upper face of the two elements.

Precision (maximum) of the bottom face (boundary) orinfimum subset X of an ordered set (or class) M, is called the largest element M, which is equal to or less than all of the elements of X.In other words, the infimum is the largest of all the lower faces.

L=inf inf (a,b) = ∨ – the exact lower bound of the two elements.

Theorem: if the lower (upper) face exists, then it is unique.

Proof: x=inf inf (a,b) ∧ y =inf inf (a,b) ⇒ y≤x ∧ x≤y ⇒ x=y

THEOREM IS PROVED.

A lattice is called distributive if sup and inf are distributive:

a∪ (b⋂c) = (a∪b) ⋂ (a∪c),a⋂ (b∪c) = (a⋂b) ∪ (a⋂c), (2.6.4)

Lemma: the set of natural numbers N+ is a lattice with respect to operations ≤,max, min.

Proof: by definition, a lattice is a partially ordered set. Let us show that the set of natural numbers is a partially ordered set. Moreover, a linearly ordered set.

Consider the relation ≤. This is a relation of order because it is:

– Reflective:∀a ∈ N,a ≤ a

– Transitive: ∀a,b,c ∈ N,a ≤ b ⋂ b ≤ c ⇒ a ≤ c

– Antisymmetric: ∀a,b ∈ N,a ≤ b ⋂ b ≤ a ⇒ a = b

In addition, there are many natural numbers linearly ordered, because: ∀a,b ∈ N,a ≤ b ⋂ b ≤ a)

To prove that the set N is a lattice, it remains to show that for any two-element subset X ⊂ N there are exact upper and lower faces. This follows from linear ordering. X= {a,b}

Supposeb a ≤ b. Then: in fX=a, supX=b

Similarly, we can reason for another case.

APPROVED PROVEN

2.7. The principle of mathematical induction

Formulation: suppose that it is required to establish the validity of an infinite sequence of statements numbered by natural numbers: P (1),P (2),…,P (n),P (n+1).

Assume that:

– It is established thatP (1) is true (this statement is called the base of induction).

– For anyn, it is proved that ifP (n) is true, thenis trueP (n +1) (this statement is called the induction transition).

Then all the statements of our sequence are true.

Proof:

– induction basis. Let P (1) be true, i.e.holds P (k) for some k ∈ N+.

– inductive step. If (P + k) – true, then ∀n ∈ N+ P (n) – true.

We prove that the method of mathematical induction can be applied using the method of proof by contradiction. Suppose that for some numbers in the natural series the method of mathematical induction is incorrect.

Let them form the set N» ⊆ N+. N+ is a lattice with respect to the operations ≤,max, min (by the lemma proved in Section 2.6); therefore, N», as its subset, is also a lattice ⇒ ∃m | ∀k ∈ N»(m,k) =m.

– If m = 1, then a contradiction with (a) the condition.

– If m ≠ 1, then (m – 1) is not natural.

P (m – 1 +1) is true (by condition (b)); therefore, P (m) is true (a contradiction to condition (b)).

PRINCIPLE PROVED

2.8. The Cantor diagonal method

If each element of the set X corresponds to a single element from the set Y, then it is said that a one-to-one correspondence is established between these sets.

Consider 2 infinite sets: the

– set of natural numbers 1, 2, 3, 4, 5, …, n, …;

– the set of even positive integers 2, 4, 6, …, 2n, … (this is a subset of the first set).

Since a series of even numbers can be numbered using natural numbers, a one-to-one correspondence can be established between these two sets. If a one-to-one correspondence cannot be established between a set and its certain subset, then the set is finite.

A set equivalent to a set of natural numbers is called countable. In other words, a countable set can be established one-to-one correspondence with a set of natural numbers.

Theorem: the set of real numbers of the interval [0, 1] is uncountable.

Proof (by diagonalization method): each number is represented as an infinite decimal fraction: 0. a1 a2 a3… consisting of digits and not having a period of 9. Suppose that some countable set (of all or only some) of real numbersalying on the interval [0, 1]. Then they can be arranged as a list of lines:

0. a11 a12 a13 a14…

0. a21 a22 a23 a24…

0. a31 a32 a33 a34…

…

Consider the sequence of numbers: b1≠a11,b2≠a22,b3≠a33,…,not equal to 9. Then the number 0. b1 b2 b3is… not in the list, although it is in the interval on the segment [0, 1]. This means that all real numbers from this segment cannot be enumerated using natural numbers. Thus, no countable set of real numbers lying on the segment [0, 1] does not exhaust this segment.

THEOREM IS PROVEN.

2.9. The principle of transfinite induction

Transfinite induction is a method of proof that generalizes mathematical induction to the case of an uncountable number of parameter values.

Transfinite induction is based on the following statement.

Statement: let a completely ordered setbe given A. P (x),x ∈ A is a statement. Suppose that for each element of the set A, since P (y) is true for all y <x, it follows that p (x) is true. Then the statement P (x) is true for any x.

Mathematical induction is a special case of transfinite induction. Indeed, let M be the set of natural numbers. Then the statement of transfinite induction turns into the following: if for any positive integer n the truth of statements P (1), P (2), …, P (n – 1) implies the truth of statement P (n), then all statements P (n) Moreover, the induction base, that is, P (1), turns out to be a trivial special case for n = 1.

2.10. Newton’s binomial

2.10.1. Case of two variables

Formula (Newton’s binomial). A formula for decomposing into separate terms a non-negative integer power of the sum of two variables, having the form: (a+b) n=∑k=0nCnkankbk

Proof (by induction). We have the formula: (a+b) n=∑k=0nCnianibi= Cn0an+ Cn1an-1b1+…+Cnna0bn

Induction base: for n = 2, the statement is obvious: (a+b) 2=C20a2b0+ C21a1b1+C22a0b2=a2+2ab+b2

Induction step: suppose that the statement is true for n – 1 and show that it will be true for n. (a+b) n-1=∑i=0n-1Cn-1ian-1-ibi

(a+b) n= (a+b) n-1* (a+b) = ∑i=0n-1Cn-1ian-1-ibi* (a+b)

Which is equivalent: (Cn-10an-1b0+Cn-11an-2b1+…+Cn-1n-1a0bn-1) * (a+b)

And: Cn-10anb0+Cn-11an-1b1+…+Cn-1n-1a1bn-1+Cn-10an-1b1+Cn-11an-2b2+…+Cn-1n-1a0bn

Group the terms: Cn-10an+ (Cn-10+Cn-11) an-1b1+…+Cn-1n-1bn

Using the proven earlier identity Cnk=Cn-1k+ Cn-1k-1 we get:

Cn0an+Cn1an-1b1+Cn2an-2b2+…+Cnnbn

WHAT YOU NEED TO PROVE.

2.10.2. Ordered partitions and the generalized

Newton bin recall that a partition of a set A is the family {Ai} of its pairwise disjoint subsets such that: ∪i Ai=A. Thesubsets Ai are called partition blocks. If the family takes into account the order of the subsets, then it is called an ordered partition. We say that the ordered partition (A1,A2,…,Am of the) set E= {e1,e2,…,en} is of type (k1,k2,…,km) if |A1|=k1,|A2|=k2,…,|Am|=km. The number of such partitions is denoted by P (k1,k2,…,km) or Pn (k1,k2,…,km), where n=k1+k2+…+km.

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

This is the number of permutations with repetitions. For the proof of this formula, see §2.4.

Theorem: (x1+x2+…+xm) n=n!∑k1+k2+…+km=n ((1) / (k1!k2!…km!)) x1k1x2k2…xmkm

Proof: we consider how the boxes are factors of the product: (x1+x2+…+xm) (x1+x2+…+xm) … (x1