A073947 Number of strings over Z_3 of length n with trace 0 and subtrace 0.
1, 1, 3, 9, 21, 63, 225, 729, 2187, 6561, 19845, 59535, 177633, 531441, 1594323, 4782969, 14344533, 43033599, 129127041, 387420489, 1162261467, 3486784401, 10460471301, 31381413903, 94143533121, 282429536481, 847288609443, 2541865828329, 7625594296341
Offset: 1
Examples
a(3;0,0)=3 since the three ternary strings of trace 0, subtrace 0 and length 3 are { 000, 111, 222 }.
Links
- Harvey P. Dale, Table of n, a(n) for n = 1..1000
- Max Alekseyev, PARI/GP scripts for miscellaneous math problems
- F. Ruskey, Strings over Z_3 with given trace and subtrace
- F. Ruskey, Strings over GF(3) with given trace and subtrace
- Index entries for linear recurrences with constant coefficients, signature (6,-15,27,-36,27).
Programs
-
Mathematica
LinearRecurrence[{6,-15,27,-36,27},{1,1,3,9,21},40] (* Harvey P. Dale, Nov 29 2024 *)
Formula
a(n; t, s) = a(n-1; t, s) + a(n-1; t+2, s+2t+1) + a(n-1; t+1, s+t+1) where t is the trace and s is the subtrace.
G.f.: q*(21*q^4-21*q^3+12*q^2-5*q+1)/[(1-3q)(1+3q^2)(1-3q+3q^2)]. - Lawrence Sze, Oct 24 2004
Extensions
Terms a(21) onward from Max Alekseyev, Apr 09 2013
Comments