A078039 revisited
Dion Gijswijt
gijswijt at science.uva.nl
Sun Mar 7 11:32:47 CET 2004
If b(n),c(n),d(n),e(n) are the numbers of zeros, ones, twos and threes
after n iterations, then:
[b(n),c(n),d(n),e(n)]=[1,0,0,0]A^n, there the matrix A equals:
A=[[1,1,1,0],[1,1,1,1],[1,1,0,0],[1,1,1,0]].
(the rows of A correspond to the replacements of 0,..,3 respectively.)
Of course a(n)=b(n)+c(n)+d(n)+e(n)=
[1,0,0,0]A^n [1,1,1,1]^T.
So the GF for a(n) equals:
sum_n=0^infty x^n [1,0,0,0]A^n [1,1,1,1]^T =
[1,0,0,0] sum_n=0^infty (xA)^n [1,1,1,1]^T =
[1,0,0,0] 1/(1-xA) [1,1,1,1]^T=
(1+x)/(-1+2x+3x^2+x^3).
Hope this is of use.
Dion Gijswijt.
> the repeated substitution
> 0 -> {0,1,2}
> 1 -> {0,1,2,3}
> 2 -> {0,1}
> 3 -> {0,1,2}
> starting on list {0}
> and flattening at each step
> { {sequence1}, {sequence2},..}
> to {sequence1,sequence2,..}
> generates a list after n steps
> with length =a(n)=A078039
>
> with GF= (1 - x)/(1 + x - 2*x^2 + x^3)
> or, unsigned : (1 + x)/(1 - x - 2*x^2 - x^3)
>
> Who sees the link between the substitutions
> and the GF?
>
>
> Wouter Meeussen
>
>
>
>
>
>
>
>
>
> ===============================
> This email is confidential and intended solely for the use of the
> individual to whom it is addressed. If you are not the intended
> recipient, be advised that you have received this email in error and
> that any use, dissemination, forwarding, printing, or copying of this
> email is strictly prohibited. You are explicitly requested to notify the
> sender of this email that the intended recipient was not reached.
More information about the SeqFan
mailing list