1

I have to find pattern of count of series. Lenght of series is $2n$. It is neccessary to use exaclty double times every number in range $[1...n]$ and all of neighboring numbers are different.

Look at example.

$a_0 = 0$ $a_1 = 0$ $a_2 = 2$ (because of $1212$ and $2121$)

And my idea is: $$ a_{n+1}= {2n+1\choose 2}a_n $$

Is it properly ?

xawey
  • 13

1 Answers1

1

For $a_3$, you'll add two $3$'s somewhere to each one of those so they're not next to each other. There are $5$ possible places: the two ends, and three in between two numbers, so there are ${5 \choose 2}$ ways of putting the two $3$'s in so they're not next to each other.

For case $a_n$: There are $2n+1$ possible places to place $n+1$ in each of the ${a_n}$ series of length $2n$, so there are ${2n+1 \choose 2}$ ways to place the two $n$'s in each series.

Or,

$$a_{n+1} = {2n+1 \choose 2} a_n.$$

We can see the closed form by inspection:

$$a_{n} = {2n-1 \choose 2} a_{n-1} \\ = {2n-1 \choose 2}{2n-3 \choose 2}{2n-5 \choose 2} \cdots {7 \choose 2}{5 \choose 2}a_2 \\ = \frac{(2n-1)(2n-2)}{2}\frac{(2n-3)(2n-4)}{2}\frac{(2n-5)(2n-6)}{2} \cdots \frac{7 \cdot 6}{2}\frac{5 \cdot 4}{2}\cdot 2,$$

so

$$a_n =\frac{(2n-1)!}{3 \cdot 2^{n-2}}, n \geq 3.$$

John
  • 26,319
  • So How to find pattern without recursion ? – xawey Aug 15 '14 at 18:33
  • 1
    To find a closed form, note that ${2n+1 \choose 2}=\frac {2n(2n+1)}2$ Look at the numerators of $a_n$ for a while-it looks like a factorial. Then you can justify a closed form. – Ross Millikan Aug 15 '14 at 18:42
  • Could you help say more about your idea? When it comes to my idea: $a_n = {2n-1\choose 2}a_{n-1} = {2n-1 \choose 2}\cdot {2n-3\choose 2}\cdot {2n-5 \choose 2} \cdot... \cdot {3\choose 2}$ And it is the same that I choose : ${2n-1 \choose n}$. But id doesn't work. What do I do wrong ? – xawey Aug 15 '14 at 19:16
  • I agree with your recursion formula. Note that $a_2 = 2.$ Your formula in the comment above takes it down one too far, I think. It should end with $\cdots {7 \choose 2}{5 \choose 2}\cdot 2$. – John Aug 15 '14 at 19:38