ホーム >> 組合せ >> 下位の桁よりも数字が大きい自然数の個数
hide or visible

問題の説明

十進法表記で考えてください.($1$) の条件は,$0$ となる桁がないということです.
($2$) の条件は,右にいくにつれて桁の数が小さくなっていくということです.

場合分けをすれば基本的な組合せの知識で解けますが,実は,発想の転換によって,エレガントに解くことができます.

ヒント

まずは桁数について考えてみましょう.どのような桁の数が条件を満たすでしょうか.同じ数が $2$ 度現れるような数は条件 $(2)$ を満たさないことに注意してください.

エレガントな解答

まず,$987654321$ という数を考えます.この数は $2$ 条件を満たしています.つぎに,この自然数から幾つかの数を消去して得られる自然数を考えます.たとえば,$2,3,5$ を消去すると,$987641$ が得られます,$9,8,7,6,5,2,1$ を消去すると,$743$ が得られます.このようにして得られた数たちは,また $2$ 条件を満たしています.特に,$987654321$ からいくつかの数を消去して得られる数たちと,$2$ 条件を満たす数たちは一対一に対応します.

したがって,$987654321$ から数を消す方法を考えれば良いです.ある数について,それを消去するかしないかの $2$ 通りが考えられることと,すべての数を消去してはいけないことを考慮すると,消去する方法の総数は, $$2^9-1=511$$ よって,$511$ 通りです.

別解

桁数で場合分けして解くこともできます.
求める自然数の桁数は $1$ 以上 $9$ 以下です.自然数 $k\ (1\le k \le 9)$ について,$1,2,3,4,5,6,7,8,9$ から $k$ 個の異なる数字を選ぶ方法は ${}_9 \mathrm{C} _{k}$ 通りあります.選んだ $k$ 個の数について,条件 ($2$) を満たすような並べかたは $1$ 通りしかありません.(大きい順に並べるしかない) つまり,条件を満たす $k$ 桁の自然数の総数は,${}_9 \mathrm{C} _k$ です.よって,求めるべき数は $$\sum_{k=1}^9 {}_9 \mathrm{C} _k=(1+1)^9-1=511$$ です.ここで,最初の等号は二項定理を用いています.