A385726 a(n) = 3^n - 6*binomial(n,4) - 6*binomial(n,3) - 4*binomial(n,2) - 2*n - 1.

0, 0, 0, 2, 18, 102, 446, 1668, 5676, 18260, 56868, 173934, 526862, 1587978, 4774386, 14337536, 43031928, 129121224, 387396584, 1162231674, 3486747690, 10460308430, 31381005510, 94143114012, 282429459428, 847288518492, 2541865721676, 7625597360678, 22876792310886, 68630377198770

Offset

0,4

Comments

a(n) is the number of ternary strings of length n that contain at least three 1's or at least three 2's (or both).

Links

Paolo Xausa, Table of n, a(n) for n = 0..2000

Index entries for linear recurrences with constant coefficients, signature (8,-25,40,-35,16,-3).

Formula

E.g.f.: exp(x)*(exp(2*x)-(1 + x + x^2/2)^2).

a(n) = 3^n - A385689(n).

G.f.: 2*x^3*(1 + x + 4*x^2)/((1 - 3*x)*(1 - x)^5). - Stefano Spezia, Jul 08 2025 [corrected by Jason Yuen, Jan 07 2026]

Example

a(3) = 2 since the strings are 111 and 222.
a(4) = 18 since the strings are (number of permutations in parentheses): 1111 (1), 1112 (4), 1110 (4), 1222 (4), 0222 (4), 2222 (1).

Mathematica

A385726[n_] := 3^n - n*(n*(n*(n - 2) + 7) + 2)/4 - 1; Array[A385726, 30, 0] (* or *)
LinearRecurrence[{8, -25, 40, -35, 16, -3}, {0, 0, 0, 2, 18, 102}, 30] (* Paolo Xausa, Jan 07 2026 *)

Crossrefs

Cf. A383343, A385689.

Sequence in context: A267691 A219758 A005969 * A094251 A345969 A101570

Adjacent sequences: A385723 A385724 A385725 * A385727 A385728 A385729

Keyword

nonn,easy

Author

Enrique Navarrete, Jul 08 2025

Extensions

Data corrected by Paolo Xausa, Jan 07 2026

Status

approved