Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By SlipEternal

Math Help - Number of sequences

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    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.
    Last edited by SlipEternal; April 2nd 2014 at 10:19 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    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.
    Last edited by SlipEternal; April 3rd 2014 at 09:37 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    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) }$
    Last edited by SlipEternal; April 4th 2014 at 01:57 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    Re: Number of sequences

    I figured out what I did wrong. I forgot to use inclusion/exclusion, so those counts were grossly inaccurate.
    Last edited by SlipEternal; April 4th 2014 at 03:28 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    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$
    Last edited by SlipEternal; April 5th 2014 at 02:47 PM.
    Thanks from romsek
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Difficult number sequences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 27th 2011, 05:37 PM
  2. Number sequences
    Posted in the Algebra Forum
    Replies: 5
    Last Post: June 6th 2010, 06:20 AM
  3. Number Sequences hard
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 19th 2009, 11:36 AM
  4. Number sequences
    Posted in the Algebra Forum
    Replies: 7
    Last Post: February 16th 2009, 06:14 AM
  5. Puzzling Number Sequences
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: February 16th 2007, 04:02 PM

Search Tags


/mathhelpforum @mathhelpforum