4. Brualdi 6.9
De termine the number of integral solutions of the equation
,
which satisfy
Answer:
Let 
. Then the given equation
becomes
with
Let S be the set of all non- negative integral solutions of
the equation .
Then, 
.
Let the set 
consist of solutions in S for which
We make a change of
variable ,
to get || which is the same as the number of non-negative
solutions of
the equation 
. Therefore
Let the set 
consist of solutions in S for which
We
make a change of variable ,
to get || which is the same as the number of non-negative
solutions of
the equation 
. Therefore
Let the set 
consist of solutions in S for which
We
make a change of variable,
to get || which is the same as the number of non-negative
solutions of
the equation 
. Therefore
Let the set 
consist of solutions in S for which
We
make a change of variable,
to get || which is the same as the number of non-negative
solutions of
the equation 
. Therefore
The set 
consists of solutions in S which have
and 
. Let
. Then, || is the same as the non-negative
integral
solutions of the equation
Thus, || = 0.
The set
∩ consists of solutions in S which have
and 
. Let
. Then, |
∩ | is the same as the non-negative
integral
solutions of the equation
Thus, 
.
Similarly, it can be easily verified that
By inclusion-exclusion principle we get that the number of
solutions of the equation
which satisfy
is
5. Brualdi 6.11
Determine the number of permutations of {1, 2, ..., 8} in which no even integer
is in its
natural position.
Answer:
Let S be the set of all permutations of {1, 2, ..., 8}. Then, |S| = 8!. Let
be the set
of all permutations of {1, 2, ..., 8} such that 2 is in its natural position.
Thus || = 7!.
Similarly, let be the set of all permutations of {1, 2, ..., 8} such that 4
is in its natural
position, be the set of all permutations of {1, 2, ..., 8} such that 6 is in
its natural
position. and let be the set of all permutations of {1, 2, ..., 8} such that
8 is in its
natural position, then we get
∩ is the set of all permutations of {1, 2, ..., 8} such that 2 and 4 is in
their natural
position, therefore || = 6!. Similarly, it can be easily verified that
6. Brualdi 6.12
Determine the number of permutations of {1, 2, ..., 8} in which exactly four
integers
are in their natural position.
Answer:
The number of ways to choose 4 integers such that they are in their natural
position
is
. The other 4 integers form derangements.
So the number of permutations of
{1, 2, ..., 8} in which exactly four integers are in their natural positions is
7. Brualdi 6.14
Determine a general formula for the number of permutations of the set {1, 2,
..., n} in
which exactly k integers are in their natural positions.
Answer:
The number of ways to choose k integers such that they are in their natural
position
is 
. The other n − k integers form
derangements. So the number of permutations
of {1, 2, ..., n} in which exactly k integers are in their natural position is
8. Brualdi 6.16
Use combinatorial reasoning to derive the identity
Define 
.
Answer:
We can partition the permutations according to the number of integers in their
natural
position. Since the number of permutations in which exactly k integers are in
their
natural positions is 
, we get that the total
number of permutations
9. Brualdi 6.20 Starting from the formula
, (n = 2, 3, 4, . . . ), give
a proof of Theorem 6.3.1.
Answer:
We need to prove for n ≥1
Proof is by induction:
Therefore 
As sume that the Theorem is true for n = k. Then we get
(by induction
hypothesis)
10. Brualdi 6.21
Prove that 
is an even number iff n is an odd number.
Answer:
(=>) If is an even number, then
is odd. Since
2, 3, . . . , (see Problem 6.20), we get 
is odd and hence n is odd.
(
) Proof by contradiction: Let n be an odd number and let
be an odd number.
Then, since is even and since
, n = 2, 3, . . . , we
get
is even. But since n is odd, we get that
is even. Therefore by (=>), n
− 1
is odd. Therefore n is even. This is a contradiction. Therefore
is an even
number
whenever n is an odd number.
