A279673 The maximum number of coins that can be processed in n weighings where all coins are real except for one LHR-coin starting in the light state.

1, 3, 9, 19, 41, 99, 233, 531, 1225, 2851, 6601, 15251, 35305, 81763, 189225, 437907, 1013641, 2346275, 5430537, 12569363, 29093289, 67339363, 155862889, 360759571, 835013705, 1932719395, 4473463369, 10354262163, 23965938537, 55471468387, 128394046889

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.

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.

Examples

			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.
		

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. A279674, A279682, A279684, A279685.

Programs

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

Mathematica

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

PARI

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

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