IGNOU BDP MTE 13 Discrete Mathematics Solved Assignment ENGLISH

Please make sure your assignment questions match your current IGNOU session

MTE 13 (January 2025 - July 2025) - ENGLISH

Assignment

(To be done after studying all the blocks)

Course Code: MTE-13

Assignment Code: MTE-13/TMA/2025

Maximum Marks: 100

1. Check whether the following statements are true or not. Justify your answers with a short proof or a counter example.

i) If the contrapositive of a statement is true, then the statement itself is also true.

ii) a_n+3a_n-1+2a_n-2= 2" is a linear homogeneous recurrence relation.

iii) A particular solution of the recurrence relation a_n-2a_n-1 + a_n-2=1 has the form Cn².

iv) There exists a boolean expression in variables x,x, and x, with CNF as

           

v) If a dice is rolled thrice, then the probability of getting a 6 each time is 

vi) Every odd cycle has the same chromatic and edge chromatic numbers.

vii) Every Eulerian graph is Hamiltonian.

viii) gives the number of ways in which any 3 objects can be placed in any 4 boxes.

ix) There exists a self-complementary planar graph on 5 or more vertices.

x) The number of partitions of 6 is 10.

2. a) Draw the logic circuit for the Boolean expression

b) Express the following statements in symbolic form.

i) There is a man in the park with blue eyes.

ii) Every blue-eyed man in the park is wearing a red hat.

iii) If a man wears no hat, then he has black eyes.

c) Using generating functions find 

3. a) There are about 77 crore ways to arrange the letters of the word “COMBINATORICS”. Count the exact number of such ways.

(2) b) Solve the recurrence relation:

c) List all the onto mappings from the set {a,b,c,d} to {1,2,3,4}. How many onto mappings are there form {a,b,c,d} to {1,2,3,4,5}?

d) For any statements p,q and r, prove that

4. a) Draw three nonisomorphic induced subgraphs of the following graph, each having the same number of vertices. Justify your choice.

b) Is the complement of the Peterson graph planar? Justify your answer.

c) What do you understand by a subdivision of a graph? Is every subdivision of a Hamiltonian graph Hamiltonian? Justify.

5. a) In the June, 2021 Term-End Examination of MTE-13, it was asked to give a direct and an indirect proof of the following statement.

"If a,b ∈ Z such that a is even and a+b is even, then b is even."

One student gave an indirect proof as follows:

"Let b be m+1, which is an odd number. We already know a and a+b are even. If we substitute b=m+1 in a + b, it becomes a+m+1, which is an odd number. This contradicts the given statement. Hence b is an even number."

What is wrong with the above proof? Also give a correct direct and an indirect proof.

b) write down and count all the partitions of the number 7. To verify your answer use the generating function for P, taking n =7 in Theorem 5 (of Unit 5, Block2).

6. a) Express x⁵ in terms of falling factorials and hence evaluate for m = 0,1,2,3,4,5.

b) Find a recurrence relation for a_n, the number of ways to arrange cars in a row with n spaces if we can use Maruti 800, Tata Safari or Scorpio. A Tata Safari or Scorpio requires two spaces, whereas a Maruti 800 requires just one space. Assume that you have unlimited number of each type of car and we do not distinguish between 2 cars of the same type.

c) If K_m,n for m, n ≥ 2 is Hamiltonian, how are m and n related? Justify your answer.

d) Show that if 7 colours are used to paint 50 bicycles and each bicycle is coloured with a single colour, at least 8 bicycles will have the same colour.

7. a) A box contains 6 red and 4 green balls. Four balls are selected from the box at random. What is the probability that two of the selected balls will be red and two will be green?

b) Define vertex connectivity and cut vertex set of any graph G. Find the vertex connectivity and cut vertex set for the following graph:

c) How many numbers from 0 to 759 are not divisible by either 3 or 7?

8. a) Solve the recurrence relation:

using generating function technique. Also find a₅ using your answer.

b) Is there a 4-regular graph on 7 vertices? Justify your answer.

c) Find the Boolean expression in the DNF form for the function defined in tabular form below:

MTE 13 2025 - Hindi

सावीय कार्य

पाठयक्रम कोड: MTE-13

सत्रीय कार्य कोड: MTE-13/TMA/2025

अधिकतम अंकः 100

1. जाँच कीजिए कि निम्नजिक्षित कथन सत्य है या असमय। अपने अतों की पुष्टि एक लघु उपपरित या प्रतिउदाहरण देकर कीजिए।

i) यदि किसी कथा का प्रतिस्थितकस्य है, तो वह कथन स्वयं भी साय होगा।

ii)  एक रैखिक समधात पुनरावृणित संबंध है।

iii) पुनरावृतिसंबंध के एक विशेष हारका रूप है।

iv) चरी x₁,x₂ और x₃ में एक ऐसा बूलीय व्यंजक है जिसका CNF

 है।

v) यदि एक पासे को तीन बार कैका जाता है तो प्रत्येक बार प्राप्त होने की प्रायिकता  है।

vi) प्रत्येक विषम चक्र की वर्णिक संख्या और कोर वर्णिक संख्यामा होती है।

vii) प्रत्येक ऑयलरीय ग्राफ हैमिल्टोनीय है।

viii)  उन तरीकों की संख्या को दर्शाता है जिनमें किन्हीं 3 वस्तुओं को 4 संदूकों में रखा जाना है।

ix) 5 या अधिक शीर्षों पर एक स्वपूरक समतलीय याक का अभिनव है।

x) 6 के विभाजनों की संख्या 10 है।

2. क) सूरीय व्यंजक  कार्क परिपथ बनाइए।

ख) निम्नलिखित कराको प्रकरूप में लिखिए।

i) बगीचे में एक नीली आँख वाला आदमी है।

ii) बगीचे में नीली आँखों वाले प्रायेक आद‌मी ने एक लाल टोपी पहनी हुई है।

iii)यदि किसी आद‌मी ने कोई भी टोपी नहीं पहनी है, तो उसकी आँकाली है।

ग) जनक फलों के प्रयोग से जातकीजिए।

3. साद "COMBINSTORICS" के अको व्यवस्थित करने के ग 77 करोड़ तरीके हैं। इन मरीकी की ठीक-ठीक संख्या जात कीजिए।

ख) पुनरावृ‌त्ति संबंध

को हम कीजिए।

ग) समुच्चय  से (1,2,3,4) पर सभी आच्छादक फसनी की सूची बनाइए। समुच्चय से (1,2,3,4,5) पर किन आउाद‌क फलन हैं?

घ) किन्हीं कथनी  p,q और r के लिए, सिद्ध कीजिए।

4.क) नीचे दिए ग्राफ के तीन अतुल्यकारी प्रेरित उपया बाहर, जिनमें प्रत्येक के शीर्षों की संख्या समान हो। अपने चयन की पुष्टि कीजिए।

ख) क्या पिटर्सन साफ का पूरक समीय है? अपने उत्तर की पुष्टि कीजिए।

ग) एक ग्राफ के उपविभाजन से आप क्या समोर का एक हैमिल्टनी की उपविभाजन हैमिल्टीनीया होता है? पुष्टि कीजिए।

5.क) MTE-13 की जून, 2021 संयंत्र परीक्षा में निम्नलिखित कथन की एक फायक्ष और एक परीक्षा उपपन्ति देने के लिए कहा गया था।

यदि इस प्रकार है कि सम है और  भी सम है, तो b एक सम संख्या होगी

एक छात्र ने परीक्ष उपपति इस प्रकार दी।

"मान लीजिए b बराबरm+1 है, जोकि एक विषम संख्या है। हम पहले से ही जानते हैं कि a और  सम संख्याएँ हैं। यदि हम  में b =m+1 रख दें तो यह a + m + 1 हो जाती है, जो कि विषम संख्या है। इससे दिए गए कथन का विरोध उत्पन होता है। इसलिए, ब एक सम संख्या है।"

उपरोक्त उपपन्ति में क्या गलत है? साथ ही, एक सही प्रत्यक्ष एवं एक परोक्ष उपपन्ति दीजिए।

ख) संख्या 7 के सभी विभाजन को लिखिए और उनकी गणना कीजिए। अपनी उत्तर की जाँच के लिए खंड 2 की इकाई 5 के प्रमेया 5 में  लेकर p_n जनक नाका प्रयोग कीजिए। 

6. क) x⁵को पतली कमणिली के रूप में लिखिए और इस प्रकार  के लिए  का मान

ख) यदि हमें केवल मारुति 800, टाटा सफारी या स्कोर्पियो को ही व्यवस्थित करना है तो इन माडलों की कारों को ॥ स्थानों वाली एक पंक्ति में व्यवस्थित करने के तरीकों की संख्या व, के लिए एक पुनरावृत्ति संबंध ज्ञात कीजिए। एक टाटा सफारी या स्कोर्पियो को दो स्थानों की जरूरत होती है जबकि एक मारुति 800 को केवल एक स्थान की जरूरत होती है। मान कर चलिए कि आपके पास प्रत्येक माडल की अनगिनत कारें हैं, और हम एक ही माडल की दो कारों में फर्क नहीं करते हैं।

ग) यदि  के लिए Km,n हैमिल्टोनी है पुष्टि कीजिए। और किस प्रकार संबंधित हैं? अपने उत्तर की 

घ) यदि 50 साइकिली की रंगने के लिए रंग का प्रयोग किया गया है और प्रत्येक साइकिल को एक ही रंग से रंगा गया है, जो दिखाइए कि कम से कम साइकिलों को एक ही रंग से रंगा गया है।

7. क) एक संदूक में 6 साल और 4 ही गई हैं। क्या प्रायिकता है कि संदूक से याद‌छया चुनी हुई चार गौदों में से दो गर्दै जाम और दोहरी हैं?

ख) किसी ग्राफ G के लिए शीर्ष-संबद्वतांक और काट शीर्ष समुच्चय परिभाषित कीजिए। नीचे दिए गए ग्राफ

के लिए शीर्ष - संबद्वतांक और काट शीर्ष समुच्चय ज्ञात कीजिए।

ग) 0 से 759 तक की संख्या में से किसी संसाली या से विभाजन नहीं है? 

क) पुनरावृ‌नित संबंध

की जनक फना विधि से हम कीजिए। साथ ही अपनी उन्तार से जात कीजिए।

ख) क्या 7 सीधी पर कोई 4-नियमित साफ है अपने उत्तम की पुष्टि कीजिए। 

ग) नीचे दी हुई तालिका में परिभाषित करन के लिए खूनीयाव्यांजक ज्ञात कीजिए।

Q: How will I receive the PDF?
A: Immediately after payment, the download link will appear.

Q: Is this hand-written or typed?
A: This is a professional typed computer PDF. You can use it as a reference for your handwritten submission.