Multiplicative

Number Theory Level 4

Let $a_{n}$ denote the number of distinct ways $n$ ordered numbers multiplied together $a_{1}a_{2}a_{3}...a_{n}$ can correctly and progressively be grouped pairwise by parentheses

e.g. $a_{4} = 5$ since $((a_{1}a_{2})a_{3})a_{4}$ , $(a_{1}(a_{2}a_{3}))a_{4}$ , $a_{1}((a_{2}a_{3})a_{4})$ , $a_{1}(a_{2}(a_{3}a_{4}))$ , $(a_{1}a_{2})(a_{3}a_{4})$

Also note $a_{1} = a_{2} = 1$

Find $a_{10}$

Bonus: Find a general formula for $a_{n}$

Not an original problem

The answer is 4862.

1 solution

Alapan Das
Mar 5, 2020

Suppose, the product is like this

${a_1}{a_2}.......{a_n}$ , and we can put parentheses like this...

$({a_1}....{a_r})(a_{r+1}..{a_n})$ ......(1)

And we can get $P_r$ and $P_{n-r}$ ways to put parentheses to each of the parts of (1) parentheses. ( $P_n$ denotes number of ways to pair the product of $n$ ordered numbers in parentheses.)

Then from above case ''breaking'' we found $P_n=\sum_{k=1}^{n-1} {P_{k}}{P_{n-k}}$ ....(2)

Hence,

$P_{10}=2[{P_1}{P_9}+{P_2}{P_8}+{P_3}{P_7}+{P_4}{P_6}]+{P_5}^2$ .

We know $P_1=1, P_2=1$ .

From (2) we can proof $P_3=2, P_4=5, P_5=14, P_6=42, P_7=132, P_8=429, P_9=1430$ .

So, $P_10=2*(1430+429+2*132+5*42)+14^2=4862$ .

time to find a general formula :)

Zhang Xiaokang - 1 year, 3 months ago

Catalan numbers

Pi Han Goh - 1 year, 3 months ago

Not what I had in mind but that'll do!

Zhang Xiaokang - 1 year, 3 months ago

Multiplicative

The answer is 4862.

1 solution

0 pending reports