We throw a die a number of times. We let Y k be the number of different faces that came up after k throws. Now we want P [ Y k ≤ 5 ].According to the answer sheet, we use the principle of inclusion-exclusion here to arrive at the following answer: P ( Y k ≤ 5 ) = ( 6 5 ) ( 5 6 ) k − ( 6 4 ) ( 4 6 ) k + ( 6 3 ) ( 3 6 ) k − ( 6 2 ) ( 2 6 ) k + ( 6 1 ) ( 1 6 ) k − ( 6 0 ) ( 0 6 ) k (which I believe to be equal to) P ( Y k ≤ 5 ) = P ( Y k = 5 ) − P ( Y k = 4 ) + P ( Y k = 3 ) − P ( Y k = 2 ) + P ( Y k = 1 ) − P ( Y k = 0 )But I just can't wrap my head around how the principle of inclusion-exclusion was exactly used here. My first thought was that it has something to do with the fact that if we see 5 faces, we've also seen at least 4 faces, etc. so that [ Y k ≤ 4 ] is a subset of [ Y k ≤ 5 ]. I've tried to manually calculate (using the principle of inclusion-exclusion) P ( Y k = 1 ∪ Y k = 2 ∪ Y k = 3 ∪ Y k = 4 ∪ Y k = 5 ) but I don't arrive at the same answer. So far I haven't come to a good intuitive understanding yet, it would be great if someone could help me grasp this.

Question

We throw a die a number of times. We let       Y    k   be the number of different faces that came up after   k throws. Now we want   P  [      Y    k    ≤  5  ].According to the answer sheet, we use the principle of inclusion-exclusion here to arrive at the following answer:  P  (      Y    k    ≤  5  )  =                    (                    6      5                      )              (      5    6        )    k    −                    (                    6      4                      )              (      4    6        )    k    +                    (                    6      3                      )              (      3    6        )    k    −                    (                    6      2                      )              (      2    6        )    k    +                    (                    6      1                      )              (      1    6        )    k    −                    (                    6      0                      )              (      0    6        )    k   (which I believe to be equal to)   P  (      Y    k    ≤  5  )  =  P  (      Y    k    =  5  )  −  P  (      Y    k    =  4  )  +  P  (      Y    k    =  3  )  −  P  (      Y    k    =  2  )  +  P  (      Y    k    =  1  )  −  P  (      Y    k    =  0  )But I just can&#039;t wrap my head around how the principle of inclusion-exclusion was exactly used here. My first thought was that it has something to do with the fact that if we see 5 faces, we&#039;ve also seen at least 4 faces, etc. so that   [      Y    k    ≤  4  ] is a subset of   [      Y    k    ≤  5  ]. I&#039;ve tried to manually calculate (using the principle of inclusion-exclusion)   P  (      Y    k    =  1  ∪      Y    k    =  2  ∪      Y    k    =  3  ∪      Y    k    =  4  ∪      Y    k    =  5  ) but I don&#039;t arrive at the same answer. So far I haven&#039;t come to a good intuitive understanding yet, it would be great if someone could help me grasp this.

Leslie Rollins · Accepted Answer

Let       E    i   be the event that face number   i does not appear, for each   i  =  1  ,  2  ,  …  ,  6. Then event   {      Y    k    ≤  5  } is the same as the event that at least one       E    i   occurs, i.e. that at least one face is missing. Therefore, using the principle of inclusion exclusion, and the symmetry of the problem,                    P        (                  Y          k                ≤        5        )                            =        P                  (                      ⋃                          i              =              1                        6                                E            i                    )                                                  =                  ∑                      r            =            1                    6                (        −        1                  )                      r            +            1                                                              (                                            6            r                                              )                                      P        (                  E          1                ∩                  E          2                ∩        ⋯        ∩                  E          r                )                                          =                  ∑                      r            =            1                    6                (        −        1                  )                      r            +            1                                                              (                                            6            r                                              )                                                            (                                          6                −                r                            6                        )                    k                .            This is where the equality you were given comes from.

Janessa Olson · Accepted Answer

No, you are misinterpreting. The equation you have is                    (1)                              P                (        |        F        |        ≤        5        )        =                  ∑                      |            A            |            =            5                                    P                (        F        ⊆        A        )        −                  ∑                      |            A            |            =            4                                    P                (        F        ⊆        A        )        +                  ∑                      |            A            |            =            3                                    P                (        F        ⊆        A        )        −                  ∑                      |            A            |            =            2                                    P                (        F        ⊆        A        )        +                  ∑                      |            A            |            =            1                                    P                (        F        ⊆        A        )        −                  ∑                      |            A            |            =            0                                    P                (        F        ⊆        A        )            where   F is the set of faces that show up, and   A  ⊆  {  1  ,  2  ,  3  ,  4  ,  5  ,  6  } is a subset of faces in each sum.Expanding a little more, we have 6 events &quot;only 1,2,3,4,5 are allowed&quot;, &quot;only 1,2,3,4,6 are allowed&quot;, ..., &quot;only 2,3,4,5,6 are allowed&quot;, or equivalently, the six events are &quot;1 does not show up&quot;, &quot;2 does not show up&quot;, ..., &quot;6 does not show up&quot;.   |  F  |  ≤  5 is the union of these events, and intersecting   k of these events is precisely reducing the allowable faces to 6-  k. So inclusion-exclusion gives      P    (  |  F  |  ≤  5  )  =      ∑          possible       1      -intersection            P    (  e  v  e  n  t  )  −      ∑          possible       2      -intersection            P    (  e  v  e  n  t  )  +  …which is equation (1).