Strings on [n] with certain restrictions

JBL

Compute the number of strings of length $k$ with entries in $[n] = \{1, 2, \ldots, n\}$ such that between any two occurrences of the letter $i$ there is an occurrence of a letter strictly larger than $i$ .

For example, with $n = 3$ and $k = 3$ there are 9 such strings: 121, 131, 232 and the six permutations of 123.

I don't know a solution, so in particular I don't know whether there is a nice answer Embarassed

. So, if you can say anything else interesting about these sequences .... (An easy statement: $k \leq 2^n - 1$ , with a single string when $k = 2^n - 1$ .)

Edit: Conjecture: this is the same as A122888 in the OEIS.

Later edit: the conjecture is true. Let $f(n, k)$ be the number of such strings of length $k$ on $[n]$ . I claim that this is the coefficient of $x^{k + 1}$ in the $n$ -fold composition of $g(x) = x + x^2$ with itself. For $n = 1$ this is clear: there is one string of length 0 and one of length 1 and no others. Now, we show that they obey the same recursion. By polynomial arithmetic,
$\begin{align*} [x^{k + 1}] g^{(n)}(x) & = [x^{k + 1}]g^{(n - 1)}(x) + [x^{k + 1}]\left(g^{(n - 1)}(x)\right)^2 \\ & =...$ where $[x^*]$ is a coefficient extractor. On the other hand we have
$f(n, k) = f(n - 1, k) + \sum_{i = 0}^{k - 1}f(n - 1, i)\cdot f(n - 1, k - i)$
because the first term counts strings in which $n$ does not appear while the second term counts strings in which $n$ does appear. (The latter is true because when $n$ appears, exactly one copy is present and the substrings of our original string to the left and right of this copy of $n$ can be any valid strings on $[n - 1]$ .)

**Posted:** Tue May 06, 2008 9:17 am

_________________
Joel
Hi Deeps! <3

JBL

Follow-up: how many strings are there of length $k$ with entries in $[n]$ such that between any two occurrences of the letter $i$ there is an occurrence of $i + 1$ ?

Or, as a special case: now we have that $k \leq \frac {n(n + 1)}{2}$ . How many strings of length $\frac{n(n + 1)}{2}$ are there with entries in $[n]$ such that between any two occurrences of the letter $i$ there is an occurrence of $i + 1$ ?

**Posted:** Tue May 12, 2009 11:57 am

_________________
Joel
Hi Deeps! <3

darij grinberg

**Posted:** Tue May 12, 2009 4:35 pm

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

JBL

Thanks and thanks! A reasonably nice formula with some other good combinatorial interpretations -- so it seems still possible that there is a nice formula of some sort.

**Posted:** Thu May 14, 2009 6:17 pm

_________________
Joel
Hi Deeps! <3