yukicoder No.727 仲介人moko

概要

品物を売りたい人と買いたい人がそれぞれN人いる.
売りたい人は来ると品物を1つ売り,買いたい人は売っているものからなにか1つ買う.
売買の組み合わせは何通りあるか

解法

愚直DPしか思いつかないしそのままだとOEISに出てこなくて(階乗で割ると出るらしい)辛かった.

  • 品物を買いたい人それぞれについて誰の品物を買うか決める([tex;N!]通り)
  • 売る人買う人の配置を考える(1\times 3\times 5\times ...\times (2N-1)通り) ※詳しくは下で
  • 配置にペアを当てはめる(N!通り)

なので,1\times 3\times 5\times ...\times 2N-1 \times (N!)^2とかになる.

配置について

配置の場合の数は1\times 3\times 5\times ...\times (2N-1)になるらしい.これは2N頂点の完全グラフの完全マッチングの個数らしいがよくわからないのでなぜこうなるかまとめてみる.
まずN=1は明らかに1通り.
N=2はこんな感じで
f:id:SugarDragon5:20180825000737p:plain
N=1の最初とそれに対応するどこかに挿入したものなので,a_2=a_1\times 3
N=3も,
f:id:SugarDragon5:20180825001035p:plain
みたいな感じにN=2の最初と対応する箇所に挿入したもので,a_3=a_2\times 5
こんな感じで以下のような漸化式が立って
 a_1=1,a_{n+1}=a_n\times (2n-1)
これを解けばいい.