二項係数の恒等式

久しぶりの記事です.受験勉強から逃避したくて式をコネコネしていたところ,非自明な恒等式が得られたので解説します.行間広めなのはご容赦ください.

得られた恒等式

総和の範囲にガウス記号が入っていたりする点など,ビジュアル点は高いですね.

導出

$2n$次多項式$f(x)=(x^2+x+1)^n$の$x^m$の係数を$2$通りの方法で計算します.
(i)1通り目.$x^2+x+1=\dfrac{1-x^3}{1-x}$より,$f(x)=\dfrac{(1-x^3)^n}{(1-x)^n}$と変形出来ます.
負の二項定理より,$\dfrac{1}{(1-x)^n}=\displaystyle\sum_{j=0}^{\infty}\binom{n+j-1}{j}x^{j}$であることを踏まえると,$k=0,1,\ldots,\lfloor\dfrac{m}{3}\rfloor$について$[x^{3k}](1-x^3)^n×[x^{m-3k}]\dfrac{1}{(1-x)^n}$の総和をとることで$[x^m]f(x)=\displaystyle\sum_{k=0}^{\lfloor\dfrac{m}{3}\rfloor}\binom{n}{k}\binom{n+m-3k-1}{n-1}(-1)^{k}$が得られます.
(ii)2通り目.$x^2+x+1=(x+1)^2-x$より,$f(x)=\{(x+1)^2-x\}^{n}$と変形出来るので,二項定理より$f(x)=\displaystyle\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}x^i(x+1)^{2n-2i}$.よって$[x^m]f(x)=\displaystyle\sum_{i=0}^{m}\binom{n}{i}\binom{2n-2i}{m-i}(-1)^i$が得られます.
(i),(ii)より目標の恒等式が得られました(やったね！).

深掘りしたい(途中段階)

二項係数関連の恒等式は組合せ論的な解釈が付き物ですが,今回扱った恒等式を組合せ論的な解釈によって証明することは可能でしょうか？母関数を用いた導出からも分かる通り,両辺はそれぞれ${0,1,2}$を要素に持ち,要素の和が$m$で長さが$n$の列の総数と一致します.少し考察してみたところ,左辺について次のような組合せ論的な解釈が得られたので紹介します.

得られた考察

任意の$i$について$a_i\in\{0,1,2\}$であるような長さ$n$の列$(a_1,a_2,\ldots,a_n)$ で$\displaystyle\sum_{s=1}^{n}a_s=m$であるものの個数を数え上げることを考える.

非負整数を要素に持つ長さ$n$の数列で和が$m$であるもの全体の集合を$A$,$1≦i≦n$について,$A$の部分集合で各元が$a_i≧3$を満たすもの全体の集合を$A_i$と定めます.このとき,条件を満たす数列の個数は$|A|-|A_1\cup A_2\cup\ldots\cup A_n|$であり,重複順列の性質から$|A|=\binom{n+m-1}{n-1}$,包除原理を用いて計算すると$|A_1\cup A_2\cup\ldots\cup A_n|=\displaystyle\sum_{k=1}^{\lfloor\dfrac{m}{3}\rfloor}\binom{n}{k}\binom{n+m-3k-1}{n-1}(-1)^{k-1}$なので,整理することで$\displaystyle\sum_{k=0}^{\lfloor\dfrac{m}{3}\rfloor}\binom{n}{k}\binom{n+m-3k-1}{n-1}(-1)^{k}$が条件を満たす数列の個数だと分かる.

右辺の組合せ論的な解釈が現時点では得られていないので,もし発見した方は私のX(@Uirou_math)のDM等に連絡ください...！

追記

noshi91氏(@noshi91)とMARTH氏(@MARTH_math)から右辺の組合せ論的な解釈について同様の解法を教えていただいたので追記します.
$b_i,c_i\in\{0,1\}$である長さ$n$の数列$b,c$で$a_i=b_i+c_i$を満たすものを考える.$b,c$の組としてあり得るもの全体の集合を$X$,$X$の部分集合で各元が$ (b_i,c_i)=(0,1)$を満たすもの全体の集合を$X_i$とすると,数列$a$の個数は$|A|-|A_1\cup A_2\cup \ldots \cup A_n|$であり、包除原理の要領で計算すると右辺に一致する.

終わりに

最後までお読みいただきありがとうございました.