問題4638・・・算チャレ掲示板にてあみーさん提示問を適当にアレンジしました... Orz〜
1~7番までの番号のついた箱がある。
ここに、1~7の番号札を入れることを考える。
箱の番号と一致するか、差が２までの入れ方で１箱に１枚のカードの入れ方は何通り？
解答
上記サイト掲示板より Orz〜
・わたしの
途中までは出せるんだけど...f(7) の計算の方法が急にわからなくなったり...^^;;...?
f(1)=1
f(2)=2
f(3)=3!=6
f(4)=f(2)^2+2*f(3)-2=14
f(5)=f(2)^2+f(3)+2*f(2)*f(3)-3=31
f(6)=f(3)^2+f(2)^2+f(4)+2*f(3)*f(2)-5=73
f(7)=???
1,2,6,14,31,73,172,400,...ってな数列になるようですね...^^;...v
オンライン整数列大事典 より...
A002524Number of permutations of length n within distance 2 of a fixed permutation.
(Formerly M1600 N0626)
・uchinyanさんのもの Orz〜
|
確かに面倒にはなりますが，漸化式は割と容易に作れますね。
カード 1 〜 n，箱 1 〜 n として，カード i を箱 j に入れるのを i -> j などと書き，
n -> n を a(n) 通り，n -> n-1 を b(n) 通り，n -> n-2 を c(n) 通り，全体を s(n) 通り，とすれば，
a(n) = (n->n) = s(n-1)
b(n) = (n->n-1, n-1->n) + (n->n-1, n-2->n) = s(n-2) + (s(n-2) - c(n-2)) = 2 * s(n-2) - c(n-2)
c(n) = (n->n-2, n-1->n, n-2->n-1) + (n->n-2, n-1->n, n-3->n-1) + (n->n-2, n-2->n, n-1->n-1) + (n->n-2, n-2->n, n-3->n-1)
= s(n-3) + (s(n-3) - c(n-3)) + s(n-3) + s(n-4) = 3 * s(n-3) + s(n-4) - c(n-3)
s(n) = a(n) + b(n) + c(n)
ただし，
a(1) = 1, b(1) = 0, c(1) = 0, s(1) = 1
a(2) = 1, b(2) = 1, c(2) = 0, s(2) = 2
a(3) = 2, b(3) = 2, c(3) = 2, s(3) = 6
a(4) = 6, b(4) = 4, c(4) = 4, s(4) = 14
です。ここまでは，一部漸化式を使いながらも，結局は，地道に数えます。後は上記の漸化式で，
a(5) = 14, b(5) = 10, c(5) = 7, s(5) = 31
a(6) = 31, b(6) = 24, c(6) = 18, s(6) = 73
a(7) = 73, b(7) = 55, c(7) = 44, s(7) = 172
a(8) = 172, b(8) = 128, c(8) = 100, s(8) = 400
a(9) = 400, b(9) = 300, c(9) = 232, s(9) = 932
a(10) = 932, b(10) = 700, c(10) = 545, s(10) = 2177
a(11) = 2177, b(11) = 1632, c(11) = 1272, s(11) = 5081
a(12) = 5081, b(12) = 3809, c(12) = 2964, s(12) = 11854
a(13) = 11854, b(13) = 8890, c(13) = 6918, s(13) = 27662
a(14) = 27662, b(14) = 20744, c(14) = 16148, s(14) = 64554
a(15) = 64554, b(15) = 48406, c(15) = 37679, s(15) = 150639
．．．
なお，差が m の場合も考えたくなりますが，一般にこの方で解くのはかなり難しそうです。 | |
*理解するのが大変なわたし...^^;...Orz〜
|
コメント（0）
