😊出会いの泉😊

あ、時計がずれてたのか9時9分投稿に失敗した……。


一応、例示も置いときます。

例1：602214076 は、1 未満の数字が 2 回、2 未満の数字が 3 回、3 未満の数字が 5 回、4 未満の数字が 5 回、5 未満の数字が 6 回、6 未満の数字が 6 回、7 未満の数字が 8 回、8 未満の数字が 9 回、9 未満の数字が 9 回、登場するので条件を満たす。

例2：299792458 は、1 未満の数字が 0 回だったり、7 未満の数字が 4 回だったり、偽になる命題が存在するので条件を満たさない。

例3：101325 は、9 桁表示の 000101325 で個数をカウントするので、条件を満たす。

99,999,999(個)でしょうか？

1～10 では9(個)
1～10^2 では80
1～10^3 では700
1～10^4 では6,000
1～10^5 では50,000
1～10^6 では400,000
1～10^7 では3,000,000
1～10^8 では20,000,000
1*10^8+1～2*10^8では 15,217,031
2*10^8+1～3*10^8では 13,119,879
3*18^8+1～4*10^8では 11,708,091
4*10^8+1～5*10^8では 10,546,875
5*10^8+1～6*10^8では 9,453,125
6*10^8+1～7*10^8では 8,291,909
7*10^8+1～8*10^8では 6,880,121
8*10^8+1～9*10^8では 4,782,968
9*10^8+1～10^9-1では 0
よって
10^8+1～10^9-1では79,999,999
以上から
1～999,999,999で条件を満たすものは20,000,000+79,999,999=99,999,999(個)
の模様です。

正しく9に纏わるDD++さんらしい問題でした。

正解です、お見事！
問題も正解も投稿日時もキューだらけの問題でした。

きっとスマートな解法があるのでしょうが、思いつかないので力技です。



n ≧ m ≧ 1 とする。
0, 1, ..., m の m+1 種類の数を重複を許して一列に n 個並べるとき、
1 ≦ q ≦ m となる任意の整数 q について q 未満の数を q 個以上含むような並べ方の数を f(m,n) とおく。

[1] m = 1 のとき
条件を満たさないものは並べる数のすべてが "1" となる場合の 1 通りなので、
f(1,n) = 2^n - 1
となる。

[2] m ≧ 2 のとき
並べる数のなかの "m" の個数を k 個として k で場合分けする。
k > n-m の場合は m 未満の数が m 個未満となってしまうため、条件を満たさない。
0 ≦ k ≦ n-m の場合、数 "m" の配置方法が nCk 通りあり、その各々に対して残りの数の並べ方が f(m-1,n-k) 通りある。
よって、
f(m,n) = Σ[k=0,...,n-m] nCk * f(m-1,n-k)
となる。

[1],[2]を用いて順次計算していくと次のようになる。

f(1,1) = 1
f(1,2) = 3
f(1,3) = 7
f(1,4) = 15
f(1,5) = 31
f(1,6) = 63
f(1,7) = 127
f(1,8) = 255
f(1,9) = 511

f(2,2) = 3
f(2,3) = 16
f(2,4) = 61
f(2,5) = 206
f(2,6) = 659
f(2,7) = 2052
f(2,8) = 6297
f(2,9) = 19162

f(3,3) = 16
f(3,4) = 125
f(3,5) = 671
f(3,6) = 3130
f(3,7) = 13686
f(3,8) = 57867
f(3,9) = 240049

f(4,4) = 125
f(4,5) = 1296
f(4,6) = 9031
f(4,7) = 54062
f(4,8) = 301321
f(4,9) = 1616764

f(5,5) = 1296
f(5,6) = 16807
f(5,7) = 144495
f(5,8) = 1059261
f(5,9) = 7196785

f(6,6) = 16807
f(6,7) = 262144
f(6,8) = 2685817
f(6,9) = 23343742

f(7,7) = 262144
f(7,8) = 4782969
f(7,9) = 56953279

f(8,8) = 4782969
f(8,9) = 100000000

f(9,9) = 100000000


求めるものは、 m = 9, n = 9 の場合の数から並べる数のすべてが "0" となる 1 通りを除いたものなので、
f(9,9)-1 = 99999999
通りとなる。



計算結果を見ると、
f(m,m) = (m+1)^(m-1)
になるみたいですね。

なるほど、そういうこともできるんですね。
結論にスパッと切り込む方法としては、
(314159265, 425260376, 536371487, ……, 203048154)
のように数字を 1 つずつずらした数からなる 10 個組を作ると、9 個の命題のうち何個満たされるかが全て異なることを証明することでしょうか。

そうすれば 999,999,999 個のうちゾロ目を除いた 999,999,990 個中 10 個に 1 個が条件を満たすことから 99,999,999 個であるとすぐにわかります。

まあ、満たされる命題数が全て異なることの証明が手間になるわけですけども。

りらひいさんの漸化式が面白かったので、これでいろいろ遊んでいたら
OEISでA373086がたまたまヒットした。
ここにリンクで張られた論文が関連するように思われるんですが、自分にはわからない部分が
多くて手ごわくて、りらひいさんならよく理解されるのではないかと思いました。