[Math] Number of ways of attending classes over N days

combinatoricsprobability

Problem Statement

In a university, your attendance determines whether you'll be allowed to attend your graduation ceremony. You are not allowed to miss classes for four or more consecutive days. You graduation ceremony is on the last day of the of the academic year, which is the Nth day.

Your task is to determine the following:

  1. The number of ways of attending classes over N days.
  2. The probability that you will miss your graduation ceremony.

Information I tried to decode from the problem statement:

  1. There would be two choices everyday for N number of days i.e. attend the class or not.

  2. But, because of the constraint, the allowed consecutive gaps are 0 days, 1 days, 2 days and 3 days.

  3. Let's try to find the invalid ways and subtract it from total number of possibilities.

  4. So, Total number of ways – Invalid possibilities i.e. 4. $$ 2^{n – 1} – ( 2^{n – 4} * (n – 3)) $$

  5. I also visited this answer but was not able to map it to my problem.

MY DOUBT

Actually, I am not able to figure out whether my solution is correct. My approach seems right to me but actually it is right or wrong I'm not able to figure out. Or is there any other way of solving this problem?

Any assistance will be helpful. Sorry If I missed something. Please do let me know what else I can add.

Thanks

Best Answer

There probably isn't a closed form, but you can write a recurrence as follows:

$f(n, k)$ = number of ways to attend classes in the first $n$ days such that you were absent the last $k$ days where $0 \leq k < 4$.

Then, the recurrence transition is as follows:

You attend class on day $n$, then: $f(n, 0) = f(n-1, 0)+f(n-1, 1)+f(n-1, 2)+f(n-1, 3)$.

You don't attend class on day $n$, then

  • $f(n, 1) = f(n-1, 0)$
  • $f(n, 2) = f(n-1, 1)$
  • $f(n, 3) = f(n-1, 2)$
Related Question