Welcome to our community

Be a part of something great, join today!

Find a recursive formula for the number of combinations

CStudent

New member
Nov 16, 2018
15
I have some question integrating between combinatorics and recursive formulas.


Generally, I have some difficulty with the concept of recursion, as well as with the recursion in programming unfortunately.


I have some question to solve, and maybe you can guide me:


Find a recursive formula and a terminal condition for the number of words with the length 'n' that can be written by $A, B, C$, such that these combinations won't be shown: $AB, AC, BA, BC$.


Now, I know that if we start from $A$ or $B$ we of course have one option, 'n' $A's$, 'n' $B's$ - which are two combinations.


Now, if we start from $C$, I understand we have more 'n-1' letters to write such that we don't write the illegal ones.


I know that means we have $a_{n-1}$ combinations after $C$.
But that is what I don't understand, what is that $a_{n-1}$, how do we know it really contains only the legal combinations?


I wold love to get some sense of this concept.


Thanks.
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
I have some question integrating between combinatorics and recursive formulas.


Generally, I have some difficulty with the concept of recursion, as well as with the recursion in programming unfortunately.


I have some question to solve, and maybe you can guide me:


Find a recursive formula and a terminal condition for the number of words with the length 'n' that can be written by $A, B, C$, such that these combinations won't be shown: $AB, AC, BA, BC$.


Now, I know that if we start from $A$ or $B$ we of course have one option, 'n' $A's$, 'n' $B's$ - which are two combinations.


Now, if we start from $C$, I understand we have more 'n-1' letters to write such that we don't write the illegal ones.


I know that means we have $a_{n-1}$ combinations after $C$.
But that is what I don't understand, what is that $a_{n-1}$, how do we know it really contains only the legal combinations?


I wold love to get some sense of this concept.


Thanks.
If $a_n$ is the number of permissible words of length $n$, then you have shown that $a_n = 2 + a_{n-1}$. (In fact, there is only one word starting with A, one word starting with B, and $a_{n-1}$ words starting with C.) That is the recursive formula. To complete the definition, you need to add that $a_1 = 3$. I'm guessing that this is what the question means by a terminal condition, though I would call it the initial condition. It simply says that there are three words of length 1, namely A, B and C.
 

CStudent

New member
Nov 16, 2018
15
If $a_n$ is the number of permissible words of length $n$, then you have shown that $a_n = 2 + a_{n-1}$. (In fact, there is only one word starting with A, one word starting with B, and $a_{n-1}$ words starting with C.) That is the recursive formula. To complete the definition, you need to add that $a_1 = 3$. I'm guessing that this is what the question means by a terminal condition, though I would call it the initial condition. It simply says that there are three words of length 1, namely A, B and C.
Yes, but I have an obstacle in understanding the concept of the recursion...

Again, I don't understand how we can leap to $a_{n−1}$. Okay, after the first C, we have n-1 places, how does it tells us that has $a_{n−1}$? How do we know what is this $a_{n−1}$ at all?

Thank you.
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
Yes, but I have an obstacle in understanding the concept of the recursion...

Again, I don't understand how we can leap to $a_{n−1}$. Okay, after the first C, we have n-1 places, how does it tells us that has $a_{n−1}$? How do we know what is this $a_{n−1}$ at all?

Thank you.
If the first letter is a C then there is no restriction on what the next letter can be. In other words, it's exactly equivalent to starting again, but with only $n-1$ places instead of $n$.