A369580 a(n) := f(n, n), where f(0,0) = 1/3, f(0,k) = 0 and f(k,0) = 3^(k-1) if k > 0, and f(n, m) = f(n, m-1) + f(n-1, m) + 3*f(n-1, m-1) otherwise.

2, 16, 138, 1216, 10802, 96336, 861114, 7708416, 69072354, 619380496, 5557080938, 49879087296, 447852531986, 4022246329936, 36132550233498, 324645166734336, 2917340834679234, 26219438520320016, 235672871308226634, 2118552629658530496, 19046140604787232242, 171241206828437556816

Offset

1,1

Comments

Take turns flipping a fair coin. The first to n heads wins. Sequence gives numerator of probability of first player winning. The denominator is .3^(2n-1).

It appears that a(n) for any n is divisible by 2^(A001511(n)).

Links

Tadayoshi Kamegai, Table of n, a(n) for n = 1..100

Bartosz Sobolewski and Lukas Spiegelhofer, Decomposing the sum-of-digits correlation measure, arXiv:2411.07779 [math.NT], 2024. See p. 16.

Formula

Limit_{n->oo} a(n)/3^(2n-1) = 1/2.

a(n) = Sum_{i>=n} Sum_{j=0..n-1} binomial(i-1,n-1)*binomial(i-1,j)*3^(2n-1)/2^(2i-1).

9*a(n) - a(n+1) = 2*A162326(n) (conjectured).

a(n) = 3^(2n-1)*A(n, n) where A(0, k) = 0 for k > 0, A(k, 0) = 1 for k >= 0 and A(n, m) = (A(n-1, m) + A(n, m-1) + A(n-1, m-1))/3.

Prog

(Python)
def lis(n):
    table = [[0]*(n+1) for _ in range(n+1)]
    table[1][1] = 2
    for i in range(1, n+1) :
        table[i][0] = 3**(i-1)
    for i in range(1, n+1) :
        for j in range(1, n+1) :
            if (i == 1 and j == 1) :
                continue
            table[i][j] = table[i][j-1] + table[i-1][j] + 3*table[i-1][j-1]
    return [int(table[i][i]) for i in range(1, n+1)]

Crossrefs

Cf. A344576, A050231, A001850.

Cf. A001511 (see comments), A162326 (see formula).

Sequence in context: A002302 A378461 A348803 * A056662 A348618 A151402

Adjacent sequences: A369577 A369578 A369579 * A369581 A369582 A369583

Keyword

nonn

Author

Tadayoshi Kamegai, Jan 26 2024

Status

approved