n یک عدد طبیعی دلخواه است. یک ترتیب دلخواه از اعداد ۱ تا n که در آن هر یک از اعداد ۱ تا n دقیقاً یک بار آمده باشد را یک جایگشت از \{1, 2, \dots, n\} مینامیم. میگوییم جایگشت p_1, p_2, \dots, p_n در دنباله a_1, a_2, \dots, a_k ظاهر شده است اگر اندیسهای 1 \le i_1 < i_2 < \cdots < i_n \le k وجود داشته باشند به طوری که برای هر 1 \le j \le n داشته باشیم a_{i_j}=p_j . بهعنوان مثال جایگشت 1,3,2 در دنباله 3,1,2,3,2,3 ظاهر شده است.
یک دنباله از اعداد ۱ تا n یک دنباله جالب نامیده میشود اگر هر جایگشت دلخواهی از \{1, 2, \dots, n\} در این دنباله ظاهر شده باشد.
ثابت کنید برای هر عدد طبیعی n حداقل یک دنباله جالب به طول 2^n - 1 وجود دارد.
پاسخ