[Information Index] [Generation Index] [COS homepage]

Ternary words of given trace and subtrace.

Here we consider the set S(n;t,s) of length n words a1a2···an over the alphabet {0,1,2} that have trace t and subtrace s. The trace of a ternary word is the sum of its digits mod 3, i.e. t = a1+a2+ ··· +an mod 3. The subtrace is the sum of the products of all n(n-1)/2 pairs of digits taken mod 3, i.e. s = SUM( aiaj : 1 < i < j < n ).

(trace,subtrace)
n (0,0) (0,1) (0,2) (1,0)
(2,0) 		(1,1)
(2,1) 		(1,2)
(2,2)
1 1 0 0 1 0 0
2 1 0 2 2 1 0
3 3 0 6 3 3 3
4 9 6 12 9 6 12
5 21 30 30 30 21 30
6 63 90 90 81 81 81
7 225 252 252 225 252 252
8 729 756 702 702 729 756
9 2187 2268 2106 2187 2187 2187
10 6561 6642 6480 6561 6642 6480
11 19845 19602 19602 19602 19845 19602
12 59535 58806 58806 59049 59049 59049
13 177633 176904 176904 177633 176904 176904
14 531441 530712 532170 532170 531441 530712
15 1594323 1592136 1596510 1594323 1594323 1594323
16 4782969 4780782 4785156 4782969 4780782 4785156
17 14344533 14351094 14351094 14351094 14344533 14351094
18 43033599 43053282 43053282 43046721 43046721 43046721
19 129127041 129146724 129146724 129127041 129146724 129146724
20 387420489 387440172 387400806 387400806 387420489 387440172

Examples:

Further Notes:

  • The number S(n;t,s) can be computed from the following recurrence relation

    S(n;t,s) = S(n-1;t,s) + S(n-1;t-1,s-(t-1)) + S(n-1;t-2,s-2(t-2))

                = S(n-1;t,s) + S(n-1;t+2,s+2t+1) + S(n-1;t+1,s+t+1)

  • Column (0,0) is sequence A073947 in Neil J. Sloane's database of integer sequences.
    The sequence has the rational generating function (x-1)2((x-1)3+5x3) / (3x-1)(3x2+1)(3x2-3x+1)

  • Column (0,1) is sequence A073948 in Neil J. Sloane's database of integer sequences.
    The sequence has the rational generating function 6x4(x-1) / (3x-1)(3x2+1)(3x2-3x+1)

  • Column (0,2) is sequence A073949 in Neil J. Sloane's database of integer sequences.
    The sequence has the rational generating function 2x2((x-1)3+2x3) / (3x-1)(3x2+1)(3x2-3x+1)

  • Column (1,0),(2,0) is sequence A073950 in Neil J. Sloane's database of integer sequences.
    The sequence has the rational generating function -x(x-1)((x-1)3+2x3) / (3x-1)(3x2+1)(3x2-3x+1)

  • Column (1,1),(2,1) is sequence A073951 in Neil J. Sloane's database of integer sequences.
    The sequence has the rational generating function x2((x-1)3- 4x3) / (3x-1)(3x2+1)(3x2-3x+1)

  • Column (1,2),(2,2) is sequence A073952 in Neil J. Sloane's database of integer sequences.
    The sequence has the rational generating function -3x3(x-1)2 / (3x-1)(3x2+1)(3x2-3x+1)

  • These numbers are defined and used in a more general setting in the papers:
    C.R. Miers and F. Ruskey, Counting Strings with Given Elementary Symmetric Function Evaluations I: Strings over Zp with p Prime, SIAM J. Discrete Mathematics, 17 (2004) 675-685.
    C.R. Miers and F. Ruskey, Counting Strings with Given Elementary Symmetric Function Evaluations II: Circular Strings, SIAM J. Discrete Mathematics, 18 (2004) 71-82.
    [Information Index] [Generation Index] [COS homepage]
    Questions?? Email The wizard of COS.
    (Please note that the suffix XXXX must be removed from the preceeding email address.)
    It was last updated Saturday, 19-May-2007 23:20:19 PDT.
    There have been 2763 visitors to this page since May 16, 2000 .
    ©Frank Ruskey, 1995-2003.