CODEWITHSUNDEEP
mathcombinationspermutation
Mrinal Kamboj
Mrinal Kamboj

Reputation: 11478

Solving the combination problem where a pattern is invalid (needs to be removed)

Problem is on N days, a student can be present or absent, but a student is not allowed to be absent for 3 or more consecutive days. Thus total number of combinations are - 2^N, where every day there are only 2 options, A - Absent or P - Present

Let's take N as 7, which means total combinations are - 2^7 = 128

Now Invalid patterns are , AAA, AAAA, AAAAA, AAAAAA, AAAAAAA so they need to be removed from total value and following is my understanding:

1. 3 Absent together:

    AAAP--- - 2^3 = 8
    ---PAAA - 2^3 = 8
    PAAAP-- - 2^2 = 4 * 3C1 (as there are such combinations) = 12
    Total - 28

2. 4 Absent together:
   AAAAP-- - 2^2 = 4
   --PAAAA - 2^2 = 4
   PAAAAP- - 2 *2 = 4
   Total - 12

3. 5 Absent together:
   AAAAAAP- - 2
   -PAAAAAA - 2
   PAAAAAP - 1
   Total - 5

4. 6 Absent together:
   AAAAAAP
   PAAAAAA
   Total - 2

5. 7 Absent together:
   AAAAAAA
   Total - 1

Total Invalid - 28 + 12 + 5 + 2 + 1 = 48

Total Valid Combinations - 128 - 48 = 80

Please let me know have I deduced it correctly, or there's something incorrect with my understanding

Upvotes: 0

Views: 73

Answers (1)

MBo
MBo

Reputation: 80287

Let's make recurrent equations. Valid combination of length k might end with 0, 1, or 2 "A"'s - denote numbers of such variants v0, v1 and v2.

We can make valid combination of length k+1 with zero-ending "A"'s if we add "P" to any valid combination of length k

v0(k+1) = v0(k) + v1(k) + v2(k)

We can make valid combination of length k+1 with one ending "A" if we add "A" to any zero-ending combination of length k

v1(k+1) = v0(k)

We can make valid combination of length k+1 with two ending "A"'s if we add "A" to any one-ending combination of length k

v2(k+1) = v1(k)

Now look at Python code (Ideone example)

v0 = 1
v1 = 0
v2 = 0
for i in range(10):
    v0, v1, v2 = v0 + v1 + v2, v0, v1
    print(i, v0)

Result is

0 1
1 2
2 4
3 7
4 13
5 24
6 44
7 81   
8 149
9 274

Note you have mistake v(7) = 81, not 80

and this is tribonacci sequence with more simple recurrence expression:

 a(n) = a(n-1) + a(n-2) + a(n-3)

Upvotes: 1

Related Questions