3 Feb. 2010

Let A and B be subsets of a finite group G.
Let F[A,B](n) be the number of ways c(1)*c(2)*...*c(n) is an element of B with c(m) in A for all n >= m > 0.

My interest in quaternions/floretions leads me to consider these groups first :). That said, I would be interested to know what the results are for other groups (Furthermore, I make no claim to be the first person to pose any questions discussed here and would be happy for further references.)

Let G = {i, -i, j, -j, k, -k, e, -e} = {+-i, +-j, +-k, +-e} be the quaternion group and A = {i, j, k}. Since this is the only set I will be using for A at the moment, I simplify the notation by writing F[B](n) for F[A,B](n) and leave off the set brackets.

What I started out wanting to know was an expression for F[e](n). As a small bonus, we will see A099583, A054878 (closed walks of length n along the edges of a tetrahedron based at a vertex) are combinatorially related. First, some examples: Similarly, Lemma:
  1. F[+-e](n) = F[e](n) + F[-e](n)
  2. F[+-e](n) = F[+-i, +-j, +-k](n-1)
  3. F[e](n) = F[-i, -j, -k](n-1)
  4. F[-i,-j,-k](n) = 3*F[-e](n-1) + F[+-i, +-j, +-k](n-1)
  5. F[+-i, +-j, +-k](n) = 2*F[+-i, +-j, +-k](n-1) + 3*F[+-e](n-1)
  6. F[+-i, +-j, +-k, +-e](n) = 3^n
Proof: 1. and 6. should be clear upon inspection. To show the 2nd identity, ask: what quaternions, when multiplied by i, j, or k, are in the set {+-e}? The answer is +-i, +-j, +-k. This shows
F[+-e](n) = c*F[+-i, +-j, +-k](n-1) where c is the number of ways to multiply i (or -i or j or -j etc.) by an element from A = {i, j, k} to return an element from the set {+-e}. Since there is only one way to multiply i in this case, namely i*i = -e, we have c = 1, q.e.d. The other identities are left as exercises.

From 2 and 5 we have:

Corollary: F[+-e](n) = 2*F[+-e](n-1) + 3*F[+-e](n-2)

Thus, A054878(n) (which satisfies the recurrence a(n) = 2a(n-1)+3a(n-2)) and F[+-e](n) are the same sequence (upon defining F[+-e](0) = 1).

We can now answer the original question about F[e](n).

The initial values are F[e](1) = 0, F[e](2) = 0.

Therefore, F[e](3) = (3 + 3(-1)^3)/2 + 3^(3-2) - 3*0 = 3
F[e](4) = (3^2 + 3(-1)^4)/2 + 3^(4-2) - 3*0 = 15
F[e](5) = (3^3 + 3(-1)^5)/2 + 3^(5-2) - 3*3 = 12 + 27 - 9 = 30

(F[e](n)) = (0, 0, 3, 15, 30, 78, 273, 861, 2460, 7260, 22143)

The explicit formula seems to be:
F[e](n) = (3*(-1)^n + 2*(-I)^n + 3^(n/2) + 2*I^n*3^(n/2) + 3^n)/8

Finally, F[-e](n) = F[+-e](n) - F[e](n)
(F[-e](n)) = (0, 3, 3, 6, 30, 105, 273, )
(the bisections of (F[-e](n)) and (F[e](n)) are equal)

From R.Mathar: The recurrence 0,0,3,15,30,78,273,...
obeys a(n)= 2*a(n-1) +6*a(n-3) +9*a(n-4)

with g.f. -3*x^3*(1+3*x)/((3*x-1)*(1+x)*(3*x^2+1)) = -1+1/2/(3*x^2+1)+3/8/(1+x)-1/8/(3*x-1)

and "closed form"

F[+-e](n), essentially A054878(n), = 0,3,6,21,60,183,546,1641,4920,14763,.. (n>=1) = (3^n+3*(-1)^n)/4

has g.f. 3*x^2/((1+x)*(1-3*x)) = -1 + ( 3/(1+x)+1/(1-3*x)) /4

F[e](n) has g.f. 3*x^3*(1+3*x)/((1+x)*(1-3*x)*(1+3*x^2))

and the difference

7 Feb. 2010

Continuing with the above thoughts, the goal for today is to obtain combinatorial interpretations of integer sequences satisfying general 4th order linear recurrences via floretions. As the reader is likely to be well aware, such sequences have a multitude of combinatorial interpretations, for example in terms of tiles and closed walks.

Returning to the original definition: Let A and B be subsets of a finite group G.
Let F[A,B](n) be the number of ways c(1)*c(2)*...*c(n) is an element of B with c(m) in A for all n >= m > 0.

(see Robert Munafo's introduction if the terms ieb(X), tes(X), etc. are unclear)

In particular, let A be any subset the floretion group. Let B be the set consisting of a single group element.

Example 1:

Choose A = {ii, ik, ee} and B = {ee}. It is easily shown that tesseq(ii + ik + ee) = (1, 3, 7, 17, 41, ...), i.e. "Numerators of continued fraction convergents to sqrt(2)" from the second term.
But tes((ii + ik + ee)^n) = F[A, {ee}](n) - F[A, {-ee}](n), yielding yet another combinatorial interpretation of A001333, namely:

For n > 0, A001333(n) is the number of ways c(1)*c(2)*...*c(n) = ee subtracted by the number of ways c(1)*c(2)*...*c(n) = -ee with c(m) in {ii, ik, ee} for all n >= m > 0.

Example 2:

Choose A = {ie, kk, ee}. B = {ie}. Here, we have iebseq(ie + kk + ee) = (1, 2, 3, 4, 5, ) = natural numbers. Similar to above, ieb((ie + kk + ee)^n) = F[A, {ie}](n) - F[A, {-ie}](n).

Conclusion: Combining tesseq, iebseq, jebseq, ... as the difference of two F[A,B] terms for appropriate sets A and B appears to be a basic but interesting idea. Though the fact that tesseq(X) always satisfies a 4th order linear reccurence for any floretion X was clear to begin with (using matrix methods or Floret's Equation or considering special cases), it is less clear what the situation is like for general F[A,B]. A next step as part of a closer investigation could be to show that F[A,{ee}](n) and F[A,{-ee}](n) themselves satisfy 4th order linear recurrences. Apart from shedding light on the situation, doing so would return yet another way to prove that tesseq has the same property!

Back to floretions