OFFSET
0,2
COMMENTS
An LHR-coin is a coin that can change its weight periodically from light to heavy to real to light.
If an LHR-coin starts in the real state, then the maximum number of coins that can be processed in n weighings is a(n-1).
Also the number of outcomes of n weighings such that every even-numbered imbalance that is not the last one must be followed by a balance.
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Tanya Khovanova and Konstantin Knop, Coins that Change Their Weights, arXiv:1611.09201 [math.CO], 2016.
Index entries for linear recurrences with constant coefficients, signature (2,-1,4).
FORMULA
a(n) = 2a(n-1) - a(n-2) + 4a(n-3).
G.f.: (1 + x + 4*x^2) / (1 - 2*x + x^2 - 4*x^3). - Colin Barker, Dec 17 2016
EXAMPLE
If we have three weighings we are not allowed to have outcomes that consist of three imbalances. That means a(3) = 27 - 8 = 19.
If we have four weighings we are not allowed the following outcomes: =<<<, <=<<, <<<=, <<<<, where any less-than sign can be interchanged with a greater-than sign. Thus a(4) = 81 - 3*8 - 16 = 41.
MATHEMATICA
LinearRecurrence[{2, -1, 4}, {1, 3, 9}, 30]
PROG
(Magma) I:=[1, 3, 9]; [n le 3 select I[n] else 2*Self(n-1)-Self(n-2)+4*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Dec 17 2016
(PARI) Vec((1 + x + 4*x^2) / (1 - 2*x + x^2 - 4*x^3) + O(x^40)) \\ Colin Barker, Dec 17 2016
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Tanya Khovanova and Konstantin Knop, Dec 16 2016
STATUS
approved