Stirling permutations

hbghlyj

symmetricfunctions.com
$Q_n$ 是 $1,1,2,2,3,3,\dots,n,n$ 的排列的集合，使得在等于 $i$ 的两项之间，只出现大于 $i$ 的数字。
例如，$12234431\in Q_n$.
求证$$|Q_n| = (2n-1)!!$$

hbghlyj

例如，三阶 Stirling 排列有 15 个

1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3;
1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1;
1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1;
1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1;
3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1。