問題
次の条件を満たす正の整数全体の集合をとおく。
「各けたの数字はたがいに異なり，どの2つのけたの数字の和も9にならない。」
ただし，の要素は10進法で表す。また，1けたの正の整数はに含まれるとする。このとき次の問いに答えよ。
(1) の要素でちょうど4けたのものは何個あるか。
(2) 小さい方から数えて2000番目のの要素を求めよ。
方針
和が9になる数字の組 に分けると、条件は各組から高々1個の数字を使うことになる。 けたの個数は、使用する組を選び、各組から数字を1つ選び、並べる。ただし先頭が のものを除く。(2)では1けたから3けたまでの総数を引き、4けたの中で何番目かを求め、千の位、百の位、十の位の順にブロック数で絞り込む。
解答
(1)
2つの数字の和が9になる組は である。条件は、これら5組の各組から高々1つの数字を使うことと同値である。
4けたの数を作るには、まず5組から4組を選び、各組から1つずつ数字を選び、それら4つを並べる。先頭が0であるものも含めて数えると 通りである。
ここから先頭が のものを除く。先頭に を使うには組 を使い、残り3けたには他の4組から3組を選ぶ。各組から1つずつ数字を選び、残り3つの位置に並べるので 通りである。したがって、求める個数は
である。
(2)
まず3けた以下の個数を数える。1けたの正の整数は から までの9個である。
2けたのものは、先頭0を除いて 個である。3けたのものは
個である。よって3けた以下は 個である。
したがって2000番目の数は、4けたの数の中で 番目である。
千の位を1つ固定する。千の位は0ではなく、その数字が属する組はもう使えない。残り4組から3組を選び、各組から1つ選んで残り3けたに並べるので、千の位を固定したときの個数は である。、 だから、1487番目の千の位は である。 で始まる数の中では 番目である。
千の位が のとき、使えない組は である。百の位に使える数字は小さい順に である。百の位を1つ固定すると、残り2けたは、残り3組から2組を選び、各組から1つ選んで並べるので 個である。、 だから、百の位は である。 で始まる数の中では 番目である。 で始まるとき、使えない組は と である。十の位に使える数字は小さい順に である。十の位を1つ固定すると、一の位は残り2組から1つを選び、その中の数字を1つ選ぶので4通りである。、 だから、十の位は である。 で始まる数の中では 番目である。 で始まるとき、残る組は と である。一の位に使える数字は小さい順に であり、3番目は である。よって小さい方から数えて2000番目の の要素は である。