A279682 The maximum number of coins that can be processed in n weighings where all coins are real except for one LHR-coin.

1, 3, 9, 19, 49, 123, 297, 707, 1697, 4043, 9561, 22547, 53073, 124571, 291721, 682083, 1592577, 3713643, 8650425, 20132275, 46818225, 108804923, 252718825, 586701827, 1361496929, 3158352139, 7324384281, 16981143379, 39360789521

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

The first seven terms coincide with sequence A102001, which counts all the outcomes that don't have three imbalances in a row.

This sequence also counts the possible outcomes starting in the light or heavy state, and for the coins starting in the real state the possible number of outcomes is a subset for coins starting in the light state.

Examples

			Consider a(7): in addition to outcomes that do not have three imbalances in a row, we are not allowed to have any outcomes like <<=<=<<, in which the first (odd-numbered imbalance) and the fourth (even-numbered imbalance) are both followed by an imbalance. We can replace a less-than sign with a greater-than sign. That means a(7) = A102001(7) - 32 = 739 - 32 = 707.
		

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

Crossrefs

Cf. A279673, A279674, A279684, A279685.

Programs

Magma

I:=[1,3,9,19,49]; [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..30]]; // Vincenzo Librandi, Dec 18 2016

Mathematica

LinearRecurrence[{3, -1, 1, -2, -8}, {1, 3, 9, 19, 49}, 30]

PARI

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

Formula

a(n) = 3*a(n-1) - a(n-2) + a(n-3) - 2*a(n-4) - 8*a(n-5).

G.f.: (1 + x^2 - 6*x^3)/((1 + x)*(1 - 2*x)*(1 - 2*x + x^2 - 4*x^3)). - Ilya Gutkovskiy, Dec 17 2016