图为铁路交换网络示意图，编号为1, 2, 3,···,

图为铁路交换网络示意图，编号为1, 2, 3,···,n的各列车厢停留在左铁轨上，接下来它们要从右铁轨离开，离开时的编号顺序可能发生变化。左铁轨上的车厢必须通过下面的栈才能到达右铁轨，到达栈中的车厢可以继续停在栈里或者离开到右铁轨上。______

①求解n=3时，右铁轨上所有可能的车厢序列；

②求解n=4时，右铁轨上所有可能的车厢序列；

③对任意的n,给出右铁轨上所有可能的车厢序列的个数。