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.

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

Author

Tanya Khovanova and Konstantin Knop, Dec 16 2016

Keywords

• nonn

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.

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 - 4 - 8 = 15.
		

Links

• 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 (3, -1, 1, -2, -8).

Crossrefs

Cf. A279673, A279674, A279682, A279685.

Programs

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

Mathematica

LinearRecurrence[{3, -1, 1, -2, -8}, {1, 3, 5, 15, 37}, 30]

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