By Richard Stanley


2019-01-09 03:33:24 8 Comments

Let $L_n$ be the length of the $n$th term of Conway's "look and say" sequence (https://oeis.org/A005341). The generating function $F(x)= \sum_{n\geq 0}L_nx^n$ is a rational function, say $P(x)/Q(x)$ in lowest terms, where $Q(0)=1$. The look and say sequence is built up from 92 "atoms" in a way that suggests $\deg Q(x)=92$. Actually, however, $\deg Q(x)=72$. Is there a theoretical reason for this?

For those who are interested, \begin{eqnarray*} P(x) & = & x+x^2-x^3-x^4-x^5-x^6-x^8+4x^9+6x^{10}-6x^{12}-8x^{13}\\ & & \ +x^{14}+5x^{15}+4x^{16}+x^{17}+4x^{18}+x^{19}-3x^{20}-6x^{21}-8x^{22}\\ & & \ -12x^{23}+6x^{24}+36x^{25}+20x^{26}+x^{27}-58x^{28}-34x^{29}+30x^{30}\\ & & \ +20x^{31}+23x^{32}-35x^{33}+9x^{34}+26x^{35}-8x^{36}-12x^{37}\\ & & \ -42x^{38}-7x^{39}+79x^{40}+13x^{41}-16x^{42}-14x^{43}-107x^{44}\\ & & \ +65x^{45}+33x^{46}+32x^{47}+39x^{48}-126x^{49}-38x^{50}+25x^{51}\\ & & \ +66x^{52}+64x^{53}-89x^{54}+8x^{55}-45x^{56}+15x^{57}+27x^{58}\\ & & -15x^{59}+44x^{60}+56x^{61}-54x^{62}-41x^{63}+11x^{64}+21x^{65}\\ & & \ +50x^{66}-62x^{67}+19x^{68}+4x^{69}+4x^{70}-15x^{71}-31x^{72}\\ & & \ +22x^{73}+20x^{74}-18x^{75}+18x^{76}-18x^{77}+18x^{78} -12x^{79}. \end{eqnarray*} and \begin{eqnarray*} Q(x) & = & (1-x)(1-x^2-2x^3-x^4+2x^5+2x^6+x^7-x^8-x^9-x^{10}-x^{11}\\ & & \ -x^{12} +2x^{13}+5x^{14}+3x^{15}-2x^{16}-10x^{17}-3x^{18}-2x^{19}\\ & & \ +6x^{20}+6x^{21}+x^{22}+9x^{23}-3x^{24}-7x^{25}-8x^{26}\\ & & \ -8x^{27}+10x^{28}+6x^{29}+8x^{30}-5x^{31}-12x^{32}+7x^{33}\\ & & \ -7x^{34}+7x^{35}+x^{36}-3x^{37}+10x^{38}+x^{39}-6x^{40}\\ & & \ -2x^{41}-10x^{42}-3x^{43}+2x^{44}+9x^{45}-3x^{46}+14x^{47}\\ & & \ -8x^{48}-7x^{50}+9x^{51}+3x^{52}-4x^{53}-10x^{54}-7x^{55}\\ & & \ +12x^{56}+7x^{57}+2x^{58}-12x^{59}-4x^{60}-2x^{61}+5x^{62}\\ & & \ +x^{64}-7x^{65}+7x^{66}-5x^{67}+12x^{68}-6x^{69}+3x^{70} -6x^{71}). \end{eqnarray*}

1 comments

@Guntram 2019-01-09 20:27:22

The characteristic polynomial of the transition matrix $A$ is given by $f(x) = x^{18}(x-1)^2(x+1) Q(x)$ with $Q$ as in the question, see the link given by Per Alexandersson.

With the notation in http://www.se16.info/js/lands2.htm, the relevant pieces recalled below, a computation for $A$ gives

  • $0$-eigenvector: $(2)-(4)-(73)+(75)$ (in particular the kernel is 1-dimensional)

  • $1$-eigenvectors: $(1); (2)+(3)-(73)-(74)$

  • $(-1)$-eigenvector: $(2)-(3)-(73)+(74)$.

Interpreting this computation as a theoretical explanation, one might say:

  • trivially, the block $(1)$ (given by $22$) is stable

  • the successor of $(2)+(75)$ equals the successor of $(4)+(73)$ (up to a permutation of the blocks).

  • the successor of $(2)+(3)$, S $+ (2)+(3)$ where S = $\text{Hf Pa H C}$, shares the same "prefix" S with the successor of $(73)+(74)$, S + $(73) + (74)$ (again, up to permutation of blocks)

  • the successor of $(2)+(74)$ is given by T $+ (3)+(73)$, where T = $\text{Hf Pa H Ca}$, while the successor of $(3)+(73)$ is given by T$+(2)+(74)$.

These facts then force the degree to be smaller than the degree of the blocks.

Presumably the generalized eigenvectors for 0 correspond to combinations of blocks whose successors eventually become equal.

\begin{array}{|c|c|c|c|} \hline \text{Number} & \text{Element} & \text{Evolution} \\ \hline 1 & \text{H} & \text{H} \\ \hline 2 & \text{He} & \text{Hf Pa H Ca Li} \\ \hline 3 & \text{Li} & \text{He} \\ \hline 4 & \text{Be} & \text{Ge Ca Li} \\ \hline 73 & \text{Ta} & \text{Hf Pa H Ca W} \\ \hline 74 & \text{W} & \text{Ta} \\ \hline 75 & \text{Re} & \text{Ge Ca W}\\ \hline \end{array}

Related Questions

Sponsored Content

1 Answered Questions

[SOLVED] Funny recurrence

1 Answered Questions

0 Answered Questions

0 Answered Questions

Nonlinear recurrence sequence systems of order one

1 Answered Questions

[SOLVED] Conway's subprime Fibonacci sequences

0 Answered Questions

What objects satisfy Eulerian-like recurrence?

  • 2012-08-27 21:02:21
  • Per Alexandersson
  • 159 View
  • 2 Score
  • 0 Answer
  • Tags:   co.combinatorics

5 Answered Questions

[SOLVED] Coin flipping and a recurrence relation

2 Answered Questions

[SOLVED] Counting sequences - a recurrence relation.

2 Answered Questions

[SOLVED] Inhomogenous recurrence relations

  • 2010-04-13 18:29:36
  • mechko
  • 180 View
  • 1 Score
  • 2 Answer
  • Tags:   co.combinatorics

Sponsored Content