7
$\begingroup$

While looking at various ways of computing $\binom{2n}{n}$ for various values of $n$, I tried the following method: First, define the sequence $T_0=\{n+1,...,2n\}$, then for $k=1,...,n$, given $T_{k-1}=\{a ^{(k-1)}_1,...,a^{(k-1)}_n\}$, define: $$ t_{0}:=k , \\\,\\ t_{i}:=\frac{t_{i-1}}{\gcd\left(t_{i-1},\,a_i^{(k-1)}\right)}, \\ \,\\ a_{i}^{(k)}:=\frac{a_i^{(k-1)}}{\gcd\left(t_{i-1},\,a_i^{(k-1)}\right)} $$ for $i=1,...,n$. Eventually, we get $\binom{2n}{n}=a_1^{(n)}\cdots a_n^{(n)}$.
By indicating for each $k=1,...,n$ which indices are affected by it (i.e. those $i$ for which $a_i^{(k-1)}\neq a_i^{(k)}$), we get a patterns like the following:

($n=10$)Pattern for n=10 The graph of the case $n=10$ is gotten as follows. In this case we have: $$ T_0=\{11,12,13,14,15,16,17,18,19,20\} \\ T_1=\{11,12,13,14,15,16,17,18,19,20\} \\ T_2=\{11,6,13,14,15,16,17,18,19,20\} \\ T_3=\{11,2,13,14,15,16,17,18,19,20\} \\ T_4=\{11,1,13,7,15,16,17,18,19,20\} \\ \cdots $$ So the first column won't have any points, because the first factor $11$ never changes. The second and third column would have a point at height $2$, because the second number changes $12\to6\to2$ while we cancel $2$ and $3$ respectively. The fourth column would have 2 points at height $2$ and $4$, because while cancelling the factor $4$ the second entry $2\to1$ and the fourth entry $14\to7$ etc..

($n=100$)Pattern for n=100 ($n=1000$)Pattern for n=1000 ($n=10000$)Pattern for n=10000 ($n=40000$)Pattern for n=40000 Interestingly, by removing the entries for prime $k$'s from the graph we get the following image: ($n=40000$)Pattern for n=40000 without primes

Furthermore by coloring $k$'s of the form $p$, $2p$ and $3p$ in blue, green and cyan respectively, where $p$ is a prime, we get the following plot:

($n=40000$)Pattern for n=40000 with primes colored

Here's the same image without the red $k$'s:

($n=40000$)Pattern for n=40000 with primes only

And here's with additionally $4p$, $5p$ and $6p$ as magenta, yellow and black, respectively:

($n=40000$)enter image description here

Are there any known numerical properties of that can explain the above pattern?


$\endgroup$
  • 1
    $\begingroup$ I'm not sure if your notation is standard, but it's extremely confusing to me. In particular you seem to be reusing $k$, both as an index and as a variable name (maybe even as two variable names?). $\endgroup$ – Mees de Vries Aug 20 at 14:41
  • 3
    $\begingroup$ The idea seems to be to calculate $$\frac{(n+1)(n+2)\cdots(2n)}{1\cdot2\cdot3\cdots n}$$ in such a way that you divide the numerator by one factor of the denominator at a time, and in such a way that you do as much cancellation as possible as early as possible, processing whatever factors remain in the numerator in sequence. BUT FER PETE'S SAKE WHAT IS THE PROCESS OF TURNING THIS CALCULATION INTO A PLOT? $\endgroup$ – Jyrki Lahtonen Aug 20 at 17:14
  • 1
    $\begingroup$ I moved an edited version of the explanation for $n=10$ adjacent to the plot. I think that helps readers. $\endgroup$ – Jyrki Lahtonen Aug 20 at 17:35
  • 1
    $\begingroup$ I think I can explain the rightmost "dotted line" with slope $m=2$. That "line" contains a dot (at least) for each prime number $p$ in the range $(n/2,n]$. In the cancellation process that factor $p$ will always be cancelled by the factor $2p$ in the numerator. This is because among the integers $n+1,n+2,\ldots,2n$, $2p$ is the smallest one that is divisible by $p$. The index of $2p$ in the numerator is $2p-n$. So to each such prime $p$, we have a dot at the point $(p,2p-n)$ in the plot. Those all fall on the line of slope $2$ through the point $(n,n)$. $\endgroup$ – Jyrki Lahtonen Aug 20 at 17:41
  • 2
    $\begingroup$ Interesting! ${}$ $\endgroup$ – Jyrki Lahtonen Aug 20 at 18:57

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.