Information Technology Reference
In-Depth Information
2, this part of the proof is similar to the previous one, but we have
to bear in mind that, in this case, it is the same consider an increment equal to 1
than an increment equal to
Now let m
=
1
n
1. For every A
∈ F
2 , we can define the n values
,
a
,
x 1
,
x 2
,...,
x n 1 to be
1
,
if
| Δ
A
(
i
) | =
1;
a
=
A
(
1
) ,
x i =
0
,
if
Δ
A
(
i
)=
0;
n
then there is a bijection between the set of sequences a
,
x 1 ,
x 2 ,...,
x n 1 and
F
2 ,
,
and clearly the number of different possibilities for the sequences a
,
x 1 ,
x 2 ,...,
x n 1
is equal to 2 n as it was stated, and the proof finishes.
n
n
n
n
It is clear that
F
= F
2 and
F
= F
3 . Therefore
,
2
,
,
3
,
F
2 =
F
3 =
n
2 n
n
3 n
.
and
,
,
n , m is obtained.
In the next theorem the cardinality of the rest of the sets
F
n
Theorem 4. Let m
>
3 . The cardinality of the set
F
m is given by
,
n
2 h
2 h
h
m [
]
h = 0
2
F
n , m =
3
rm
2 m [
]
r = 1
m
[
n rm
2
]
n
+
2 h
h = 0
+
.
(7.22)
rm
+
2 h
h
n
Proof. For every A
∈ F
m we define the n
+
1values a
,
x 1 ,
x 2 ,...,
x n to be
,
Δ
A
(
i
) ,
if
| Δ
A
(
i
) |≤
1
,
a
=
A
(
1
) ,
x i =
1
,
if
Δ
A
(
i
)=
m
1
,
1
,
if
Δ
A
(
i
)=
1
m
,
,
,
,...,
clearly the sequence a
x 1
x 2
x n determines the function A , so there is a bijection
n
,
,
,...,
F
between the set of sequences a
x 1
x 2
x n and the set
m . But now the values x i
,
satisfy the following relation
n
m
n
m
x i =
rm
, −
r
.
(7.23)
n
The number of functions A
∈ F
m for which r
=
0, clearly is given by
,
n
2 h
2 h
h
m [
]
h = 0
2
m , the number of A
n
and, for every r ,0
<
r
∈ F
m for which
x i =
rm or
,
x i =
rm is equal to
Search WWH ::




Custom Search