のようになっていて、そこに別のまち針を刺すことができます。
この n 本のまち針全てを、直接的または間接的に針山に刺すことを考えます。
例えば、n=2 で、赤いまち針と青いまち針がある場合、
「両方を直接針山に刺す」
「赤を直接針山に刺し、青を赤の頭に刺す」
「青を直接針山に刺し、赤を青の頭に刺す」
の 3 通りの刺し方があります。
例えば、n=3 で赤青黄のまち針がある場合、
「赤と青を直接針山に刺し、黄は赤の頭に刺す」
「青を直接針山に刺し、赤と黄を両方とも青の頭に刺す」
「黄を直接針山に刺し、赤を黄の頭に、青を赤の頭に刺す」
などなど、全部で 16 通りの刺し方があります。
そこで、問題です。
(1) n=3 の残りの 13 通りを見つけてください。
(2) n=4 の場合、刺し方は 125 通りあります。全て見つけられるでしょうか。
(3) n=5 の場合、刺し方は何通りあるでしょう。
(4) n=6 や n=7 の場合はどうでしょう。
(5) 一般の n の場合に解けるでしょうか？
n=7 まではとても綺麗な結果になります。
n≧8 でも同じ法則が続くのならば、一般の n についてパッと解く方法がありそうですが、
私は今のところ発見できていません。
グラフ理論方面にヒントがありそうな気がする、というかモロにグラフ理論の範囲じゃない
かと思うのですが、うまく情報が見つけられません。
どなたか、情報をお持ちでしたらぜひ教えてください。
（注） 「目指せ！最長不倒」の関連問題です。
りらひいさんからのコメントです。（令和５年５月６日付け）
ｎ本の場合に刺し方がF(n)通りあるとする。ただし、n=0 の場合は、F(0)=1 とする。
まち針が n+1 本ある時を考える。
特定の1本のまち針[赤]に着目し、その先端側にあるまち針の本数を i 本、頭側にあるま
ち針の本数を n-i 本とする(0≦i≦n)。
ｎ本のまち針をこの２グループに分ける方法は、nCi 通り。
先端側にある i 本のまち針の刺し方は、F(i) 通りで、その各々に対し、まち針[赤]を刺す場
所が i+1 通り(針山と i 本のまち針の頭)。
頭側にある n-i 本のまち針の刺し方は、F(n-i) 通り
(まち針[赤]の頭を針山とみなせばよいため)。
よって、漸化式は、
F(n+1) = Σ[i=0...n] nCi * F(i) * (i+1) * F(n-i)
となる。F(n)の式の形は予想できているので、数学的帰納法で示せばよい。
……のですが、式変形できずに詰まっています。
DD++ さんからのコメントです。（令和５年５月６日付け）
そうなんですよ。
Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n
Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)
このどっちかが成り立ってくれれば話は終わりなんですが、「二項係数の性質」にもそれっ
ぽい式はないんですよね。
二項係数関係の総和は、底か指数かどちらか固定されていたら「よくある問題」なんですが、
両方変わっていくのはほとんど見たことがありません。
うんざりはちべえさんからのコメントです。（令和５年５月６日付け）
共立 数学公式 改定増補 昭和52年10月5日改増18刷 の ４．多項定理
４．１ 多項定理
ｎが正の整数なるとき、(a+b+・・・+f)^n=Σ{n!/(p!q!・・・t!)} a^p b^q ・・・f^t
ここに、Σはp+q+・・・+t=nなるすべての(p,q,・・・,t)の組についての和を表す。
４．２ ｎが正の整数なるときは、(a+bx+cx^2+・・)^n=Σ{n!/(p!q!r!・・)}a^p b^q c^r・・x^(q+2r+3s+・・）
ここに、Σはp+q+r+・・・=nなるすべての(p,q,r・・・)の組についての和を表す。
x^mの係数を求めるには、p+q+r+s+・・・=n,q+2r+3s+・・・=m を満足する(p,q,r,・・・)のすべて
の組を求め、その各々の組に対する和を取る。
４．３ m,nを正の整数として、(1+x+x^2+・・・+x^m)^n=a0+a1x+a2x^2+・・・+a(mn) x^(mn) とお
くと、
１．a0+a1+a2+・・・+a(mn)=(m+1)^n
２．a1+2a2+3a3+・・・+mna(mn)=(1/2)mn(m+1)^n
とあります。
４．３において、x=1とすると、１．が求められます。
(m+1)^n=ΣnCi m^(n-i)より、a^i=ΣnCi m^(n-i)
m=n+1を代入すると、１．より、(n+2)^nが求められます。
参考になりませんか・・・・・・
DD++ さんからのコメントです。（令和５年５月６日付け）
やっと情報を見つけました。こっちにある証明法がわかりやすかったので、この問題の用
語や数値に合わせながら翻訳します。
まず、針山もまち針とみなします。つまり、「針山をまち針の頭に刺す」が、なぜかできそう
な気分になっておきます。以下の操作を行います。
(1) n+1 本のまち針（本当は針山であるものも含む）を机上に並べます。
(2) n+1 個の頭から 1 つを選びます。そして、その頭とつながっておらず、かつどこにも刺し
ていない針先 n 個のうち 1 つを選びます。選んだ針先を選んだ頭に刺します。
(3) n+1 個の頭から 1 つを選びます。そして、その頭とつながっておらず、かつどこにも刺し
ていない針先 n-1 個のうち 1 つを選びます。選んだ針先を選んだ頭に刺します。
(4) さらに繰り返し、合計 n 回行います。選べる針先の選択肢が 1 つずつ減っていき、n 回
目では 1 個のうち 1 個を選んで刺すことになります。
(5) ある 1 本のまち針の頭に他の n 本が全部刺さっているオブジェ（木と呼びたいが根っこ
が刺さってない……）ができたら操作終了です。
各選択肢の個数を考えると、この操作の方法は全部で (n+1)^n * n! 通りあります。ただし、
同じ形のオブジェがまち針を刺す順番違いで n! 個ずつできるので、オブジェの種類は (n+1)^n
通りです。
そして、このオブジェには n+1 本の各まち針が一番下になるパターンが (n+1)^(n-1) 通りず
つ含まれます。つまり、まち針とみなしていた針山の上に本物のまち針 n 本が全部刺さって、
きちんと題意通りの形になっているパターンは (n+1)^(n-1) 通りとなります。
これで「最長数列の総数」も解決したことになります。あるいは、考え方を流用すれば、「ま
ち針の木」の問題に帰着させるまでもなくあっちを解けるかも。上手い説明ができるかどうか
考えてみます。
そして、次の恒等式の謎。
Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n
Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)
組み合わせを用いて証明できたことになりますが、式変形で示せるのかどうか。
ＧＡＩ さんからのコメントです。（令和５年５月６日付け）
[DD++さんの提示された関係式] Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n
について、
gp > for(n=1,10,print(n";",\
sum(k=0,n,binomial(n,k)*(k+1)^(k)*(n-k+1)^(n-k-1)), " VS ",(n+2)^(n)))
1;3 VS 3
2;16 VS 16
3;125 VS 125
4;1296 VS 1296
5;16807 VS 16807
6;262144 VS 262144
7;4782969 VS 4782969
8;100000000 VS 100000000
9;2357947691 VS 2357947691
10;61917364224 VS 61917364224
[DD++さんの提示された関係式] Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)
について、
gp > for(n=1,10,print(n";",\
sum(k=0,n,binomial(n,k)*(k+1)^(k-1)*(n-k+1)^(n-k-1)), " VS ",2*(n+2)^(n-1)))
1;2 VS 2
2;8 VS 8
3;50 VS 50
4;432 VS 432
5;4802 VS 4802
6;65536 VS 65536
7;1062882 VS 1062882
8;20000000 VS 20000000
9;428717762 VS 428717762
10;10319560704 VS 10319560704
[りらひいさんが提示された針刺し総数漸化式] F(n+1) = Σ[i=0...n] nCi * F(i) * (i+1) * F(n-i)
について
gp > F(n)=if(n<2,1,\
sum(i=0,n-1,binomial(n-1,i)*memorize(F,i)*(i+1)*memorize(F,n-i-1)));
gp > for(n=0,10,print(n+1";",F(n)," VS ",(n+1)^(n-1)))
1;1 VS 1
2;1 VS 1
3;3 VS 3
4;16 VS 16
5;125 VS 125
6;1296 VS 1296
7;16807 VS 16807
8;262144 VS 262144
9;4782969 VS 4782969
10;100000000 VS 100000000
11;2357947691 VS 2357947691
その他で似た等式を構成させたものを集めてみた。
gp > for(n=1,10,print(n";",\
sum(k=1,n,binomial(n-1,k-1)*k^(k-2)*(n-k)^(n-k)), " VS ",n^(n-1)))
1;1 VS 1
2;2 VS 2
3;9 VS 9
4;64 VS 64
5;625 VS 625
6;7776 VS 7776
7;117649 VS 117649
8;2097152 VS 2097152
9;43046721 VS 43046721
10;1000000000 VS 1000000000
gp > for(n=1,10,print(n";",\
-sum(k=1,n+1,(-1)^k*k*binomial(n+1,k)*(n+1)^(n-k)), " VS ",n^n))
1;1 VS 1
2;4 VS 4
3;27 VS 27
4;256 VS 256
5;3125 VS 3125
6;46656 VS 46656
7;823543 VS 823543
8;16777216 VS 16777216
9;387420489 VS 387420489
10;10000000000 VS 10000000000
gp > for(n=1,10,print(n";",\
sum(k=0,n,binomial(n,k)*Derange(k+1)*(n+1)^(n-k)), " VS ",n^(n+1)))
1;1 VS 1
2;8 VS 8
3;81 VS 81
4;1024 VS 1024
5;15625 VS 15625
6;279936 VS 279936
7;5764801 VS 5764801
8;134217728 VS 134217728
9;3486784401 VS 3486784401
10;100000000000 VS 100000000000
ここに、Derange(n)；1〜nの数字での完全順列の個数を示す。(derangement)
こんなにも似ても似つかぬものが同じ数列を構成するとは驚きです。
DD++ さんからのコメントです。（令和５年５月７日付け）
gp > for(n=1,10,print(n";",\
-sum(k=1,n+1,(-1)^k*k*binomial(n+1,k)*(n+1)^(n-k)), " VS ",n^n))
に関しては、{(n+1)-1}^n を二項展開した後少し変形しただけですかね。nCk を含む総和公
式は、「底が k に依存しない」場合は二項展開の式で変数の中身をうまく選んだ式あること
が多く、「指数が k に依存しない」場合は二項展開の式に何か掛けたり割ったりしながら微
積分を繰り返して作った式であることが多いです。
りらひいさんからのコメントです。（令和５年５月８日付け）
DD++さん、式変形できました。nCk を C[n,k] と書くことにします。
事前準備その１ C[n,i] * C[n-i,j] = C[n,j] * C[n-j,i]
（証明）
左辺＝ｎ！/｛（ｎ−ｉ）！ｉ！｝・（ｎ−ｉ）！/｛（ｎ−ｉ−ｊ）！ｊ！｝
＝ｎ！/｛（ｎ−ｊ）！ｊ！｝・（ｎ−ｊ）！/｛（ｎ−ｉ−ｊ）！ｉ！｝＝右辺 （証終）
事前準備その２ f(k)をkのn-1次以下の多項式として、
Σ[k=0...n] C[n,k] * (-1)^k * f(k) = 0
（証明は、「二項係数の性質」の中の性質(５)と(２８)
（５） ｎＣ0−ｎＣ1＋ｎＣ2−ｎＣ3＋・・・＋（−１）ｒｎＣｒ＋・・・＋（−１）ｎｎＣｎ＝０
（２８） １ｋｎＣ1−２ｋｎＣ2＋３ｋｎＣ3−・・・＋（−１）ｎ-1ｎｋｎＣｎ＝０ （ｋ＜ｎ）
１ｎｎＣ1−２ｎｎＣ2＋３ｎｎＣ3−・・・＋（−１）ｎ-1ｎｎｎＣｎ＝（−１）ｎ-1ｎ！
あるいは、平成２３年１１月１９日から２６日にかけてのらいさん・攻略法さん・ａｔ さん・ＦＮさん
のやりとり を参照）
（証明） それでは本番 (2行目から3行目の置き換えは、h=n-k)
Σ[h=0...n] C[n,h] * (h+1)^h * (n-h+1)^(n-h-1)
= Σ[h=0...n] C[n,n-h] * (n-h+1)^(n-h-1) * (h+1)^h
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * (n-k+1)^(n-k)
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * ((n+2)-(k+1))^(n-k)
= Σ[k=0...n] C[n,k]*(k+1)^(k-1)*{Σ[m=0...n-k] C[n-k,m]*(n+2)^m*(-1)^(n-k-m)*(k+1)^(n-k-m) }
= Σ[k=0...n] Σ[m=0...n-k] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= Σ[m=0...n] Σ[k=0...n-m] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1]Σ[k=0...n-m] C[n,k]*C[n-k,m]*(n+2)^m*(-1)^(n-k-m)*(k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1]Σ[k=0...n-m] C[n,m]*C[n-m,k]*(n+2)^m*(-1)^(n-m)*(-1)^k*(k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1]C[n,m]*(n+2)^m*(-1)^(n-m)*{Σ[k=0...n-m]C[n-m,k]*(-1)^k*(k+1)^(n-m-1) }
= (n+2)^n + Σ[m=0...n-1] C[n,m] * (n+2)^m * (-1)^(n-m) * 0
= (n+2)^n （証終）
DD++ さんからのコメントです。（令和５年５月９日付け）
おお、なるほど、そんな方法で k+1 の指数から k を消せるとは。これで、
Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n
Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)
の上の式は示されましたね。下の式は、りらひいさんの証明の 1 行目（ h をそのまま k に
書き換え）と 3 行目を足したものが最終結果の 2 倍になることから得られます。
これらの総和、いつかどこかでまた使うことがあるかもしれないので、証明方法ともども覚
えておきたいと思います。ありがとうございます。
りらひいさんからのコメントです。（令和５年５月１２日付け）
先日の式変形をもう一度眺めていて思ったのですが、次の式
(a+b)^n / a = Σ[k=0...n] C[n,k] * (a+k)^(k-1) * (b-k)^(n-k)
が成り立つんですね。ただし、 a≠0 とします。
計算は先日の3行目〜最終行とまったく同様です。先日の式は、 a=1、b=n+1 の場合にあ
たります。
a、b は、整数に限らず実数でいけるのが面白いところですね。
以下、工事中！
