◆東京都 かえる さんからの解答。
【問題３】
Ｎ段目における
(４，０，０，０)の個数をＡ(Ｎ)
(３，１，０，０)の個数をＢ(Ｎ)
(２，２，０，０)の個数をＣ(Ｎ)
(２，１，１，０)の個数をＤ(Ｎ)
(１，１，１，１)の個数をＥ(Ｎ)
とする。
Ｎ＋１段目においては、
Ａ(Ｎ＋１)＝Ａ(Ｎ)
Ｂ(Ｎ＋１)＝Ａ(Ｎ)＋Ｂ(Ｎ)
Ｃ(Ｎ＋１)＝Ａ(Ｎ)＋Ｃ(Ｎ)
Ｄ(Ｎ＋１)＝Ａ(Ｎ)＋Ｂ(Ｎ)＋Ｃ(Ｎ)＋Ｄ(Ｎ)
Ｅ(Ｎ＋１)＝Ａ(Ｎ)＋Ｂ(Ｎ)＋Ｃ(Ｎ)＋Ｄ(Ｎ)＋Ｅ(Ｎ)
Ａ(１)＝Ｂ(１)＝Ｃ(１)＝Ｄ(１)＝Ｅ(１)＝１に注意してこれを解けば、
Ａ(Ｎ)＝１
Ｂ(Ｎ)＝Ｎ
Ｃ(Ｎ)＝Ｎ
Ｄ(Ｎ)＝Ｎ2
| Ｅ(Ｎ)＝ | １ ６ |
Ｎ(Ｎ＋１)(２Ｎ＋１) |
| ＝ | １ ６ |
(Ｎ＋１)(Ｎ＋２)(２Ｎ＋３)・・・【答】 |
Ｐ(４，１)＝５・・・【答】
【問題２】
Ｐ(４，２)＝１４・・・【答】
【問題４】
【問題３】とほぼ同様にして、
| Ｐ(５，Ｎ)＝ | １ ４ |
(Ｎ＋１) | 2 | (Ｎ＋２) | 2 | ・・・【答】 |
【研究問題】
【問題３】とほぼ同様にして、
| Ｐ(Ｍ，Ｎ)＝ | N+1 k=1 |
ｋ | M-2 | ・・・【答】 |
【問題５】
【研究問題】により示された。・・・【答】
◆出題者の愛知県 Y.M.Ojisan さんからのコメント。
解答ありがとうございます。
問題１〜３ 正解です。
一方、M=5 N=1の場合を計算すると 問題４ 研究問題のご解答いずれも ９ が得られます。
しかし、この場合下記のごとく P(5,1)=7 です。
（５，０，０，０，０）（４，１，０，０，０）（３，２，０，０，０）
（３，１，１，０，０）（２，２，１，０，０）（２，１，１，１，０）
（１，１，１，１，１）
◆東京都 かえる さんからの解答。
【問題４】
【出題者の御指摘を踏まえ計算し直してみました。】
Ｎ段目における
（５，０，０，０，０）の個数をＡ(Ｎ)
（４，１，０，０，０）の個数をＢ(Ｎ)
（３，２，０，０，０）の個数をＣ(Ｎ)
（３，１，１，０，０）の個数をＤ(Ｎ)
（２，２，１，０，０）の個数をＥ(Ｎ)
（２，１，１，１，０）の個数をＦ(Ｎ）
（１，１，１，１，１）の個数をＧ(Ｎ）
とする。
Ｎ＋１段目においては、
Ａ(Ｎ＋１)＝Ａ(Ｎ)
Ｂ(Ｎ＋１)＝Ａ(Ｎ)＋Ｂ(Ｎ)
Ｃ(Ｎ＋１)＝Ａ(Ｎ)＋Ｃ(Ｎ)
Ｄ(Ｎ＋１)＝Ａ(Ｎ)＋Ｂ(Ｎ)＋Ｃ(Ｎ)＋Ｄ(Ｎ)
Ｅ(Ｎ＋１)＝Ａ(Ｎ)＋Ｂ(Ｎ)＋Ｃ(Ｎ)＋Ｅ(Ｎ)
Ｆ(Ｎ＋１)＝Ａ(Ｎ)＋Ｂ(Ｎ)＋Ｃ(Ｎ)＋Ｄ(Ｎ)＋Ｅ(Ｎ)＋Ｆ(Ｎ)
Ｇ(Ｎ＋１)＝Ａ(Ｎ)＋Ｂ(Ｎ)＋Ｃ(Ｎ)＋Ｄ(Ｎ)＋Ｅ(Ｎ)＋Ｆ(Ｎ)＋Ｇ(Ｎ)
Ａ(１)＝Ｂ(１)＝Ｃ(１)＝Ｄ(１)＝Ｅ(１)＝１に注意してこれを解けば、
Ａ(Ｎ)＝１
Ｂ(Ｎ)＝Ｎ
Ｃ(Ｎ)＝Ｎ
Ｄ(Ｎ)＝Ｎ2
Ｅ(Ｎ)＝Ｎ2
| Ｆ(Ｎ)＝ | １ ３ | Ｎ(２Ｎ | 2 | ＋１) |
| Ｇ(Ｎ)＝ | １ ６ | Ｎ(Ｎ＋１)(Ｎ | 2 | ＋Ｎ＋１) |
| ＝ | １ ６ | (Ｎ＋１)(Ｎ＋２)(Ｎ | 2 | ＋３Ｎ＋３)・・・【答】 |
１ １１ １０１ １１１１ １１１０１ １１１１１１ １１１１１０１ １１１１１１１１ １１１１１１１０１ ・ ・ ・ １１１１１１１１１１１１１ １１１１１１１１１１１１１１（特徴）
○ 左上から右下への対角線上は全て１
○ 左上から右下への対角線より上は全て０
○ 左上から右下への対角線より下は基本的に１
・ 但し、(３行目，２列目)、(５行目，４列目)，(７行目，６列目)・・・は０
・ 左上から右下への対角線より下の部分のうち、下２行は１
◆出題者の愛知県 Y.M.Ojisan さんからのコメント。
残念ながら 下記であるので Ｆ(N+1)の段のＣ(N)の係数は２です。
(3,2,0,0,0)→((2,1),(1,1),(0),(0),(0))
(3,2,0,0,0)→((1,1,1),(2),(0),(0),(0))
さらに同種別の難しい不備があります。
◆滋賀県の高校生 -25-@ucchie さんからの解答。
かえるさんの解法を参考にさせていただきました。
【問題４】
N段目における
(5,0,0,0,0)の個数をA(N) (4,1,0,0,0)の個数をB(N) (3,2,0,0,0)の個数をC(N) (3,1,1,0,0)の個数をD(N) (2,2,1,0,0)の個数をE(N) (2,1,1,1,0)の個数をF(N） (1,1,1,1,1)の個数をG(N）とします。
----------------------------------[補足]--------------------------------
ここで,自然数nを幾つかの自然数の和で表す場合の数をR(n)とすると、
==============
例)R(5)は、以下のようにしてR(5)=7
5
=4+1
=3+2
=3+1+1
=2+2+1
=2+1+1+1
=1+1+1+1+1
・R(k)(k=1,2,3,4,5,…)を求めると
R(1)=1
R(2)=2
R(3)=3
R(4)=5
R(5)=7
…
==============
ここで,R(N)を利用すると、
K(N)(K=A,B,…,G)から、L(N+1)(L=A,B,…,G)を作れる総数は,…(*)
K(N)が含む数字についてのRの積で示せます(重複は除く)。
例えば、
・C(N)からは,
R(3)×R(2)=6(通り)
(3,2は互いに独立しているので)
・E(N)からは,
R(2)H2(H:重複組み合わせ)×R(1)＝3C2×1=3(通り)
----------------------------------------
(*)の文章がうまく書けないのですが、
C(N):(3,2,0,0,0)からは、
C(N+1):(3,2,0,0,0)
D(N+1):(3,1+1,0,0,0)
E(N+1):(2+1,2,0,0,0)
F(N+1):(2+1,1+1,0,0,0),(1+1+1,2,0,0,0)
G(N+1):(1+1+1,1+1,0,0,0)
の合計6通り、新たに作れるという事です。
-----------------------------------------
このように考えると、全ての場合について把握する事ができます
---------------------------------[補足終]-------------------------------
以上のことを踏まえると(実際に調べると)
N+1段目においては、
A(N+1)=A(N)
B(N+1)=A(N)+B(N)
C(N+1)=A(N)+C(N)
D(N+1)=A(N)+B(N)+C(N)+D(N)
E(N+1)=A(N)+B(N)+C(N)+E(N)
F(N+1)=A(N)+B(N)+2C(N)+D(N)+E(N)+F(N)
G(N+1)=A(N)+B(N)+C(N)+D(N)+E(N)+F(N)+G(N)
A(1)=B(1)=C(1)=D(1)=E(1)=F(1)=G(1)=1より、
A(N)〜G(N)を求めると
[A(N)~E(N)は計算略]
A(N)=1
B(N)=N
C(N)=N
D(N)=N2
E(N)=N2
F(N)
| =1+ | N-1 k=1 |
{A(N)+B(N)+2C(N)+D(N)+E(N)} |
| = | N(N+1)(4N-1) 6 |
G(N)
| =1+ | N-1 k=1 |
{A(N)+B(N)+C(N)+D(N)+E(N)+F(N)} |
| = | N(N3+3N2-N+3) 6 |
よって以上から、
P(5,N)
=A(N)+B(N)+C(N)+D(N)+E(N)+F(N)+G(N)
=G(N+1)
| = | (N+1)(N3+6N2+8N+6) 6 |
| ∴ P(5,N)= | (N+1)(N3+6N2+8N+6) 6 |
【問題５(考察)】
(以下【問題４】の例)
--------------------------------
(5,0,0,0,0)の個数:A(N)⇒Nの0次式(Mがどんな値を取ろうが定数1)
(4,1,0,0,0)の個数:B(N)⇒Nの1次多項式
(3,2,0,0,0)の個数:C(N)⇒Nの1次多項式
(3,1,1,0,0)の個数:D(N)⇒Nの2次多項式
(2,2,1,0,0)の個数:E(N)⇒Nの2次多項式
(2,1,1,1,0)の個数:F(N)⇒Nの3次多項式
(1,1,1,1,1)の個数:G(N)⇒Nの4次多項式
--------------------------------
(証明)
使用数字数がn個(1≦n≦M)である組み合わせについてはT<n>(N)で示す事にします。
(厳密には全て区別するべきですが簡単にするために全て同じとします)
上の例では、
A(N)=T<1>(N),B(N)=C(N)=T<2>(N)ということです。
以下nの値で場合分けをする。
(i)n=1のとき
T<1>(N)＝1(0次式)
(任意のMについて成り立ちます)
(ii)1≦n≦Mのとき
-------------[補足]----------------
以下の乃<n>(N)は条件を満たすT<n>(N)について,
nの値ごとにまとめたもので,あるnについての全てのT<n>(N)の和を示すものではないとします。
例えば、ある組み合わせT<3>が(2,2,2,0,0,0)なら,
T<3>(N+1)=T<1>(N)+乃<2>(N)+T<3>(N)
と書きますが、
T<2>:(4,2,0,0,0,0)についての総数は含んでも
T<2>:(5,1,0,0,0,0)についての総数は含みません。
-----------------------------------
ある１つのT<n>(N+1)を求める際の以下の計算を考えると、
(nつの数字で構成された"ある組み合わせ"は、
nつ未満の数字で構成された組み合わせ、
もしくはnつの数字で構成された"ある組み合わせ"そのものからしか作れないので)
| T<n>(N+1)=T<1>(N)+乃<2>(N)+乃<3>(N)+…+乃<n-1>(N)+T<n>(N) |
| ⇔T<n>(N+1)-T2(N)=T<1>(N)+乃<2>(N)+乃<3>(N)+…+乃<n-1>(N) |
| ⇔T<n>(N)=1+ | N-1 k=1 |
(1+乃<2>(k)+乃<3>(k)+…乃<n-1>(k)) …(1) |
より、T<n>(N)のNの最高次数は、右辺のNの最高次数に一致することがわかる。
ここで(1)式について、
・n=2のとき,(i)を利用して
T<2>(N)=1+N-1=N(Nの1次式)
・(1)式についてnの値を1ずつ増やしていくと(狽ﾍ次数を1つ上げるので)、
T<3>(N)=(Nの2次多項式)
…
T<M>(N)=(NのM-1次多項式)
ここで、P(M,N)＝T<M>(N+1)であるから
P(M,N)はNのM−1次多項式である
(証明終)
【コメント】
理解しずらい解答の上、曖昧すぎて申し訳ありません。
◆出題者の愛知県 Y.M.Ojisan さんからのコメント。
-25-@ucchie さん解答ありがとうございます。
問題５はＯＫです。
問題４は前のコメントの後半がケアされておらず不正解です。
具体的には (2,2,1,0,0) ないし((2,2),1,0,0,0)の組 と (2,(2,1),0,0,0) において 2と2が前者では区別なく、後者では区別があるので数え方が２倍異なります。
従ってＥ（Ｎ）ひとつに纏めるのではうまくゆきません。
かえるさんの方法も立派な解法ですが、上記のように煩雑で混乱します。
別のアプローチをお勧めします。
◆滋賀県の高校生 -25-@ucchie さんからの解答。
ヒントをいただいて，再びですが，かえるさんの方法で解いた答えが以下の通りです。
(計算略)
【問題４】
| P(5,N)= | (N+1)(N+2)(5N2+11N+12) 24 |
今後は別のアプローチで解けるよう頑張ります。
【研究問題】(計算略)
P(1,N)=1
P(2,N)=N+1
| P(3,N)= | (N+1)(N+2) 2 |
| P(4,N)= | (N+1)(N+2)(2N+3) 6 |
| P(5,N)= | (N+1)(N+2)(5N2+11N+12) 24 |
| P(6,N)= | (N+1)(N+2)(4N3+13N2+23N+15) 30 |
| P(M,N)= | (N+1)(N+2)(NのM-3次多項式) (M-1)! |
の形で示せる(？) |
まだ漸化式の利用が拭い切れず、P(6,N)を更に求めました。
P(5,N)とP(6,N)，正解であってほしいです...
とても興味深い問題なので色々な解法を探したいです。
◆出題者の愛知県 Y.M.Ojisan さんからのコメント。
（１）P(5,N)とP(6,N)，正解です。
（２）気がつきませんでしたが （Ｎ＋１）（Ｎ＋２）でくくれるのも正しい予想です。
正攻法で攻めれば証明できますが、なにか快刀乱麻の解釈を期待します。
◆宮城県 甘泉法師 さんからの解答。
【問題１】
p(n,r):自然数ｎをｒ個に分けた時の分け方の個数
p(n,1)＝１
p(n,n)＝１
p(n,r)＝０ n＜r
p(n,r)＝p(n-r,r) + p(n-1,r-1)
右辺第一項は、1個入っている箱がない場合の数
右辺第二項は、1個入っている箱がある場合の数
入る個数に０を許す場合の数v(n,r)は玉の数をｒ個ふやし、配分後に箱からひとつづつ玉を取り去るとかんがえて
v(n,r)=p(n+r,r)=p(n,r)＋p(n+r-1,r-1)
P(M,1)=v(M,M)
P(4,1)
=v(4,4)
=p(4,4)＋p(7,3)
={p(3,3)+p(0,3)} + {p(6,2)+p(4,3)}
=1 + p(5,1) + p(4,2) + p(3,2) + p(1,3)
=1 + 1 + p(3,1) + p(2,2) + p(2,1) + p(1,2)
=5
【問題２】
玉をｎ個、箱、袋の数をｒとして
| Σ {mi} |
n Π i=0 | v(i,r) H mi ≡ v(2;n,r) |
| Σ {mi} |
n Σ i=0 | mi*i = n を満たす異なる組{mi}についての和 |
(3,0,0,0,1):1 H 3 * 5 H 1 = 5
(2,1,0,1,0):1 H 2 * 1 H 1 * 3 H 1= 1*1*3 = 3
(2,0,2,0,0):1 H 2 * 2 H 2 = 1*3 = 3
(1,2,1,0,0):1 H 1 * 1 H 2* 2 H 1 = 1*1*2 = 2
+ (0,4,0,0,0):1 H 4 = 1
------------------------------------------------
14
【研究問題】玉をｎ個、 箱、袋、小袋、小小袋、...の数をｒとして
| Σ {mi} |
n Π i=0 | v(j;i,r) H mi ≡ v(j+1;n,r) |
| Σ {mi} |
n Σ i=0 | mi*i = n を満たす異なる組{mi}についての和 |
◆出題者の愛知県 Y.M.Ojisan さんからのコメント。
甘泉法師 さん 正解です。
ｐの素性に言及しないのなら、
ｐを経由せず直接 ｖ(n,r)＝ｖ(n-r,r) + ｖ(n,r-1) でよいでしょう。
ｐおよびそのパターンである｛ｍi｝を一般的に表すことは未解決問題であり、ご解答にあるように
「。。。を満たす異なる組{mi}について。。」と記述せざるをえません。
逆に本問題の困難さをすべてここに集約することで、ご解答にあるような単純な手続きにすることが可能です。
現実の問題は大抵の場合完全に解くことが出来ず、一部に実験が必要です。
このとき無数のアプローチがあり得ますが、実験規模を最小にする最適なアプローチを選択することが肝要で、その例題といえるでしょう。