第3問

A(n)

を、

a_1+\cdots+a_k=n

かつ各

a_i+1

（

i=1,2,\ldots,k

）が二のべきであるような正整数の数列

a_1\ge a_2\ge\cdots\ge a_k

の個数とする。

B(n)

を、

b_1+\cdots+b_m=n

かつ各不等式

b_j\ge2b_{j+1}

（

j=1,2,\ldots,m-1

）が成り立つような正整数の数列

b_1\ge b_2\ge\cdots\ge b_m

の個数とする。すべての正整数

n

に対して

A(n)=B(n)

であることを証明せよ。

ステップ 4/4: 全単射を結論する

前のステップ次のステップ

A(n)=B(n)

詳しい解説

行和写像（型 $A$ から型 $B$ へ、行から作った配列の列和を読み取ることによる）と列和写像（型 $B$ から型 $A$ へ、列から作った見事な配列の行和を読み取ることによる）は互いに逆写像である。なぜなら見事な配列はその行和からも列和からも一意に復元できるからである。したがってこれらの写像は、和が $n$ になる型 $A$ の数列と和が $n$ になる型 $B$ の数列の間の全単射を与え、すべての正整数 $n$ に対して $A(n)=B(n)$ である。