二重階乗
これで再帰的構成が得られたから、スターリング順列の数が二重順列で数えられることは帰納的にわかる。 あるいは同じ数の対の間に入れるのは大きい数だけという制約の代わりに、この多重集合の置換に現れる、同じ数の対のうち最初のほうは、あるきまった順番に並ぶという制約で考えることもできる。そのような順列が定めるのは、順列の 2k 箇所に関するマッチングであり、したがってふたたび個の順列の総数が二重階乗で数えられることがわかる
ヒープの順序木: k + 1 個のノードが 0, 1, 2, ..., k でラベル付けられた木で、ルートのラベルが 0 かつ、ほかのノードのラベルはその親ノードのラベルより大きく、各ノードの子ノードが決まった順になっている。この木のオイラー巡回(英語版) (Euler tour) はスターリング順列を与え、任意のスターリング順列はこの方法で木で表現できる
根なし二分木(英語版)で n + 5/2 個のラベル付き葉ノードを持つもの。そのような木の各々は、葉ノードが一つ少ない木から、n 本の辺の一つを細分して、新たな頂点を新たな葉ノードの親にすれば作れる。