Counting number of words of length $n$ [closed]

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

1

I am considering this graph and semi-infinite walks on it. By $W_n$ denote the set of words of length $n$. I am trying to find out how many words of length $n$ there are, i.e. to find the cardinality of $W_n$.

For example, ABCD is a word of length $4$.

This seems to be rather tricky, at least I did not find an answer for general $ninmathbbN$.

combinatorics graph-theory symbolic-computation

share|cite|improve this question

asked Jul 21 at 21:41

Rhjg

253214

closed as off-topic by amWhy, Taroccoesbrocco, Jose Arnaldo Bebita Dris, Xander Henderson, Mostafa Ayaz Jul 22 at 14:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Taroccoesbrocco, Jose Arnaldo Bebita Dris, Xander Henderson, Mostafa Ayaz

If this question can be reworded to fit the rules in the help center, please edit the question.

add a comment | 

up vote
1
down vote

favorite

1

I am considering this graph and semi-infinite walks on it. By $W_n$ denote the set of words of length $n$. I am trying to find out how many words of length $n$ there are, i.e. to find the cardinality of $W_n$.

For example, ABCD is a word of length $4$.

This seems to be rather tricky, at least I did not find an answer for general $ninmathbbN$.

combinatorics graph-theory symbolic-computation

share|cite|improve this question

asked Jul 21 at 21:41

Rhjg

253214

closed as off-topic by amWhy, Taroccoesbrocco, Jose Arnaldo Bebita Dris, Xander Henderson, Mostafa Ayaz Jul 22 at 14:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Taroccoesbrocco, Jose Arnaldo Bebita Dris, Xander Henderson, Mostafa Ayaz

If this question can be reworded to fit the rules in the help center, please edit the question.

add a comment | 

up vote
1
down vote

favorite

1

up vote
1
down vote

favorite

1

1

I am considering this graph and semi-infinite walks on it. By $W_n$ denote the set of words of length $n$. I am trying to find out how many words of length $n$ there are, i.e. to find the cardinality of $W_n$.

For example, ABCD is a word of length $4$.

This seems to be rather tricky, at least I did not find an answer for general $ninmathbbN$.

combinatorics graph-theory symbolic-computation

share|cite|improve this question

asked Jul 21 at 21:41

Rhjg

253214

I am considering this graph and semi-infinite walks on it. By $W_n$ denote the set of words of length $n$. I am trying to find out how many words of length $n$ there are, i.e. to find the cardinality of $W_n$.

For example, ABCD is a word of length $4$.

This seems to be rather tricky, at least I did not find an answer for general $ninmathbbN$.

combinatorics graph-theory symbolic-computation

share|cite|improve this question

asked Jul 21 at 21:41

Rhjg

253214

share|cite|improve this question

share|cite|improve this question

asked Jul 21 at 21:41

Rhjg

253214

asked Jul 21 at 21:41

Rhjg

253214

asked Jul 21 at 21:41

Rhjg

253214

253214

closed as off-topic by amWhy, Taroccoesbrocco, Jose Arnaldo Bebita Dris, Xander Henderson, Mostafa Ayaz Jul 22 at 14:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Taroccoesbrocco, Jose Arnaldo Bebita Dris, Xander Henderson, Mostafa Ayaz

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by amWhy, Taroccoesbrocco, Jose Arnaldo Bebita Dris, Xander Henderson, Mostafa Ayaz Jul 22 at 14:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Taroccoesbrocco, Jose Arnaldo Bebita Dris, Xander Henderson, Mostafa Ayaz

If this question can be reworded to fit the rules in the help center, please edit the question.

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
4
down vote

Let $A(n)$ be the number of words of length $n$ ending in $A$ and similarly for all the other letters. You can write a set of coupled recurrences like $E(n)=K(n-1)+D(n-1)$, one for each letter. You can encode this in a spreadsheet with $n$ in rows, the letters in columns, and the recurrence relations in the intersections. $A(1)=1$ and the same for all the letters. Write the recurrence into row $2$ and copy down.

Alternately you can think of a column vector with $A(n), B(n), ldots N(n)$ as entries and a matrix you multiply on the left to increase $n$ to $n+1$. If you can diagonalize the matrix you can find a closed form in terms of powers of the diagonal entries.

share|cite|improve this answer

answered Jul 21 at 21:52

Ross Millikan

276k21186352

• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I want, for example, know how many words of length 10 there are, then for example $$A(10)=G(9)=F(8)=D(7)+K(7)=C(6)+J(6)=B(5)+I(5)=A(4)+H(4)=G(3)+A(3)=F(2)+G(2)=E(1)+F(1)=2$$? And now I have to do the same for all the other letters. Thats cool but very much work. Maybe I should try the second approach. But I do not understand what you mean.
  – Rhjg
  Jul 21 at 22:08
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please explain your second approach a bit more? I do not understand what you mean. A closed form would be great.
  – Rhjg
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  They are really two ways of doing the same calculation. It is a complicated diagram so it will be a lot of work. The spreadsheet approach means you just need to write the equations once because you just reference the line above. Copy down takes care of the rest. It won't get a symbolic answer, but will give you the numeric answer without too much work.
  – Ross Millikan
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I dont understand what you mean with spreadsheet and copy down. I wrote down $A(n)=G(n-1), B(n)=A(n-1),...$ for all all letters
  – Rhjg
  Jul 21 at 22:16
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The matrix approach is the same equations. The fifth row would have the computation for $E(n+1)$. It would have $1$s in the fourth and eleventh columns representing the $E(n+1)=D(n)+K(n)$ equation. It will be a $14 times 14$ matrix with mostly zeros and a $1$ for each arrow in the diagram. Each time you multiply the vector by it you get one more step. Many matrices $M$ can be written as $M=P^-1DP$ where $D$ is diagonal. Then you have $M^k=P^-1D^kP$ and finding the power of a diagonal matrix is easy.
  – Ross Millikan
  Jul 21 at 22:18
  

  
  
  
  

 | 
show 3 more comments

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
4
down vote

Let $A(n)$ be the number of words of length $n$ ending in $A$ and similarly for all the other letters. You can write a set of coupled recurrences like $E(n)=K(n-1)+D(n-1)$, one for each letter. You can encode this in a spreadsheet with $n$ in rows, the letters in columns, and the recurrence relations in the intersections. $A(1)=1$ and the same for all the letters. Write the recurrence into row $2$ and copy down.

Alternately you can think of a column vector with $A(n), B(n), ldots N(n)$ as entries and a matrix you multiply on the left to increase $n$ to $n+1$. If you can diagonalize the matrix you can find a closed form in terms of powers of the diagonal entries.

share|cite|improve this answer

answered Jul 21 at 21:52

Ross Millikan

276k21186352

• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I want, for example, know how many words of length 10 there are, then for example $$A(10)=G(9)=F(8)=D(7)+K(7)=C(6)+J(6)=B(5)+I(5)=A(4)+H(4)=G(3)+A(3)=F(2)+G(2)=E(1)+F(1)=2$$? And now I have to do the same for all the other letters. Thats cool but very much work. Maybe I should try the second approach. But I do not understand what you mean.
  – Rhjg
  Jul 21 at 22:08
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please explain your second approach a bit more? I do not understand what you mean. A closed form would be great.
  – Rhjg
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  They are really two ways of doing the same calculation. It is a complicated diagram so it will be a lot of work. The spreadsheet approach means you just need to write the equations once because you just reference the line above. Copy down takes care of the rest. It won't get a symbolic answer, but will give you the numeric answer without too much work.
  – Ross Millikan
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I dont understand what you mean with spreadsheet and copy down. I wrote down $A(n)=G(n-1), B(n)=A(n-1),...$ for all all letters
  – Rhjg
  Jul 21 at 22:16
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The matrix approach is the same equations. The fifth row would have the computation for $E(n+1)$. It would have $1$s in the fourth and eleventh columns representing the $E(n+1)=D(n)+K(n)$ equation. It will be a $14 times 14$ matrix with mostly zeros and a $1$ for each arrow in the diagram. Each time you multiply the vector by it you get one more step. Many matrices $M$ can be written as $M=P^-1DP$ where $D$ is diagonal. Then you have $M^k=P^-1D^kP$ and finding the power of a diagonal matrix is easy.
  – Ross Millikan
  Jul 21 at 22:18
  

  
  
  
  

 | 
show 3 more comments

up vote
4
down vote

Let $A(n)$ be the number of words of length $n$ ending in $A$ and similarly for all the other letters. You can write a set of coupled recurrences like $E(n)=K(n-1)+D(n-1)$, one for each letter. You can encode this in a spreadsheet with $n$ in rows, the letters in columns, and the recurrence relations in the intersections. $A(1)=1$ and the same for all the letters. Write the recurrence into row $2$ and copy down.

Alternately you can think of a column vector with $A(n), B(n), ldots N(n)$ as entries and a matrix you multiply on the left to increase $n$ to $n+1$. If you can diagonalize the matrix you can find a closed form in terms of powers of the diagonal entries.

share|cite|improve this answer

answered Jul 21 at 21:52

Ross Millikan

276k21186352

• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I want, for example, know how many words of length 10 there are, then for example $$A(10)=G(9)=F(8)=D(7)+K(7)=C(6)+J(6)=B(5)+I(5)=A(4)+H(4)=G(3)+A(3)=F(2)+G(2)=E(1)+F(1)=2$$? And now I have to do the same for all the other letters. Thats cool but very much work. Maybe I should try the second approach. But I do not understand what you mean.
  – Rhjg
  Jul 21 at 22:08
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please explain your second approach a bit more? I do not understand what you mean. A closed form would be great.
  – Rhjg
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  They are really two ways of doing the same calculation. It is a complicated diagram so it will be a lot of work. The spreadsheet approach means you just need to write the equations once because you just reference the line above. Copy down takes care of the rest. It won't get a symbolic answer, but will give you the numeric answer without too much work.
  – Ross Millikan
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I dont understand what you mean with spreadsheet and copy down. I wrote down $A(n)=G(n-1), B(n)=A(n-1),...$ for all all letters
  – Rhjg
  Jul 21 at 22:16
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The matrix approach is the same equations. The fifth row would have the computation for $E(n+1)$. It would have $1$s in the fourth and eleventh columns representing the $E(n+1)=D(n)+K(n)$ equation. It will be a $14 times 14$ matrix with mostly zeros and a $1$ for each arrow in the diagram. Each time you multiply the vector by it you get one more step. Many matrices $M$ can be written as $M=P^-1DP$ where $D$ is diagonal. Then you have $M^k=P^-1D^kP$ and finding the power of a diagonal matrix is easy.
  – Ross Millikan
  Jul 21 at 22:18
  

  
  
  
  

 | 
show 3 more comments

up vote
4
down vote

up vote
4
down vote

Let $A(n)$ be the number of words of length $n$ ending in $A$ and similarly for all the other letters. You can write a set of coupled recurrences like $E(n)=K(n-1)+D(n-1)$, one for each letter. You can encode this in a spreadsheet with $n$ in rows, the letters in columns, and the recurrence relations in the intersections. $A(1)=1$ and the same for all the letters. Write the recurrence into row $2$ and copy down.

Alternately you can think of a column vector with $A(n), B(n), ldots N(n)$ as entries and a matrix you multiply on the left to increase $n$ to $n+1$. If you can diagonalize the matrix you can find a closed form in terms of powers of the diagonal entries.

share|cite|improve this answer

answered Jul 21 at 21:52

Ross Millikan

276k21186352

Let $A(n)$ be the number of words of length $n$ ending in $A$ and similarly for all the other letters. You can write a set of coupled recurrences like $E(n)=K(n-1)+D(n-1)$, one for each letter. You can encode this in a spreadsheet with $n$ in rows, the letters in columns, and the recurrence relations in the intersections. $A(1)=1$ and the same for all the letters. Write the recurrence into row $2$ and copy down.

Alternately you can think of a column vector with $A(n), B(n), ldots N(n)$ as entries and a matrix you multiply on the left to increase $n$ to $n+1$. If you can diagonalize the matrix you can find a closed form in terms of powers of the diagonal entries.

share|cite|improve this answer

answered Jul 21 at 21:52

Ross Millikan

276k21186352

share|cite|improve this answer

share|cite|improve this answer

answered Jul 21 at 21:52

Ross Millikan

276k21186352

answered Jul 21 at 21:52

Ross Millikan

276k21186352

answered Jul 21 at 21:52

Ross Millikan

276k21186352

276k21186352

• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I want, for example, know how many words of length 10 there are, then for example $$A(10)=G(9)=F(8)=D(7)+K(7)=C(6)+J(6)=B(5)+I(5)=A(4)+H(4)=G(3)+A(3)=F(2)+G(2)=E(1)+F(1)=2$$? And now I have to do the same for all the other letters. Thats cool but very much work. Maybe I should try the second approach. But I do not understand what you mean.
  – Rhjg
  Jul 21 at 22:08
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please explain your second approach a bit more? I do not understand what you mean. A closed form would be great.
  – Rhjg
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  They are really two ways of doing the same calculation. It is a complicated diagram so it will be a lot of work. The spreadsheet approach means you just need to write the equations once because you just reference the line above. Copy down takes care of the rest. It won't get a symbolic answer, but will give you the numeric answer without too much work.
  – Ross Millikan
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I dont understand what you mean with spreadsheet and copy down. I wrote down $A(n)=G(n-1), B(n)=A(n-1),...$ for all all letters
  – Rhjg
  Jul 21 at 22:16
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The matrix approach is the same equations. The fifth row would have the computation for $E(n+1)$. It would have $1$s in the fourth and eleventh columns representing the $E(n+1)=D(n)+K(n)$ equation. It will be a $14 times 14$ matrix with mostly zeros and a $1$ for each arrow in the diagram. Each time you multiply the vector by it you get one more step. Many matrices $M$ can be written as $M=P^-1DP$ where $D$ is diagonal. Then you have $M^k=P^-1D^kP$ and finding the power of a diagonal matrix is easy.
  – Ross Millikan
  Jul 21 at 22:18
  

  
  
  
  

 | 
show 3 more comments

• 
  
  
  

  
  

  
  
  
  
  
  

  
  If I want, for example, know how many words of length 10 there are, then for example $$A(10)=G(9)=F(8)=D(7)+K(7)=C(6)+J(6)=B(5)+I(5)=A(4)+H(4)=G(3)+A(3)=F(2)+G(2)=E(1)+F(1)=2$$? And now I have to do the same for all the other letters. Thats cool but very much work. Maybe I should try the second approach. But I do not understand what you mean.
  – Rhjg
  Jul 21 at 22:08
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please explain your second approach a bit more? I do not understand what you mean. A closed form would be great.
  – Rhjg
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  They are really two ways of doing the same calculation. It is a complicated diagram so it will be a lot of work. The spreadsheet approach means you just need to write the equations once because you just reference the line above. Copy down takes care of the rest. It won't get a symbolic answer, but will give you the numeric answer without too much work.
  – Ross Millikan
  Jul 21 at 22:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I dont understand what you mean with spreadsheet and copy down. I wrote down $A(n)=G(n-1), B(n)=A(n-1),...$ for all all letters
  – Rhjg
  Jul 21 at 22:16
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The matrix approach is the same equations. The fifth row would have the computation for $E(n+1)$. It would have $1$s in the fourth and eleventh columns representing the $E(n+1)=D(n)+K(n)$ equation. It will be a $14 times 14$ matrix with mostly zeros and a $1$ for each arrow in the diagram. Each time you multiply the vector by it you get one more step. Many matrices $M$ can be written as $M=P^-1DP$ where $D$ is diagonal. Then you have $M^k=P^-1D^kP$ and finding the power of a diagonal matrix is easy.
  – Ross Millikan
  Jul 21 at 22:18
  

  
  
  
  

If I want, for example, know how many words of length 10 there are, then for example $$A(10)=G(9)=F(8)=D(7)+K(7)=C(6)+J(6)=B(5)+I(5)=A(4)+H(4)=G(3)+A(3)=F(2)+G(2)=E(1)+F(1)=2$$? And now I have to do the same for all the other letters. Thats cool but very much work. Maybe I should try the second approach. But I do not understand what you mean.
– Rhjg
Jul 21 at 22:08

If I want, for example, know how many words of length 10 there are, then for example $$A(10)=G(9)=F(8)=D(7)+K(7)=C(6)+J(6)=B(5)+I(5)=A(4)+H(4)=G(3)+A(3)=F(2)+G(2)=E(1)+F(1)=2$$? And now I have to do the same for all the other letters. Thats cool but very much work. Maybe I should try the second approach. But I do not understand what you mean.
– Rhjg
Jul 21 at 22:08

Could you please explain your second approach a bit more? I do not understand what you mean. A closed form would be great.
– Rhjg
Jul 21 at 22:14

Could you please explain your second approach a bit more? I do not understand what you mean. A closed form would be great.
– Rhjg
Jul 21 at 22:14

They are really two ways of doing the same calculation. It is a complicated diagram so it will be a lot of work. The spreadsheet approach means you just need to write the equations once because you just reference the line above. Copy down takes care of the rest. It won't get a symbolic answer, but will give you the numeric answer without too much work.
– Ross Millikan
Jul 21 at 22:14

They are really two ways of doing the same calculation. It is a complicated diagram so it will be a lot of work. The spreadsheet approach means you just need to write the equations once because you just reference the line above. Copy down takes care of the rest. It won't get a symbolic answer, but will give you the numeric answer without too much work.
– Ross Millikan
Jul 21 at 22:14

I dont understand what you mean with spreadsheet and copy down. I wrote down $A(n)=G(n-1), B(n)=A(n-1),...$ for all all letters
– Rhjg
Jul 21 at 22:16

I dont understand what you mean with spreadsheet and copy down. I wrote down $A(n)=G(n-1), B(n)=A(n-1),...$ for all all letters
– Rhjg
Jul 21 at 22:16

The matrix approach is the same equations. The fifth row would have the computation for $E(n+1)$. It would have $1$s in the fourth and eleventh columns representing the $E(n+1)=D(n)+K(n)$ equation. It will be a $14 times 14$ matrix with mostly zeros and a $1$ for each arrow in the diagram. Each time you multiply the vector by it you get one more step. Many matrices $M$ can be written as $M=P^-1DP$ where $D$ is diagonal. Then you have $M^k=P^-1D^kP$ and finding the power of a diagonal matrix is easy.
– Ross Millikan
Jul 21 at 22:18

The matrix approach is the same equations. The fifth row would have the computation for $E(n+1)$. It would have $1$s in the fourth and eleventh columns representing the $E(n+1)=D(n)+K(n)$ equation. It will be a $14 times 14$ matrix with mostly zeros and a $1$ for each arrow in the diagram. Each time you multiply the vector by it you get one more step. Many matrices $M$ can be written as $M=P^-1DP$ where $D$ is diagonal. Then you have $M^k=P^-1D^kP$ and finding the power of a diagonal matrix is easy.
– Ross Millikan
Jul 21 at 22:18

 | 
show 3 more comments