A279674 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 state.

1, 3, 5, 11, 29, 67, 149, 347, 813, 1875, 4325, 10027, 23229, 53731, 124341, 287867, 666317, 1542131, 3569413, 8261963, 19123037, 44261763, 102448341, 237127067, 548852845, 1270371987, 2940399397, 6805838187, 15752764925, 36461289251, 84393166325, 195336103099

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 such that every odd-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) = 2*a(n-1) - a(n-2) + 4*a(n-3).

G.f.: (1 + x) / (1 - 2*x + x^2 - 4*x^3). - Colin Barker, 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 - 2*4 - 8 = 11.

Mathematica

LinearRecurrence[{2, -1, 4}, {1, 3, 5}, 30]

Prog

(Magma) I:=[1, 3, 5]; [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) / (1 - 2*x + x^2 - 4*x^3) + O(x^40)) \\ Colin Barker, Dec 17 2016

Crossrefs

Cf. A279673, A279682, A279684, A279685.

Sequence in context: A328329 A326392 A213210 * A194563 A080443 A168607

Adjacent sequences: A279671 A279672 A279673 * A279675 A279676 A279677

Keyword

nonn,easy

Author

Tanya Khovanova and Konstantin Knop, Dec 16 2016

Status

approved