A080204 Number of fixed points under n-fold inflation for the substitution rule a->abc, b->ab, c->b that underlies the Kolakoski (3,1) sequence.

1, 3, 10, 23, 51, 114, 253, 559, 1234, 2723, 6007, 13250, 29225, 64459, 142170, 313567, 691595, 1525362, 3364293, 7420183, 16365730, 36095755, 79611695, 175589122, 387274001, 854159699, 1883908522, 4155091047, 9164341795, 20212592114, 44580275277, 98324892351, 216862376818

Offset: 1

Author

Michael Baake and Uwe Grimm, Mar 20 2003

Keywords

• easy
• nonn

Comments

See Baake-Sing (2002/2003) for the Kolakowski sequence.

a(n) is the number of possible tilings of a bracelet of "thickness" 1 and length n using single-color squares, single-color dominoes, and two-color k-ominoes with k >= 3. - Michael Tulskikh and Greg Dresden, Sep 03 2019; edited by Greg Dresden, Feb 18 2020, May 14 2020, May 18 2020

Links

• Metin Sariyar, Table of n, a(n) for n = 1..300
• J. E. Anderson and I. F. Putnam, Topological invariants for substitution tilings and their associated C*-algebras, Ergod. Theory and Dyn. Systems 18 (1998) 509-537. See also, Technical report DMS-720-IR, University of Victoria, 1995.
• Michael Baake and B. Sing, Kolakoski-(3,1) is a (deformed) model set, arXiv:math/0206098 [math.MG], 2002-2003.
• Greg Dresden and Michael Tulskikh, Tilings of 2 X n boards with dominos and L-shaped trominos, Washington & Lee University (2021).
• Index entries for linear recurrences with constant coefficients, signature (3,-2,1,-1).

Crossrefs

Equals one less than A332647.

Programs

Magma

I:=[1,3,10,23]; [n le 4 select I[n] else 3*Self(n-1)-2*Self(n-2)+Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Mar 12 2015

Mathematica

CoefficientList[Series[(1 + 3 x^2 - 2 x^3) / ((1 - x) (1 - 2 x - x^3)), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 12 2015 *)

Maxima

a(n):=(n*sum(sum(binomial(m,i)*binomial(n-2*i-1,m-1),i,0,(n-m)/2)/m,m,1,n)); /* Vladimir Kruchinin, Mar 10 2015 */

PARI

x='x+O('x^66); Vec(x*(1+3*x^2-2*x^3)/((1-x)*(1-2*x-x^3))) \\ Joerg Arndt, Jun 15 2013

Formula

Obtained from dynamical zeta function Z(x)=(1-x)/(1-2x-x^3), so that x Z'(x)/Z(x) is the ordinary power series generating function.

From Colin Barker, Jul 02 2012: (Start)

a(n) = 3*a(n-1) - 2*a(n-2) + a(n-3) - a(n-4).

G.f.: x*(1+3*x^2-2*x^3)/((1-x)*(1-2*x-x^3)). (End)

a(n) = n*Sum_{m=1..n} Sum_{i=0..(n-m)/2} binomial(m,i)*binomial(n-2*i-1,m-1)/m. - Vladimir Kruchinin, Mar 10 2015

a(n) = 2*a(n-1) + a(n-3) + 2. - Greg Dresden, Feb 08 2020

a(n) = w1^n + w2^n + w3^n - 1, for w1, w2, w3 roots of x^3-2x^2-1=0. - Greg Dresden, Feb 18 2020