A387012 Number of ternary strings of length 2*n that have fewer 0's than the combined number of 1's and 2's.
0, 4, 48, 496, 4864, 46464, 436992, 4068096, 37601280, 345733120, 3166363648, 28910051328, 263320698880, 2393742770176, 21726260035584, 196938517118976, 1783247797223424, 16132649384411136, 145839570932465664, 1317564543167102976, 11896996193604993024, 107375816824319901696
Offset: 0
Examples
a(2) = 48 since the strings of length 4 are the following (number of permutations in parentheses): 1110 (4), 1120 (12), 1220 (12), 2220 (4), 1111 (1), 1112 (4), 1122 (6), 1222 (4), 2222 (1).
Programs
-
Mathematica
a[n_] := 9^n - Sum[2^(n-k) * Binomial[2*n, n-k], {k, 0, n}]; Array[a, 22, 0] (* Amiram Eldar, Aug 16 2025 *)
Formula
a(n) = 9^n - Sum_{k=0..n} 2^(n-k)*binomial(2*n,n-k).
G.f.: (sqrt(1-8*x)*(sqrt(1-8*x)+12*x-1)-8*x*(1-9*x))/((1-9*x)*sqrt(1-8*x)*(sqrt(1-8*x)+12*x-1)).
D-finite with recurrence n*a(n) +(-29*n+28)*a(n-1) +12*(23*n-41)*a(n-2) +432*(-2*n+5)*a(n-3)=0. - R. J. Mathar, Aug 26 2025