[go: up one dir, main page]
Scribd
Upload
321 views8 pages

Math220 Discrete Math Test 3 Solutions

The document contains 16 math and programming questions with explanations and solutions. Some key details: - Question 1 involves distributing balloons to children and finding the number of ways to distribute remaining balloons. - Question 2 deals with counting the number of ways a student can choose subjects when they have 5 choices for each of 4 subjects. - Question 3 contains problems about distributing candies to children, with the first involving 2 candies among 4 children and the second involving 6 candies among 4 children. - Question 4 is about distributing certificates among bags with the constraint that each bag gets at least 1 certificate.

Uploaded by

geniusamit
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
321 views8 pages

Math220 Discrete Math Test 3 Solutions

The document contains 16 math and programming questions with explanations and solutions. Some key details: - Question 1 involves distributing balloons to children and finding the number of ways to distribute remaining balloons. - Question 2 deals with counting the number of ways a student can choose subjects when they have 5 choices for each of 4 subjects. - Question 3 contains problems about distributing candies to children, with the first involving 2 candies among 4 children and the second involving 6 candies among 4 children. - Question 4 is about distributing certificates among bags with the constraint that each bag gets at least 1 certificate.

Uploaded by

geniusamit
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 8

Q1)

because every children must have 1 balloon so Meg give 1 balloon to each child first
no of balloon remains = 25-16 = 9
So no of ways to distribute 9 balloons to 16 children is (

)=(

)


Q2)
each student have 5 choices :- he can chose from 1 to 5 no of subjects
so count = (

) (

) (

) (

) (




Q3)
a)
First i will give one candy to each one now 2 candies remain so no of way to give 2 identical
candies to 4 boys is = (

) =(

) = 10
b)
no of ways to give 6 candies to four boys = (

)=(

)=84

Q4)
because each bag should contain atleast 1 certificate so after putting 1 certificate to each
bag no of certificates remain =11-4=7
so no of ways to put 7 certificate in 4 bags are= (

)=(

)=120


Q5)
Multiplying generation function says that


by multiplying A(x) an B(x) we get


so

(

)(

) (

)(

) (

)(

) (




Q6)
Let x=and n= 3 we get



Put value of x and n we get
=>1-3*(-4

)+3*(3+1)*

/2 - 3*(3+1)*(3+2)*

/6
=>1+12

+96

+640




Q7)
Let we denote four families by x1,x2,x3 and x4
so we have to calculate x1+x2+x3+x4=36
given condition are 6x17 14x218 6x310 6x410
Let y1=x1-6
y2=x2-14
y3=x3-6
y4=x4-6
so now we have to calculate y1+y2+y3+y4=4
With conditions 0y11 0y24 0y34 0y44

Let S be the set of all nonnegative integral solutions of the equation y1+y2+y3+y4 = 4.
Let P1 be the property that y1>=2, P2 the property that y2>= 5, P3 the property that
y3>= 5, and P4 the property that y4>=5. Let Ai denote the subset of S consisting of the
solutions satisfying the property Pi, 1 <= i <= 4. Then the problem is to find the cardinality

the inclusion-exclusion principle. In fact,



||=

=(

)=35
||=

=(

)=10
||=0
||=
||=
All intersection will be also zero
So answer will be 35-10=25


Q8) 1
#include<stdio.h>
#include<conio.h>
int sum_no(int n) {
if ( n == 1 ) return 1 ;
else {
return sum_no(n-1)+n ;
}
}
void main()
{
int N,b ;
int sum=0;
printf("Enter the value of N\n ");
scanf("%d" ,&N);
sum=sum_no(N);
printf(" Sum=%d\n" , sum);
}

Q8) 2 :- no previous algorithm didnt use tail recursion. Programme that use tail recursion is
as follows

#include<stdio.h>
#include<conio.h>
int tailSum_noAux(int k, int ksum, int n )
{
if ( k == n ) {
return ksum ;
} else {
return tailSum_noAux(k+1, ksum+(k+1), n) ;
}
}

int tailSum_no (int n)
{
return tailSum_noAux(1,1,n) ;
}


void main()
{
int N,b ;
int sum=0;
printf("Enter the value of N\n ");
scanf("%d" ,&N);
sum=tailSum_no(N);
printf(" Sum=%d\n" , sum);
}


Q8) 3
#include<stdio.h>
#include<conio.h>
void main()
{
int N,b ;
int sum=0;
printf("Enter the value of N\n ");
scanf("%d" ,&N);
b=1;
while(b<=N)
{
sum=sum+b;
// sum+=b
b++;
}
printf(" Sum=%d\n" , sum);
}



Q9)

=(n+1)


by expanding

=(n+1)(n-1+1)


=(n+1)(n)


=(n+1)(n)(n-1)


=(n+1)(n)(n-1)(n-2).........2


=!(n+1) * 7


Q10)
1)
T(n)=3 if n=1
T(n)=2T(

)+1 if n>1


2)
(n)


Q11)

=-2

+15


From this we get the equation

+2r-15=0
=>(r+5)(r-3)=0
So solution is


Now put value of

and

in this equation we get


2=

....................................(1)
-2=

-5

.....................................(2)

by solving (1) and (2) we get

=1 and

=1

so solution of recurrence relation is













Q12)
1)


2)
both strategies have same time complexity but choosing largest element first cut many
branches of tree with the help of condition (if t<s return) . so largest element first is slighter
better choice.



Q)13

=-3

-3


From this we get the equation

+3r+1=0
=>

=0
So solution is


Now put value of

and

in this equation we get


-4=

....................................(1)
-4=

-2

-3

....................................(2)
0=

....................................(3)
by solving (1), (2) and (2) we get

=-21 and

=27 and

=-10

so solution of recurrence relation is





Q14)
S(n,k) the Stirling number of the 2nd kind
given n= 9 distinguishable books and k= 4 identical displays
so answer is S(9,4)



S(n,k)=

]
=7770


Q15)
1)
With the help of masters theorem we get a=2 , b=4
so

=1 so complexity is (

)

2)
With the help of masters theorem we get a=1 , b=5
so

=1 so complexity is ()


Q16)

=-2

+15


given

=2 ,

=-2 and

=-2 ,

=15
let

be the generating function for


Where

+(

)Z
=2+2Z
And

= 1-


=1+2-


=(1+5Z)(1-3Z)
so




S(n,k)=


So solution is

You might also like