2項係数の1項間漸化式

by nomura · 2020年7月14日

2項係数は以下の1項間漸化式を満たす。

(1)

\[ C(x+1,y)=\frac{x+1}{x+1-y}C(x,y) \]

(2)

\[ C(x-1,y)=\frac{x-y}{x}C(x,y) \]

(3)

\[ C(x,y+1)=\frac{x-y}{y+1}C(x,y) \]

(4)

\[ C(x,y-1)=\frac{y}{x-y+1}C(x,y) \]

(5)

\[ C(x+1,y+1)=\frac{x+1}{y+1}C(x,y) \]

(6)

\[ C(x+1,y-1)=\frac{(x+1)y}{(x-y+1)(x-y+2)}C(x,y) \]

(7)

\[ C(x-1,y+1)=\frac{(x-y-1)(x-y)}{x(y+1)}C(x,y) \]

(8)

\[ C(x-1,y-1)=\frac{y}{x}C(x,y) \]

(1)

\begin{align*} C(x+1,y) & =\frac{(x+1)!}{y!(x+1-y)!}\\ & =\frac{x+1}{x+1-y}\frac{x!}{y!(x-y)!}\\ & =\frac{x+1}{x+1-y}C(x,y) \end{align*}

(2)

\begin{align*} C(x-1,y) & =\frac{(x-1)!}{y!(x-1-y)!}\\ & =\frac{x-y}{x}\frac{x!}{y!(x-y)!}\\ & =\frac{x-y}{x}C(x,y) \end{align*}

(3)

\begin{align*} C(x,y+1) & =\frac{x!}{(y+1)!(x-y-1)!}\\ & =\frac{x-y}{y+1}\frac{x!}{y!(x-y)!}\\ & =\frac{x-y}{y+1}C(x,y) \end{align*}

(4)

\begin{align*} C(x,y-1) & =\frac{x!}{(y-1)!(x-y+1)!}\\ & =\frac{y}{x-y+1}\frac{x!}{y!(x-y)!}\\ & =\frac{y}{x-y+1}C(x,y) \end{align*}

(5)

\begin{align*} C(x+1,y+1) & =\frac{(x+1)!}{(y+1)!(x-y)!}\\ & =\frac{x+1}{y+1}\frac{x!}{y!(x-y)!}\\ & =\frac{x+1}{y+1}C(x,y) \end{align*}

(6)

\begin{align*} C(x+1,y-1) & =\frac{(x+1)!}{(y-1)!(x-y+2)!}\\ & =\frac{(x+1)y}{(x-y+1)(x-y+2)}\frac{x!}{y!(x-y)!}\\ & =\frac{(x+1)y}{(x-y+1)(x-y+2)}C(x,y) \end{align*}

(7)

\begin{align*} C(x-1,y+1) & =\frac{(x-1)!}{(y+1)!(x-y-2)!}\\ & =\frac{(x-y-1)(x-y)}{x(y+1)}\frac{x!}{y!(x-y)!}\\ & =\frac{(x-y-1)(x-y)}{x(y+1)}C(x,y) \end{align*}

(8)

\begin{align*} C(x-1,y-1) & =\frac{(x-1)!}{(y-1)!(x-y)!}\\ & =\frac{y}{x}\frac{x!}{y!(x-y)!}\\ & =\frac{y}{x}C(x,y) \end{align*}