Problem 3 [20 pts (7,13): Interleave Preserving Relative Order A. Given the sequ

Question

Problem 3 [20 pts (7,13): Interleave Preserving Relative Order A. Given the sequence (a,b,c,d,e,fg), in how many ways can be organized into 5 bins on line such that the literals remain in the same order? Example valid arrangements are (ab) () (cde) (f) (g) () (a) (bc) (d) (efg) (a) (bc) (defg) ) O B. Two sorted sequences lengths 9 and 7 are given: (1,2,3,...9) and (a,b,c,d,e,f,g). We want to interleave them into a sequence of length 16 such that numbers 1-9 remain in relative order, and also literals a-g remain in relative order. How many ways are there to do this? Example valid sequences are la2bc34d56efg789 12345abc678de9fg albcdef23456789g

Explanation / Answer

A)here let alphabets are lying and to seperate them in 5 parts; 4 partition is required,

hence total elements 7 alphabets+4 partitions =11 has to be divided into two groups of 7 and 4

hence number of ways =13!/(9!*4!) =330

B) for both group has the same sequence ; it can be treated as problem of arranging m whilte and n black balls

for which there are (m+n)!/(m!*n!) ways

hence total number of ways =16!/(9!*7!) =11440

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.