# Number of sequences

• Apr 2nd 2014, 10:10 PM
SlipEternal
Number of sequences
Let $x \in (1,\infty)\setminus \mathbb{Z}$ be any non-integer greater than one. Let $n\in \mathbb{Z}^+$ be any positive integer such that $\lfloor (n-1)x \rfloor +1 < \lfloor nx \rfloor$ (for example, if $x=\sqrt{2}$, then $n$ might be $5$ since $\lfloor 4\sqrt{2} \rfloor +1 = 6 < \lfloor 5\sqrt{2} \rfloor = 7$). How many sequences of integers $\displaystyle (a_k)_{k=1}^n$ satisfy the following properties?

1. $0<a_1<\cdots < a_n < nx$

2. For each $k=1,\ldots, n-1$, $a_k > kx$

In the example above, with $x=\sqrt{2}, n=5$, there are exactly three such sequences: $\{3,4,5,6,7\}$, $\{2,4,5,6,7\}$, and $\{2,3,5,6,7\}$.

If $n=8$, there are 12 such sequences.

Is there a simple way to compute this? I would imagine there is not a closed form for the solution, but I would like a faster way to calculate it than brute forcing it by actually finding all sequences that satisfy the conditions.
• Apr 3rd 2014, 04:11 AM
SlipEternal
Re: Number of sequences
Thinking more about this, I can try to find the number of different systems of distinct representatives. Given $x$ and $n$ as above, let $t = \lfloor nx \rfloor$. Then, for $k=1,\ldots, (n-1)$, let $A_k = \{\lceil kx \rceil, \ldots, t-n+k \}$ and $A_n = \{t\}$. Phrased this way, the problem becomes counting the number of systems of distinct representatives.
• Apr 3rd 2014, 09:34 AM
SlipEternal
Re: Number of sequences
Playing with it a little, I was able to get a generating function. If $x \to 1.5^+$ (in other words, it is infinitesimally larger than 1.5 so that $\lfloor (2n-1)x \rfloor +2 = \lfloor 2nx \rfloor$ for all $n$, then the sequence $(b_k)_{k\ge 0}$ which counts the number of sequences for $n=2k+2$ has generating function (according to Wolframalpha):

$f(z) = \dfrac{2 \cos\left( \dfrac{2}{3} \arcsin\left( \dfrac{3\sqrt{3z} }{2} \right) \right) - 2}{3z}$

However, this looks messy enough that I will not even attempt to find a closed form for $(b_k)$.

Since rational numbers are a bit easier to work with, perhaps a series of generating functions could approximate the correct generating function for any $x$. Anyway, this is close enough for now. Thanks to any who thought about it.
• Apr 4th 2014, 01:02 PM
SlipEternal
Re: Number of sequences
I found a closed form if $x \in (1,\infty) \setminus \mathbb{Q}$:

Define $a_n(x) = \lfloor nx \rfloor$ and $b_n(x) = a_n(x) - n$. Let $c_n(x)$ be the number of sequences satisfying the conditions in post 1.

$\displaystyle c_n(x) = \sum_{\displaystyle k=0}^{\displaystyle b_n(x)} \binom{n+k-1}{n-1} - \sum_{\displaystyle k=0}^{\displaystyle b_{n-1}(x)} \binom{n+k-2}{n-2}(b_n(x)-k+1)$

Wolframalpha gave me a simplified closed form for $c_n(x)$, but something is not correct...:

$\displaystyle c_n(x) = \dfrac{\displaystyle \Big(\lfloor nx \rfloor - n + 1 \Big) \binom{ \lfloor nx \rfloor }{ n-1 } }{\displaystyle n} - \dfrac{\displaystyle \Big( \lfloor (n-1)x \rfloor -n + 2 \Big) \Big( n\big( \lfloor nx \rfloor - \lfloor (n-1)x \rfloor \big) + \lfloor (n-1)x \rfloor -n + 1\Big) \binom{ \lfloor (n-1)x \rfloor }{ n-2 } }{\displaystyle n(n-1) }$
• Apr 4th 2014, 02:37 PM
SlipEternal
Re: Number of sequences
I figured out what I did wrong. I forgot to use inclusion/exclusion, so those counts were grossly inaccurate.
• Apr 5th 2014, 02:13 PM
SlipEternal
Re: Number of sequences
Ok, I finally got it and tested it. I found a recursion algorithm that actually works (for any $x \in (1,2) \setminus \mathbb{Q}$).

$c_1(x) = 1$

$\displaystyle c_n(x) = \binom{\lfloor nx \rfloor-1}{n-1} - \sum_{k=1}^{n-1}c_k(x) \binom{\lfloor nx \rfloor - \lfloor kx \rfloor - 1}{n-k-1}, n \ge 2$