سوال ۵
در یک ایستگاه قطار ریلی به شکل زیر وجود دارد:
در سمت ورودی صفی از $n$ واگن با شماره‌های ۱ تا $n$ به دنبال هم و به ترتیب شماره‌هایشان قرار دارند، به طوری که واگن شماره‌ی ۱ در ابتدا و وااگن شماره‌ی $n$ در انتهای صف قرار دارند. قسمتی که در شکل پشته نامیده شده است بن‌‌بست است و واگن‌ها می‌توانند به ترتیب از ورودی وارد پشته شده و از طریق خروجی خارج شوند. پشته به اندازه‌ی کافی طولانی است و می‌تواند همه‌ی واگن‌ها را در خود جای دهد. بدیهی است که اگر تعدادی واگن به ترتیب وارد پشته شوند، قطاری که آخر وارد شده باشد اولین قطاری از این دسته است که خارج می‌شود.
نحوه‌ی حرکت واگن‌ها در این ایستگاه را با اعمال زیر می‌توان نشان داد:
- عمل $I$: یک واگن از ورودی وارد پشته می‌شود.
- عمل $O$: کلیه‌ی واگن‌ها موجود در پشته از آن به سمت خروجی خارج می‌شوند.
تنها اعمال فوق مجازند و توجه کنید که هیچ واگنی نمی‌تواند از خروجی به پشته و یا از پشته به ورودی بازگردد. همچنین برداشتن واگن‌ها از روی ریل مجاز نیست. با توجه به این اعمال، بدیهی است که شماره‌های واگن‌های خروجی جایگشتی از دنباله‌ی ورودی $1,2,…,n$ که شماره‌های واگن‌هاست، می‌باشد.
جایگشت $a_1,a_2,…,a_n$ از اعداد $1,2,…,n$ را دنباله‌ی قابل تولید می‌نامیم اگر بتوان آن را با استفاده از اعمال $I$ و $O$ تولید کرد. به عنوان مثال دنباله‌ی $2,1,4,3$ یک دنباله‌ی قابل تولید استو ترتیب اعمالی که این دنباله را تولید می‌کند به صورت زیر است:
$I-1$: ۱ وارد پشته می‌شود.
$I-2$: ۲ وارد پشته می‌شود.
$O-3$: پشته خالی می‌شود (ابتدا ۲ و سپس ۱ از پشته خارج می‌شوند).