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.)

$\endgroup$
  • $\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 Oct 14 '16 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 Oct 14 '16 at 5:30
  • 1
    $\begingroup$ @user44191 The numerator in the summation has $q\cdot x^{2^j}$ not $(qx)^{2^j}$. $\endgroup$ – D. Ror. Oct 14 '16 at 14:52
  • $\begingroup$ Ah, you're right, I made a mistake when trying to deal with $f(x^2)$. $\endgroup$ – user44191 Oct 14 '16 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 Oct 14 '16 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.