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

Author

Tanya Khovanova and Konstantin Knop, Dec 16 2016

Keywords

• nonn
• easy

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.

Examples

			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.
		

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).

Crossrefs

Cf. A279673, A279682, A279684, A279685.

Programs

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

Mathematica

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

PARI

Vec((1 + x) / (1 - 2*x + x^2 - 4*x^3) + O(x^40)) \\ Colin Barker, Dec 17 2016

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