12345678... 右肩上がり！な数: メタドローム数 (と Worpitzkyの三角形)

メタドローム

各桁が一番左から見て増え続けている(狭義単調増加している)数をメタドローム数という
https://www.numbersaplenty.com/set/metadrome/

b進数のメタドロームの総数

ひとつのメタドローム数は、123456789からどの数字を入れるか入れないか選択する組合せに一致するので、メタドローム数の総数は{1, 2, 3, 4, 5, 6, 7, 8, 9}の部分集合の数=2^9=512

一般の進数についても同様の議論が言え、メタドローム数の個数はb進数で2^(b-1)

メタドロームの族の要素の数

任意の自然数nから重複する桁と0を排除して並べ替えて、メタドローム数にする操作を考える。この操作を今のところネットサーフィンで調べて呼称を見つけたりしたわけじゃないけど、便宜的にメタドローム化M(n)と呼ぶ

n桁の数Nをメタドローム化して、Nのなかで同じm桁のメタドローム数MになるNの個数を数えたい。

Mは桁が同じmであればC(9, m)個あるが、どのMであっても対称なのでメタドローム化で得た族M^-1(M) ∩ (0,(10^n)-1)の要素の数は同じである。
n桁の数Nがメタドローム化の操作をしてMとなるには、Mのすべての桁の数字を含んでいて、なおかつ0以外にMにない数字の桁を持ってはいけない。これはn長の数列が写像としてN: n → {Mの桁の数字} ∪ {0} で 像N(n)がMの桁の数字をすべて含んでいなければならない、ということ
Nに0が含まれている場合とそうじゃない場合に場合分けすると、全射N: n → {Mの桁の数字}=m, と 全射N: n → {Mの桁の数字} ∪ {0} = m+1 をそれぞれ別に数え上げればいいことがわかる

有限集合の間の全射の数え上げは公式が知られていて、 第二種スターリング番号{n,m}と階乗m!を用いて m!{n,m}と表現できる
(参考: 躓いてる人、写像12相を早いうちにマスターすると数学人生がそのあとバラ色になるらしいですよ（知らんけど） 写像12相 https://ja.wikipedia.org/wiki/%E5%86%99%E5%83%8F12%E7%9B%B8 )

よって、n桁の数字のm桁のメタドローム数の族の数え上げは m!{n, m} + (m+1)!{n, m+1}
この式はスターリング数の変形で m!{n+1, m+1} と一致する
https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E6%95%B0
チャッピーに頼んでpythonで計算したm!{n+1, m+1}

メタドロームの族による10の冪の分解

m桁のメタドローム数となるn桁の数の数え上げをmに沿って足し合わせることで
$$ \sum_{m=0}^{n} \begin{eqnarray} \left( \begin{array}{cc} 9 \\ m \end{array} \right) \end{eqnarray} m!S(n+1, m+1) = 10^n $$
を得れる

これは 下降階乗冪とスターリング数の間に一般に成り立つ関係の変形でもある
\begin{align} x^n & = \sum_{k=0}^{n} \begin{Bmatrix} n \\ k \end{Bmatrix} (x)_{k} \\ \end{align}
https://en.wikipedia.org/wiki/Falling_and_rising_factorials

余談: Worpitzkyの三角形

さきほど得れた公式 m!{n+1, m+1}は、1,883年にドイツのJulius Worpitzkyがベルヌーイ数の値を得るために構成した Worpitzkyの三角形 としても知られている

参考 OEISオンライン整数列大辞典 https://oeis.org/A028246 , ECT組合せ三角形辞典 http://www.luschny.de/ect/Worpitzky-Triangle.html

余談2: 右肩下がり数 カタドローム

カタドローム数はメタドローム数の逆の定義をしている数で、各桁が狭義単調減少している数

メタドローム数と違って、末尾に0が置かれることで0の有無を分別する。似たような議論で0から9の集合の部分集合の数で数え上げられるが、空集合を除くので、カタドロームの数え上げの数は2^b-1となる

調べたモチベーション

メタドロームは初頭に常に0があるとも解釈できる、メタドローム化する操作は、数字から0を無いものとして純粋に0以外のアラビア文字の組み合わせとしてみるのに使える
メタドロームとカタドロームの違いは定義が逆というよりも、位数法で用いられる0を数字として認めるか否かという、古代エジプト前後で変わった数概念になぞらえられる（という意見）