Джумадильдаев А.С. Элементы дискретной математики (часть 1)
Подождите немного. Документ загружается.
A
i
= {f ∈ Sym
n
| f(i)=i},i=1, 2,...,n.
0 <i
1
< ···<i
s
≤ n,
|A
i
1
∩···∩A
i
s
| =(n − s)!
n s
n
s
(i
1
,...,i
s
) 0 <i
1
< ···<i
s
≤ n
n
s
.
|A
1
∪···∪A
n
| =
n
s=1
(−1)
s+1
0<i
1
<···<i
s
≤n
|A
i
1
∩···∩A
i
s
| =
n
s=1
(−1)
s+1
n
s
(n −s)! =
n
s=1
(−1)
s+1
n!
s!
.
D
n
= |A
1
∪···∪A
n
| =
|Sym
n
|−|A
1
∪···∪A
n
| =
n!(
s≥0
(−1)
s
1
s!
).
F
on
(A, B)={f : A → B}
n
m
|F
on
(A, B)| =
m
s=0
(−1)
s
m
s
(m − s)
n
.
n =3,m=2 6=8− 2
A
1
∪ A
2
, A
1
A
2
• A
1
∩ A
2
= ∅
•|A
1
∩A
2
| =1
•|A
1
∩A
2
| =6
• A
1
⊆ A
2
x
1
+
x
2
+ x
3
+ x
4
=8 x
i
≤ 7, i =1, 2, 3, 4.
x
1
+x
2
+
x
3
=11 x
1
,x
2
,x
3
x
1
≤ 3,x
2
≤ 4 x
3
≤ 6.
{1, 2,...,1000}
2, 3, 5, 7
{1, 2,...,100}
{1, 2,...,n} σ ∈ Sym
n
σ(i) = i, i =1, 2,...,n.
{1, 2, 3, 4}.
{0, 1, 2,...,9}
q
k=1
(−1)
k−1
I∈
(
{1,2,...,n}
k
)
|
i∈I
A
i
|≤|
n
i=1
A
i
|,
q
q
k=1
(−1)
k−1
I∈
(
{1,2,...,n}
k
)
|
i∈I
A
i
|≥|
n
i=1
A
i
|,
q
n!=1·2·3 ···n f : n → n n = {1, 2,...,n}
Sym
n
|Sym
n
| = n!.
n
i
=
n(n − 1) ···(n − i +1)
i!
,n∈ Z,i∈ Z
+
.
C
i
n
C(n, i)
n
i
=0,
i>n.
n. n ∈ Z
+
n
i
=
n!
i!(n − i)!
,
−n
i
=(−1)
i
n + i − 1
i
.
n
k
A = {a
1
,...,a
n
} n P
k
(A)={B ⊆ A||B| =
k}
k. C
k
n
= |P
k
(A)|. B ⊆ A
k
a
n
∈ B B \{a
n
}⊆A\{a
n
} |B\{a
n
}| = k−1
C
k−1
n−1
.
a
n
∈ B B ⊆ A \{a
n
} |A \{a
n
}| = n − 1.
C
k
n−1
.
C
k
n
= C
k−1
n−1
+ C
k
n−1
.
C
0
1
=1,C
1
1
=1.
C
k
n
=
n!
k!(n − k)!
.
n
k
.
i n
n
i
.
i n
n+i−1
i
.
k
n n
n i
1
1 i
2
2
ii
···
i i
···
i
···
i
···
ii
i
1
i
2
··· i
k
A n k − 1
|A| = n + k − 1
k −1 n + k − 1
n+k−1
k−1
.
x
1
+ ···+ x
k
= n
x
i
i i =1, 2 ...,k.
n+k−1
k−1
.
1
11
121
13 31
14 6 41
1 5 10 10 5 1
C
i
n
i n C
i
n
=0 i<0
i>n.
C
i
n
= C
i
n−1
+ C
i−1
n−1
.
C
i
n
=
n
i
.
n
i
+
n
i−1
=
n+1
i
.
(x + y)
n
=
n
i=1
n
i
x
i
y
n−i
.
n
i=0
n
i
=2
n
.
n
i=0
(−1)
i
n
i
=0.
n
i
p n = p, 0 <i<p, p
2 6
15
4 4
x
1
+x
2
+
x
3
=4
u
(k)
=
∂
k
u
∂x
k u = u(x).
(u + v)
(n)
=
n
i=0
n
i
u
(i)
v
(n−i)
.
•F(A, B)={f : A → B} A B
•F
in
(A, B) A B
•F
on
(A, B) A B
A
n
m
= m · (m − 1) ···(m − n +1)
n m
A
n
m
=0, m<n.
A B n m
|F(A, B)| = m
n
,
|F
in
(A, B)| = A
n
m
,
|F
on
(A, B)| =
m
s=0
(−1)
s
m
s
(m − s)
n
.
A = {a
1
,...,a
n
} B = {b
1
,...,b
m
}.
f ∈F(A, B)
f(a
i
) ∈ B, i =1,...,n. f(a
i
) m
b
1
,...,b
m
. (f(a
1
),...,f(a
n
)) ∈
B ×···×B
n
m
n
|F(A, B)| = m
n
.
f ∈F
in
(A, B). Imf = {f(a
1
),...,f(a
n
)}
n B
Imf n B
m
n
A
= {b
1
,...,b
n
} n
B n!
A
. f
σ
, σ ∈ Sym
n
,
f
σ
(a
i
)=b
σ(i)
,
|F
in
(A, B)| =
m
n
n!=m(m − 1) ···(m − n +1).
f ∈F
on
(A, B). F
i
= {f ∈F(A, B) | f(a) = b
i
, ∀a ∈ A}
b
i
. f
A m − 1 B \{b
i
} :
f ∈F
i
⇒ f ∈F(A, B \ b
i
), |B \{b
i
}| = m − 1.
|F
i
| =(m − 1)
n
,i=1,...,n.
f ∈F
i
1
∩···∩F
i
s
f ∈F(A, B \{b
i
1
,...,b
i
s
}
|F
i
1
∩···∩F
i
s
| =(m − s)
n
.
(i
1
,...,i
s
) 1 ≤ i
1
< ···<i
s
≤ m
m
s
|F
1
∪···∪F
m
| =
m
s=1
(−1)
s+1
1≤i
1
<···<i
s
≤m
|F
i
1
∩···∩F
i
s
| =
m
s=1
(−1)
s+1
m
s
(m − s)
n
.
F
1
∪···∪F
m
,
F(A, B).
|F
on
(A, B)| = |F
1
∪···∪F
m
| = |F(A, B)|−|F
1
∪···∪F
m
| =
m
n
−
m
s=1
(−1)
s+1
m
s
(m − s)
n
=
m
0
(m − 0)
n
+
m
s=1
(−1)
s
m
s
(m − s)
n
=
m
s=0
(−1)
s
m
s
(m − s)
n
.
m
s=0
(−1)
s
m
s
(m − s)
m
=0, m<n.
n>
m.
|A| = |B| = n f ∈F(A, B).
• f
• f
• f
f ∈F
in
(A, B), f ∈F
on
(A, B).
ImA ⊂ B n.
a, a
∈ A
f(a)=f(a
). f
f ∈F
on
(A, B), f ∈F
in
(A, B).
a, a
∈ A f (a)=f(a
). |ImA| <n.
f
|A| = |B|
|A| = |B|
|Sym
n
| = n!.
m = n
|F
in
(A, B)| = A
n
m
= m(m − 1) ···(m − n +1).
m
s=0
(−1)
s
m
s
(m − s)
m
= m!.
n = m
|F
on
(A, B)| =
m
s=0
(−1)
s+1
m
s
(m − s)
n
.
|A| = |B| = m,
|F
on
(A, B)| =
m
s=0
(−1)
s+1
m
s
(m − s)
m
.
|A| = |B|,
|F
on
(A, B)| = |F
in
(A, B)|.
|F
in
(A, B)| = |Sym
m
| = m!
A
A = {
1
,
2
,
3
}.
B
B = { , , , }.
A → B, a → b, a
b 4
3
= 256
256.
A B
A → B, a → b, a b
|F
in
(A, B)| =6·5 · 4 · 3 = 360.
360.
A B
A →,a→ b, a
b
|F
on
(A, B)| =(−1)
0
3
0
(3 − 0)
4
+(−1)
1
3
1
(3 − 1)
4
+(−1)
2
3
2
(3 − 2)
4
+0=36.
36.
P (n)
n =1, 2,....
P (1)
P (n) P (n +1)
P (n) n
P (n)
1+3+5+···+(2n +1)=(n +1)
2
.
P (1) : 1 = (0 + 1)
2
.
P (n)
1+3+5+···+(2n +1)=(n +1)
2
.
1+3+5+···+(2n +1)+(2n +3)
=(n +1)
2
+(2n +3)=n
2
+2n +1+2n +3=n
2
+4n +4=(n +2)
2
.
P (n +1)
n.
n
i=0
m+i
i
=
n+m+1
n
.
n =0, 1, 2,.... n =0
n
n+1
i=0
m + i
i
=
n + m +1
n +1
+
n
i=0
m + i
i
=
n + m +1
n +1
+
n + m +1
m +1
=
n + m +1
m
+
n + m +1
m +1
=
n + m +2
n +1
n.
n ∈ Z
+
.
n
i=1
i = n(n +1)/2.
n
i=1
i
2
= n(n + 1)(2n +1)/6.
n
i=1
i
3
=(n(n +1)/2)
2
.
n
i=1
i
4
=(3n
2
+3n − 1)(2n +1)(n +1)n/30.
n
i=1
i
5
=(2n
2
+2n − 1)(n +1)
2
n
2
/12.
n
n
n n ≥ 8
x +1/x ∈ Z, x
n
+1/x
n
∈ Z, n ∈ N.
x
1
,x
2
x
2
+5x − 7=0.
n x
n
1
+ x
n
2
2
3
n
+1 3
n+1
.
0.1
n n 0.9
n
0.5
6
< 1/2 < 0.5
7
.
7
2
n
r.
a
2
n+1
=
2r
2
−2r
r
2
−
a
2
2
n
4
n
1/
√
3.
H
n
=1+
1
2
+
1
3
+ ···+
1
n
.
H
1
=1,H
2
=3/2,H
3
=11/6.
n
j=1
H
j
=(n +1)H
n
−n n ∈ N.
H
2
n
≥ n/2+1 n ∈ N.
n ∈ Z
+
n
j=1
jH
j
=
(n +1)nH
n+1
2
−
(n +1)n
4
.
a
n
a
1
=1,a
2
=2,a
n
= a
n−1
+ a
n−2
,n≥ 3.