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,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

Table of n, a(n) for n=0..30.

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

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

Cf. A279673, A279674, A279682, A279685.

Sequence in context: A148502 A295614 A089485 * A146212 A265762 A018516

Adjacent sequences: A279681 A279682 A279683 * A279685 A279686 A279687

Keyword

nonn

Author

Tanya Khovanova and Konstantin Knop, Dec 16 2016

Status

approved