Let $ n $ be a positive integer. A sequence $(a_1,a_2,\ldots,a_n)$ of length is called $balanced$ if for every $ k $ $(1\leq k\leq n)$ the term $ a_k $ is equal with the number of distinct numbers from the subsequence $(a_1,a_2,\ldots,a_k).$ a) How many balanced sequences $(a_1,a_2,\ldots,a_n)$ of length $ n $ do exist? b) For every positive integer $m$ find how many balanced sequences $(a_1,a_2,\ldots,a_n)$ of length $ n $ exist such that $a_n=m.$
Problem
Source: Moldova TST 2023
Tags: combinatorics
ReaperGod
09.04.2023 20:59
the definition is equivalent to $a_1=1$ and $a_n=a_{n-1}$ or $a_{n-1}+1$ for $n>1$ the problem is trivial from that
vsamc
09.04.2023 21:05
ReaperGod wrote: the definition is equivalent to $a_1=1$ and $a_n=a_{n-1}$ or $a_{n-1}-1$ for $n>1$ the problem is trivial from that shouldn't it be $a_n = a_{n-1}$ or $a_n = a_{n-1} + 1$ for $n>1$? @below np also i agree with your answers for (a) and (b)
ReaperGod
09.04.2023 21:13
vsamc wrote: ReaperGod wrote: the definition is equivalent to $a_1=1$ and $a_n=a_{n-1}$ or $a_{n-1}-1$ for $n>1$ the problem is trivial from that shouldn't it be $a_n = a_{n-1}$ or $a_n = a_{n-1} + 1$ for $n>1$? Yes, that is my fault.
(a) is $2^{n-1}$ and (b) is $\binom{n-1}{m-1}$