Combinatorial Proofs and Functions Assignment - CIT592

This math assignment solution covers several key concepts in discrete mathematics. It begins with an analysis of Pascal's Triangle, demonstrating Pascal's Identity and the relationship between the sums of consecutive rows. The assignment then delves into combinatorial proofs, specifically addressin...Read More

Mathematics Assignment
Student Name:
Instructor Name:
Course Number:
21st September 2019

1.)
Pascal’s Triangle coefficients
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Pascal’s Identity has it that
( n
k ) =( n−1
k−1 )+ ( n−1
k )
Taking row six, in the position 2 of row 6 we have ( 6
2 ) =15.Thus with n=6 we have
∑
k=0
6
(6
k )= (6
0 )+ (6
1 )+ (6
2 )+ (6
3 )+
(6
4 )+
(6
5 )+ (6
6 )
But (6
0 )=1∧(6
6 )=1
( 6
1 ) =( 5
0 ) + ( 5
1 )=1+5=6
(6
2 )=
(5
1 )+
(5
2 )=5+10=15
( 6
3 ) =
( 5
2 ) +
( 5
3 )=10+10=20
( 6
4 )= ( 5
3 )+ ( 5
4 )=10+5=15
( 6
5 ) =
( 5
4 ) +
( 5
5 )=5+1=6

∑
k=0
6
(6
k )= (6
0 )+ (6
1 )+ (6
2 )+ (6
3 )+(6
4 )+(6
5 )+ (6
6 )
∑
k=0
6
( 6
k )=1+6+15+20+15+6+1=64
∑
k=0
6
(6
k )=64
Taking row five, in the position 3 of row 6 we have ( 5
3 )=10.Thus with n=5 we have
∑
k=0
5
( 5
k )= ( 5
0 ) +
( 5
1) + ( 5
2 ) +
( 5
3 ) + ( 5
4 ) + ( 5
5 )
But (5
0 )=1∧(5
5 )=1
( 5
1 )= ( 4
0 )+ ( 4
1 )=1+4=5
(5
2 )= (4
1 )+ (4
2 )=4+6=10
( 5
3 )= ( 4
2 )+ ( 4
3 )=6+4=10
(5
4 )= (4
3 )+ (4
4 )=4+1=5
∑
k=0
5
( 5
k )= ( 5
0 ) +
( 5
1) + ( 5
2 ) +
( 5
3 ) + ( 5
4 ) + ( 5
5 )
∑
k=0
5
( 5
k )=1+5+10+10+5+1=32
∑
k=0
5
(5
k )=32
∑
k=0
6
(6
k )=64 And ∑
k=0
5
( 5
k )=32
64=2×32

[∑
k=0
6
(6
k ) ]=2 [∑
k=0
5
(5
k ) ]
Conclusion: The sum of each row of a Pascal’s triangle is twice the sum of the previous row.
2.)
 Counting question: How many 2-element subsets are there of the set 2n?
 Answer 1 (Left Hand Side)
There are 2n elements, from which one may choose 2.Thus this can be done (2 n
2 )ways .
 Answer 2 (Right Hand Side)
The possible choices are (n
2 )(n
0 ), (n
1 )(n
1)∧(n
0)(n
2)
Total number of ways is;
(n
2 )(n
0 )+ (n
1 )(n
1 )+
(n
0 )(n
2 )
¿ ( n
2 )( n
0 )+ ( n
1 )( n
1 ) + ( n
0 )( n
2 )
=
(n
2 )(n
0 )+ (n
1 )2
+ (n
0 )(n
2)………………………………………….equation i
But (n
0 )=1 and (n
1 )(n
1 )=
(n
1 )2
For n ≥ 2 , (n
1 )2
=n2 And also ( n
2 )= ( n
n−2)
Replacing But (n
0 )=1, ( n
1 )
2
=n2 and (n
2 )= ( n
n−2 ) in equation i above we have;
1
( n
2 ) + ( n
1 )
2
+1 ( n
2 )=1
( n
2 ) +1 ( n
2 ) + ( n
1 )
2
=( n
2 ) + ( n
n−2 ) +n2
Since these two are answers to the same question we may conclude that they must be equal.
 Conclusion: Left Hand Side=Right Hand Side

3.)
a)
Suppose we have two sets P and Q with P having a elements and Q having b elements, the number of
different functions with domain P and codomain Q can be found by the formula ba i.e.
Number of functions with domain P and codomain Q =ba
Let P = [p…q] and Q== r…s]
P and Q each have two elements.
a=b=2
Number of functions with domain P and codomain Q =ba=22=4
Number of functions with domain P and codomain Q are 4.
b)
Suppose P = [p…q].The number of its elements will be 2.
The number of distinct functions shall be determined using the formula 2|P | where |P| are the
elements in set P.
The number of distinct functions=2|P |=22=4
The number of distinct functions are 4.
4.
a)
The function is not injective.
Proof
The two elements b and c in the domain are mapped on one element i in the codomain.
The function is not surjective.
Proof
The two elements o and u in the codomain have been left out without being mapped to any element in
the domain.
Conclusion: The function is neither surjective nor injective.

For the function to qualify as subjective, every element in the codomain must have at least one element
in the domain. In the domain and codomain we shall have elements a, b, d and a, i, e respectively.
For the function to qualify as injective, b must be mapped on i. In the domain and codomain we shall
have elements a, b, d and a, i, e respectively.
Conclusion: The restricted domain and codomain shall have elements a, b, d and a, i, e respectively.
b)
The function is not subjective.
Proof
Suppose S is a subset f maps h to the set h(S),we may define D as set of all elements x in A such that x
does not belong to f(x).This is so since f(x) is a subset of h and a is in A.
D is therefore the set of the elements of A that lack this property .Elements of D are in h(S) as it is a
subset of A.
If x ∈ D then x ∈ f(x ¿
 f(x ¿= D since x ∈ D then x ∈ f(x ¿
 If x ∈ D then x ∈ f( x ¿thus f( x ¿= D
D=f ( x ) D for all x ∈ h hence f is not surjective.
The function is not injective.
Proof
The function will be injective only if it never maps distinct elements of its domain to the same element
of the codomain. However this is not possible with finite subsets of h. Hence h is not injective.
Conclusion: The restricted domain and codomain shall have elements of real number.