Discrete math question (pigeon hole principal): 4(20 points] Three pigeons each

Question

Discrete math question (pigeon hole principal):

4(20 points] Three pigeons each fly into one of ten pigeonholes. Determine how many possible pigeon configurations there are in each situation (a) - (d); explain your reasoning (a) The pigeons are distinguishable, and pigeons may share a hole (b) The pigeons are distinguishable, and may not share a hole: (e) The pigeons are indistinguishable, and may not share a hole d) The pigeons are indistinguishable, and may share a. (e) Since there are since there are ten pigeonholes, what is the minimum number of pigeons needed to guarantee that at least two pigeons share a pigeonhole, and why?

Explanation / Answer

a)

10 holes and 3 distinguishable pigeons and they can share holes, means multiple pigeons can be together in a single hole.

One Hole can hoist multiple Pigeons.

The number of different configurations:

Each pigeon has a chance to fly into each hole(i.e, 10 holes) and there are 3! ways of orderly flyings possible into holes.

means 10 x 10 x 10 x 6 = 6000

Among these 6000 different configurations, some of them need to be eliminated. Because some order of flys will result the same configurations.

ex: P - Pigeon, H - Hole

Order of flyings - P1,P2,P3

P1 flies to H1, P2 flies to H2, P3 flies to H3 and other holes are free.

its arrangement will be like below

1 2 3 0 0 0 0 0 0 0

Order of flyings - P2,P1,P3

P2 flies to H2, P1 flies to H1 P3 flies to H3 and other holes are free.

its arrangement will be same as above

1 2 3 0 0 0 0 0 0 0

So, in both order of flyings, resulted arrangement will be same.

So, we need to eliminate these extra duplicate arrangements.

Let's understand when these duplicates will occur:

If all P's went to different H's, then for this arrangement all other 5 different ways of flies will led to duplicates.

So, let's count no. of arrangements in which all P's will fly to different H's.

Means each P has only one chance of hole to go into.

= 10 P 3 = 720

Number of duplicates = 5x(10 P 3) = 3600

Number of different arrangements after removing duplicates = 6000 - 5x(10 P 3) = 2400

b)

10 holes and 3 distinguishable pigeons and they cannot share holes, means multiple pigeons cannot be together in a single hole.

One Hole can hoist only one Pigeon.

Order of flies will not matter here. Because that does not create new arrangements in this case.

= 10 P 3 = 720

c)

10 holes and 3 indistinguishable pigeons and they cannot share holes, means multiple pigeons cannot be together in a single hole and we cannot distinguish order of flies also among these 3 pigeons.

= 10 C 3 = 120

d)

10 holes and 3 indistinguishable pigeons and they can share holes, means multiple pigeons can be together in a single hole and we cannot distinguish order of flies also among these 3 pigeons. Order of fly will not matter here.

Each P has 10 chances of holes to go into.

= 10 x 10 x 10 = 1000

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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