A367275 a(n) = 3^(n - 1) * (9^n - 1) / 8, n >= 1.

1, 30, 819, 22140, 597861, 16142490, 435847959, 11767897080, 317733227721, 8578797168150, 231627523599099, 6253943137352820, 168856464709057581, 4559124547146149010, 123096362772950806239, 3323601794869686117360, 89737248461481568215441, 2422905708460002470957070

Offset

1,2

Comments

a(n) is the number of potential matchups in a single-elimination ternary tournament (e.g., Jeopardy!) with 3^n contestants (n rounds).

Since a(n) = 3*a(n-1) + 3^(3*n - 3), the sequence in base 3 is 1, 1010, 1010100, 1010101000, 1010101010000, ....

Links

Table of n, a(n) for n=1..18.

Index entries for linear recurrences with constant coefficients, signature (30,-81).

Formula

a(n) = a(n) = 3*a(n-1) + 3^(3*n - 3) with a(0)=1.

a(n) = A000244(n-1)* A002452(n).

G.f.: x/((1 - 3*x)*(1 - 27*x)). - Stefano Spezia, Dec 22 2023

Example

In a 2-round tournament, there are three first-round matches. Each first-round match has one of three possible winners, so there are 3^3 = 27 possible final matchups. Thus a(2) = 30.

Mathematica

a[n_]:=3^(n-1)*(9^n-1)/8; Array[a, 20]

Crossrefs

Cf. A000244, A002452.

Sequence in context: A096722 A261030 A160269 * A367332 A049394 A143169

Adjacent sequences: A367272 A367273 A367274 * A367276 A367277 A367278

Keyword

nonn,easy

Author

Stan Seltzer, Dec 22 2023

Status

approved