2 種類の数字だけでできる整数……そのまま掛けると多すぎる

1 から 9 の数字を使って 4 桁の整数を作ります。ちょうど 2 種類の数字が現れるものは 504 個。

種類の選び方 ${}_9{\mathrm{C}}_2=36$ に $2^4=16$ を掛けて 576、としたくなります。この 576 には、1 種類しか使っていないものが混ざっている。

2 段に分けて数える

「ちょうど 2 種類」という条件は、2 段構えで処理します。

まず、どの 2 種類を使うかを選ぶ。次に、その 2 種類だけで 4 桁を作る。

2 段目で「2 種類とも実際に現れる」ことを保証しないと、片方しか使っていない並びが混ざります。

引いてから掛ける

2 種類を $\{3,7\}$ に決めたとします。各桁がどちらかなので $2^4=16$ 通り。

このうち $3333$ と $7777$ は 1 種類しか使っていません。除いて 14 通り。

$${}_9{\mathrm{C}}_2\times (2^4-2)=36\times 14=504$$

504 個です。掛ける前に引く、という順番になります。

0 が入ると場合が分かれる

0 も使えるとすると、先頭に 0 を置けない制限が加わります。0 を含む組と含まない組で分けます。

0 を含まない 2 種類なら、さきほどと同じで 1 組あたり 14 個。組は ${}_9{\mathrm{C}}_2=36$ で 504 個。

0 と $a$ の組では、先頭が $a$ に決まります。残る 3 桁が 0 か $a$ で $2^3=8$ 通り。そのうち $aaaa$ は 1 種類なので除いて 7 個。

$a$ は 1 から 9 の 9 通りなので $9\times 7=63$ 個。

$$504+63=567$$

0 も含めて考えると 567 個になります。

検算する

4 桁の整数は全部で 9000 個。使われる数字が 1 種類なのは $1111$ から $9999$ までの 9 個です。

3 種類以上のものと合わせて 9000 になるはず。ちょうど 3 種類とちょうど 4 種類を数えれば確かめられます。

小さい桁数で試すほうが速い。3 桁なら、0 なしが $36\times (2^3-2)=216$ 個、0 ありが $9\times (2^2-1)=27$ 個で合計 243 個。

3 桁の整数 900 個のうち、1 種類が 9 個、2 種類が 243 個。残る 648 個が 3 種類とも違う場合で、$9\times 9\times 8=648$ と一致しました。

例：ちょうど 3 種類

条件が 3 種類になると、引く項が増えます。1 種類だけの場合と、2 種類だけの場合の両方が混ざるからです。

1 から 9 から 3 種類を選び、5 桁を作ります。3 種類すべてが現れるものを数える。

3 種類だけで作る 5 桁は $3^5=243$ 通り。ここから 2 種類以下のものを引きます。

2 種類の選び方が ${}_3{\mathrm{C}}_2=3$ 通りで、それぞれ $2^5=32$ 通り。1 種類しかないものを引きすぎているので、$3\times 1$ を足し戻す。

$$243-3\times 32+3=243-96+3=150$$

150 通り。種類の選び方 ${}_9{\mathrm{C}}_3=84$ を掛けて $84\times 150=12600$ 個です。

全射の個数として読む

「$n$ 桁を $k$ 種類の数字ですべて使って作る」は、$n$ 個の位を $k$ 種類へ割り当てて、どの種類も使われる形です^[4]。

4 桁で 2 種類なら 14 通り、5 桁で 3 種類なら 150 通り。どちらも空の種類を許さない配り方の数と同じ。

配る問題として見ると、桁が玉で、数字の種類が箱にあたります。

例：少なくとも 2 種類

「少なくとも 2 種類」なら、全体から 1 種類だけのものを引くだけです。

4 桁の整数 9000 個から、1 種類だけの 9 個を引いて 8991 個。

「ちょうど」と「少なくとも」で手順がまったく違う。問題文のこの 2 語を先に確かめます。

例：桁数を変える

5 桁で、1 から 9 の数字を使い、ちょうど 2 種類とします。

$1組$ あたり $2^5-2=30$ 通り。組の数は 36 なので $36\times 30=1080$ 個。

桁が 1 つ増えるだけで、504 から 1080 へ倍以上に増えます。桁数は肩に乗るので効き方が大きい。

例：0 を含む 5 桁

0 も使う場合。0 を含まない組が $36\times 30=1080$ 個。

0 と $a$ の組では、先頭が $a$ で残る 4 桁が自由。$2^4-1=15$ 個で、$9\times 15=135$ 個。

合計 1215 個です。0 を含む組では引く数が 2 ではなく 1 になる点に注意します。先頭が $a$ に固定されているので、全部 0 になる並びは最初から現れません。

よくある誤り

種類を選び、その種類だけで作り、使われない種類がある場合を引く。この 3 段を崩さなければ、桁数や種類数が変わっても同じ手順で通せます。

参考文献

^[1] が引いて足し戻す数え方、^[2] が組合せの公式、^[3] が段ごとに掛ける数え方、^[4] が空の種類を許さない配り方、^[5] が各国語での整理です。