# Find a recursive formula for the number of combinations

• MHB
• CStudent
In summary: That's why the number of permissible words starting with C is $a_{n-1}$. This follows directly from the definition of $a_n$.
CStudent
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.

CStudent said:
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.

Opalg said:
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.

CStudent said:
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$.

## What is a recursive formula for the number of combinations?

A recursive formula for the number of combinations is a mathematical expression that uses previous values to calculate the current value of the combination. It is a way to express the relationship between the number of objects and the number of possible combinations without having to list them all out.

## How is a recursive formula different from a regular formula for combinations?

A regular formula for combinations, also known as the "choose" formula, uses factorials and does not rely on previous values. A recursive formula, on the other hand, uses the previous values of the combination to calculate the current value. Recursive formulas can be more efficient and easier to use for larger numbers of objects.

## Can a recursive formula be used for any number of objects and combinations?

Yes, a recursive formula can be used for any number of objects and combinations. It is a general formula that can be applied to any situation where combinations are needed. However, for very large numbers, it may become computationally intensive and other methods may be more efficient.

## How do you find a recursive formula for the number of combinations?

To find a recursive formula for the number of combinations, you need to identify the pattern between the number of objects and the number of combinations. This can be done by listing out the combinations for smaller numbers of objects and looking for a relationship between them. Once the pattern is identified, it can be expressed as a recursive formula.

## What are the advantages of using a recursive formula for combinations?

There are several advantages of using a recursive formula for combinations. It can be more efficient and easier to use for larger numbers of objects. It also allows for a more compact and general way of expressing the relationship between objects and combinations. Additionally, recursive formulas can be used in programming and other applications where a step-by-step approach is needed.

Replies
2
Views
3K
Replies
16
Views
3K
Replies
11
Views
2K
Replies
3
Views
1K
Replies
18
Views
2K
Replies
14
Views
1K
Replies
1
Views
1K
Replies
6
Views
2K
Replies
12
Views
1K
Replies
1
Views
5K