login
A279684
The maximum number of coins that can be processed in n weighings that all are real except for one LHR-coin starting in the heavy or real state.
5
1, 3, 5, 15, 37, 87, 205, 495, 1173, 2759, 6493, 15263, 35749, 83575, 195181, 455247, 1060533, 2468391, 5740925, 13342975, 30993349, 71956951, 166991501, 387397551, 898427605, 2083016071, 4828379549, 11189823071, 25928070117, 60069313847, 139148806829
OFFSET
0,2
COMMENTS
An LHR-coin is a coin that can change its weight periodically from light to heavy to real to light.
Also the number of outcomes of n weighings that start with a balance and every even-numbered imbalance that is not the last one must be followed by a balance, or every odd-numbered imbalance that is not the last one must be followed by a balance.
LINKS
Tanya Khovanova and Konstantin Knop, Coins that Change Their Weights, arXiv:1611.09201 [math.CO], 2016.
FORMULA
a(n) = 3a(n-1) - a(n-2) + a(n-3) - 2a(n-4) - 8a(n-5).
G.f.: (1 - 3*x^2 + 2*x^3 - 4*x^4)/((1 + x)*(1 - 2*x)*(1 - 2*x + x^2 - 4*x^3)). - Ilya Gutkovskiy, Dec 17 2016
EXAMPLE
If we have two weighings we are not allowed to have outcomes that consist of two imbalances. That means a(2) = 9 - 4 = 5.
If we have three weighings we are not allowed the following outcomes: <<=, <<<, where any less-than sign can be interchanged with a greater-than sign. Thus a(3) = 27 - 4 - 8 = 15.
MATHEMATICA
LinearRecurrence[{3, -1, 1, -2, -8}, {1, 3, 5, 15, 37}, 30]
PROG
(Magma) I:=[1, 3, 5, 15, 37]; [n le 5 select I[n] else 3*Self(n-1)- Self(n-2)+Self(n-3)-2*Self(n-4)-8*Self(n-5): n in [1..40]]; // Vincenzo Librandi, Dec 16 2016
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved