5
$\begingroup$

A word (i.e., ordered string of letters) is bifix-free provided it has no proper initial string and terminal string that are identical. For example, the word $ingratiating$ has bifix $ing$, but the word $ingratiate$ is bifix-free.

Let $a_n^{(q)}$ be the number of bifix-free words over a fixed $q$-letter alphabet. The generating function $f(x) = f^{(q)}(x) = \sum_{n = 0}^{\infty} a_nx^n$ satisfies the functional equation $$f(x) = qx + qxf(x) - f(x^2).$$

Solving for $f(x)$ gives $$f(x) = \frac{qx - f(x^2)}{1-qx} = \cdots = \sum_{j=0}^{\infty} \frac{(-1)^jqx^{2^j}}{\prod_{k=0}^{j} (1 - qx^{2^k})}.$$

(Q1) Is there a "nice" solution to this functional equation, perhaps one that does not involve an infinite product or sum?

Here is a plot of $f^{(2)}(x)$ generated in Sage:

enter image description here

The limit as $n \to \infty$ of the probability that a uniformly random word of length $n$ is bifix-free is $1 - f^{(q)}(q^{-2})$. From the initial three terms in the alternating series above, as $q \to \infty$, $$f^{(q)}(q^{-2}) = \frac{1}{q-1} - \frac{1+o(1)}{q^3}.$$

(Q2) What else can be said specifically about $f^{(q)}(q^{-2})$ for integers $q \geq 2$? Is there a simpler formula than the infinite series above? Are these values rational? ...algebraic?

Here is a plot of $f^{(x)}(x^{-2})$ generated in Sage:

enter image description here

(The combinatorics-on-words paper associated with this function is here.)

Improve this question
$\endgroup$
6
  • $\begingroup$ Something interesting I noticed: there's an easy way to get $f_q(x)$ from any other $f_q(x)$, by scaling $x$ by $q$. As such, you only need to care about $f_1(x)$. $\endgroup$
    – user44191
    Commented Oct 14, 2016 at 5:22
  • $\begingroup$ Also, as such, any information about $f_q(q^{-2}) = f(\frac{1}{q})$, so any information about that probability is equivalent to information about your original function itself. $\endgroup$
    – user44191
    Commented Oct 14, 2016 at 5:30
  • 1
    $\begingroup$ @user44191 The numerator in the summation has $q\cdot x^{2^j}$ not $(qx)^{2^j}$. $\endgroup$
    – D. Ror.
    Commented Oct 14, 2016 at 14:52
  • $\begingroup$ Ah, you're right, I made a mistake when trying to deal with $f(x^2)$. $\endgroup$
    – user44191
    Commented Oct 14, 2016 at 18:41
  • $\begingroup$ It might be nice for you to provide a table of values of $a_n^{(q)}$ for small values of $n$ and $q$. $\endgroup$
    – Timothy Chow
    Commented Oct 14, 2016 at 20:06

0

Reset to default

You must log in to answer this question.