※ ChatGPTを利用し、要約された質問です（原文：1,2,3,…,nと書いてあるカードと箱があって）
カードと箱の入れ方の個数を求める方法は？
このQ&Aのポイント
1枚のカードと、1個の箱があって、カードを箱に入れていくとき、一致する番号が無いような入れ方の個数を求める方法は？
カードと箱の入れ方の個数を求めるには、A(n)=(n-1)(A(n-1)+A(n-2))という漸化式が使えます。
具体的には、1枚のカードと1個の箱の場合は0、2枚のカードと2個の箱の場合は1、4枚のカードと4個の箱の場合は9となります。
n枚のカードと、n個の箱があり
それぞれに1,2,3,…,nの異なる1文字が書いてあります。
カードを1枚ずつそれぞれの箱に入れていくとき
カードに書かれた番号と箱に書かれた番号が一致するものが無いような
入れ方の個数をA(n)とします。
例えばA(3)は
・1の箱に2のカード,2の箱に3のカード,3の箱に1のカード
・1の箱に3のカード,2の箱に1のカード,3の箱に2のカード
の2通りだけなので、A(3)=2です。
A(1)=0,A(2)=1,A(4)=9のようですが
A(n)の一般項または漸化式を求めるにはどうしたら良いでしょうか?
A(n)=(n-1)(A(n-1)+A(n-2))
かと思ったのですが、自信がありません。
お礼
ありがとうございます。 以前に何処かで解法を読んだことがあり naniwacchi様とかなり似たアプローチで求めたのですが なぜ背反なのかがわかりませんでした。