[過去ﾛｸﾞ] 分からない問題はここに書いてね458 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
454(3): １３２人目の素数さん [] 2020/03/06(金) 00:33:45.60 ID:GqTLR56E(1/6) AAS
nは6の倍数とする
1≦t<u<vかつt+u+v＝nとなる整数t,u,vの組合せは何通りあるか
よろしくお願いします
455: １３２人目の素数さん [sage] 2020/03/06(金) 00:50:42.32 ID:n77wXyP9(1) AAS
>>454
#{ u+v+w=n } = (n+2)(n+1)/2
#{ u+v+w=n ,u=v} = n/2+1
#{ u+v+w=n ,u=v=w} = n/3+1
∴#{orbits} = ((n+2)(n+1)/2 + 3(n/2+1) + 2(n/3+1))/6
463(1): １３２人目の素数さん [] 2020/03/06(金) 14:42:33.91 ID:kLdlq8Gi(4/20) AAS
>>454
t + u + v = n
となるような 0 以上の整数の組 (t, u, v) の個数をまず求める。
補題：
k を 0 以上の整数とする。
x + y = k
となるような 0 以上の整数の組 (x, y) は、 k + 1 個ある。
証明：
全ての解を並べると、 (0, k), (1, k - 1), …, (k, 0) だから、解は全部で k + 1 個ある。
t = 0 のとき、 u + v = n - t = n + 0 = n となるような 0 以上の整数の組 (u, v) の数は、
補題より、 n + 1 個ある。
t = 1 のとき、 u + v = n - t = n - 1 となるような 0 以上の整数の組 (u, v) の数は、
補題より、 n 個ある。
t = 2 のとき、 u + v = n - t = n - 2 となるような 0 以上の整数の組 (u, v) の数は、
補題より、 n - 1 個ある。
…
t = n のとき、 u + v = n - t = n - n = 0 となるような 0 以上の整数の組 (u, v) の数は、
補題より、 1 個ある。
∴
t + u + v = n
となるような 0 以上の整数の組 (t, u, v) の個数は、 (n + 1) + (n) + (n - 1) + … + 1 = (n + 1) * (n + 2) / 2 個である。
503(2): １３２人目の素数さん [sage] 2020/03/07(土) 10:33:24.26 ID:bfEFgg5v(1) AAS
>>454
1≦t<u<v, t+u+v=n,
を満たす (t,u,v) が q(n) とおりある、とする。
t>1 の場合は
(t-1,u-1,v-1) は 1≦ t-1 < u-1 < v-1 を満たし、和が n-3 となる。
q(n-3) に等しい。
t=1 の場合は
(u-1,v-1) は 1≦ u-1 < v-1 を満たし、和が n-3 となる。
[(n-4)/2] = [n/2] -2 とおりある。
これらをたすと漸化式
q(n) = q(n-3) + [n/2] - 2,
初期値 q(6) = 1,
n が3の倍数のときは
q(n) = (nn/12) - (n/2) + 1 - (1/4)mod(n,2),
一般には
q(n) = (nn/12) - (n/2) + 1 - (1/4)mod(n,2) - (1/3)d(n),
ここに
mod(n,2) = n - 2[n/2],
d(n) = 0 (nが3の倍数), = 1 (その他)
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.038s