Problem

Source: Moldova TST 2023

Tags: combinatorics



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.$