まち針の木
区別がつく n 本のまち針と、1 個の針山があります。
このまち針は、自身の頭がまた針山のようになっていて、そこに別のまち針を刺すことができます。
この 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 についてパッと解く方法がありそうですが、私は今のところ発見できていません。
グラフ理論方面にヒントがありそうな気がする、というかモロにグラフ理論の範囲じゃないかと思うのですが、うまく情報が見つけられません。
どなたか、情報をお持ちでしたらぜひ教えてください。
n本の場合に刺し方がF(n)通りあるとする。
ただし、n=0の場合はF(0)=1とする。
まち針がn+1本ある時を考える。
特定の1本のまち針[赤]に着目し、その先端側にあるまち針の本数をi本、頭側にあるまち針の本数をn-i本とする(0≦i≦n)。
n本のまち針をこの2グループに分ける方法はCombination(n,i)通り。
先端側にあるi本のまち針の刺し方はF(i)通りで、その各々に対しまち針[赤]を刺す場所がi+1通り(針山とi本のまち針の頭)。
頭側にあるn-i本のまち針の刺し方はF(n-i)通り(まち針[赤]の頭を針山とみなせばよいため)。
よって漸化式は、
F(n+1) = Σ[i=0...n] Combination(n,i) * F(i) * (i+1) * F(n-i)
となる。
F(n)の式の形は予想できているので数学的帰納法で示せばよい。
……のですが、式変形できずに詰まっています。
そうなんですよ。
Σ[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)
このどっちかが成り立ってくれれば話は終わりなんですけど、
「私の備忘録」->「代数学分野」->「二項係数の性質」
にもそれっぽい式はないんですよね。
二項係数関係の総和は、底か指数かどちらか固定されていたら「よくある問題」なんですが、両方変わっていくのはほとんど見たことがありません。
どれが積でどれが添字か全くわからないので、添字は [ ] で書くなど区別しやすい表記にしてもらうことはできますか？
やっと情報を見つけました。
https://en.m.wikipedia.org/wiki/Cayley%27s_formula
こっちにある証明法がわかりやすかったので、この問題の用語や数値に合わせながら翻訳します。
https://en.m.wikipedia.org/wiki/Double_counting_(proof_technique)
まず、針山もまち針とみなします。
つまり「針山をまち針の頭に刺す」が、なぜかできそうな気分になっておきます。
以下の操作を行います。
(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) 通りとなります。
これで「最長数列の総数」も解決したことになります。
あるいは、考え方を流用すれば「まち針の木」の問題に帰着させるまでもなくあっちを解けるかも。
上手い説明ができるかどうか考えてみます。
そして残った No.1051 の恒等式の謎。
組み合わせを用いて証明できたことになりますが、式変形で示せるのかどうか。
DD++さん
> そして残った No.1051 の恒等式の謎。
> 組み合わせを用いて証明できたことになりますが、式変形で示せるのかどうか。
式変形できました。
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
（証明は、「私の備忘録」->「代数学分野」->「二項係数の性質」の中の性質(5)と(28)、あるいは
平成２３年１１月１９日から２６日にかけてのらいさん・攻略法さん・ａｔ さん・ＦＮさんのやりとり を参照）
それでは本番 (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
おお、なるほど、そんな方法で 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 倍になることから得られます。
これらの総和、いつかどこかでまた使うことがあるかもしれないので、証明方法ともども覚えておきたいと思います。
ありがとうございます。
先日の式変形（No.1068）をもう一度眺めていて思ったのですが、次の式
(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は整数に限らず実数でいけるのが面白いところですね。
