6.2.18

$$S = \binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2$$とする。 これは$$\{1,2,\ldots,n\}$$から$$k$$個の数字を取ることを2回 (1回目と2回目で選ぶ数字には制約はない)繰り返す場合の数の総和である。

これを上手く符号化する。 今集合$$\{1,2,\ldots,n,n+1,\ldots,2n\}$$から$$n$$個数字を選ぶ。 ある選び方に対して数字が選ばれたときは"y", 選ばれなかったときは"n"として符号化する。 例えば$$n=5$$で$$\{1,2,3,4,7\}$$を選んだときは"yyyyn nynnn"となる。 このとき、$$n$$以下の数字が$$k$$個選ばれるとき、$$n+1$$以上の数字は選ばれないものがちょうど$$k$$個あることに注意しよう。 そこで次のようにしてこの符号化と最初の問題のある1つの場合に1対1に対応させる。

符号化された文字列$$c_1c_2\cdots c_n c_{n+1}\cdots c_{2n}$$に対して、 1回目は$$i=1,\ldots,n$$で$$c_i$$が"y"のものを選ぶ。 2回目は$$i=1,\ldots,n$$で$$c_{n+i}$$が"n"のものを選ぶ。

以上より$$S$$は"y"が$$n$$個、"n"が$$n$$個からなる長さ$$2n$$の文字列の総数と等しくなる。 これはミシシッピの公式から$$\frac{2n!}{n!n!} = \binom{2n}{n}$$であるため、 $$S=\binom{2n}{n}$$を得る。

(cf. 4.3.8)