進んで戻って

いよいよ年末が迫る. 元日からの通日は360+αまで来た.

ずいぶん前になるが, 365歩のマーチという曲があり, その中に「3歩進んで2歩さがる」という文句があった. これを聞いて, 昼間に2メートル登り, 夜間に1メートル滑り落ちるカタツムリが, 地上から5メートルの電柱を登りきるのに何日かかるかというクイズを思い出す向きもあろう.

TAOCP V4F3に
"To take one step forward, take two steps forward, then one step backward; to take two steps forward, take one step forward, then another"
という禅問答のような記載があり, 私も直ぐには悟りえず, しばし悩んだことがある.

順列組合せと一緒にしていわれることが多いが, 組合せは, 0,1,...,n-1のn人から, s人を選ぶ方法のことである. これはn - s = t人を選ばない方法でもあるから, TAOCPでは(s,t)組合せという.

つまり, 0号室と1号室があり, 0号室の人数をs, 1号室の人数をtとする. 0番君からn-1番君のそれぞれが, どちらの号室にいるかを, nビットの二進数で表わす.

当然_s+tC_s=_s+tC_t組が作れるわけだ.

その組合せを書き出すのに, 常識的には辞書式順, あるいは昇順に並べる. 次は(3,3)組合せの例である.




この図の赤点は, 前後の組合せで異なる位置を示す. 二進数の位置を右から0,1,2,...とすると, 始めの方の最初の赤点は, 000111から001011になった時に, 2番君が1号室から0号室に, 3番君が0号室から1号室に移ったことを示す. 右下の最後の組合せの下に6つの赤点があるのは, 111000から最初の組合せ000111に戻るには, 全員が部屋を移る必要があるということである.

かくも大勢が右往左往しては, ドア回りが混雑するので, 回転ドア方式を考えた人がいる. 0号室と1号室の間に回転ドアがあり, 回転ドアを通って1人ずつだけが入れ替わるのである.



すなわち, この図で見るように, 赤点は常に2個である. なかなかうまく出来ている.

これは6ビットのGray codeを作り, 1のビットが3個のものだけリストして作った.

(define (gray bs)
 (define (xor a b) (modulo (+ a b) 2))
 (map xor bs (cons 0 (reverse (cdr (reverse bs))))))

(for-each (lambda (n) (for-each display n) (newline))
 (filter (lambda (x) (= (apply + x) 3))
  (map gray (map (lambda (n) (n2bs n 6)) (a2b 0 64)))))

ところでよく見ると, この赤点の間隔はいろいろだ. 2つ隣り同士のところが10, 間が1個空いているのが4, 2個空いているのが4, 3個空いているのが2で計20である.

この間の幅を0と1にしても出来るといい出した人がいるらしい.

がその1例である. 最後から最初に戻るのは別として, 途中の赤点はすべて隣り同士か1個空きである. このパターンをA₃₃という. しかし, こういうパターンはこれだけでなく, 次のB₃₃もそうなっている.


途中には目をつぶると, A₃₃は111000から始まり, 011100で終る. B₃₃は111000から始まり, 001110で終る. 一般にA_stは, 0がs個, 1がt個から始まり, 0が1個, 1がt個, 0がs-1個で終り, B_stは, 0がs個, 1がt個から始まり, 0が2個, 1がt個, 0がs-2個で終る.

AとBの漸化式も知られている.

A_st = 1B_s(t-1), 0A_(s-1)t^R;
B_st = 1A_s(t-1), 0A_(s-1)t.

これを図で示すと次のようになる. いまはs=t=3である.



左の組合せは, は下の黒文字の説明にあるように, B₃₃である. 上の漸化式に当てはめると, B₃₃ = 1A₃₂, 0A₂₃.

つまり, 左のB₃₃は, A₃₂の前に1を置いたものを並べ, 次にA₂₃の前に0を置いたものを並べると読む. 1や0の後に置く部品の組合せは赤で囲んである. 説明も赤文字である.

また, A₃₃ = 1B₃₂, 0A₂₃^R.

つまり, 右のA₃₃は, B₃₂の前に1を置いたものを並べ, 次にA₂₃の, 右肩にRがついているから, 上下逆転したものの前に0を置いたものを並べると読む.

たしかに左の下半分のA₂₃と右の下半分のA₂₃^Rは, 上下が逆である.

改めて右のA₃₃を見ると, 最初の111000は最後は011100になり, 111は右へ1歩進んだ. B₃₃では, 111は右に2歩進んだ. 部品を見るとA₃₂は11が右へ1歩進み, A₂₃は111が右へ1歩進み, B₃₂は11が右へ2歩進む. 右下のA₂₃^Rを上から下へ眺めると, 今度は01110が11100になるから, 111が1歩戻ったことになる.

これが最初の「一歩進む(A_st)には, 二歩進み(B_s(t-1)), 一歩戻る(A_(s-1)t^R). 二歩進む(B_st)には, 一歩進み(A_s(t-1)), もう一歩進む(A_(s-1)t)」の謎解きであった.

私がこの解釈に気づいたのは, 2008年の1月頃であった, 2008年の夏にKnuth先生に会った時, 「あの2歩前進, 1歩後退の意味は, 苦労したがついに分かった.」と報告した. Knuth先生は笑っただけであった.

微分解析機

今回は微分解析機といっても, トルクアンプ, 日本語では回転力増幅器の, それも図の話である.

微分解析機の積分機の出力は, 摩擦で生じる微少な力なので, これで他のものを駆動することは出来ない. ところがNewmanにより, トルクアンプが発明され, それによって微分解析機は実用になった.

トルクアンプは, 下の図のような構造である.



右のinputの軸の回転を, 左のoutputの軸から力を増幅して取り出すのである. その間にロープを書けたドラムが2組あり, ロープの端は, 入力と出力軸に取りつけたT字状のレバーの先に固定されている. ドラムは両端のプーリーにかけたベルトで, 矢印の方向に, 逆方向に回転している. 入力軸が回転しない時は, ロープはドラムの面を滑っている.

今, 入力軸が, 右に回転したとする. そうすると, 下のT字状のレバーが持ち上がり, 左のロープがドラムの上で締まり, ドラムとの間に摩擦が生じ, 上のT字状のレバーが押し下げられ, 出力軸が入力軸と同じ方向に回転する. 回転角が同じになれば, ロープは弛み, 再び滑り出す.

入力軸が反対に回る場合は, 右のドラムの摩擦が生じ, 出力軸はやはり入力軸と同回転する.

つまり, 回転するドラムが動力になり, 入力の微少な力を増幅するのである.

こういう仕掛けは船の碇を巻き上げる装置にもあるらしい.

さて, 上のような図で説明したが, 私としては, ロープを直線で描いたのが気に入らないのである. 図はなるべく正確に描きたいというからには, このようにドラムの縁で光の反射のような図はだめである.



そこで考えたのがこの図である. 上と下のT字状のレバーにロープが繋がっている点をAとEとする. 図の円はドラムの断面である. ロープは, AからBに至ってドラムに接し, BCDFBCDとドラムを1回とすこし回り, Dから離れてEでもう一方のT字状のレバーに辿り着く. 先ほどの図は, これを左から見たものだ. そうすると, ロープ上の点は, Aから下がり, ドラムの円の右半分を上がり, また下がるように見えるはずである. また左右の座標位置は, ロープの長さに比例して右へ移動するはずである.

その移動の様子を, 半径の右の, 点の列で示す. 赤はロープのAからBに対応する. 緑はBCDFBCDに対応, 最後の青はDからEである.

そういう解釈で, 最初の図を描き直すと下の絵になる.



ざっと見ると最初の図と左程違わないが, ドラム回りのロープは本当らしくなったのではないか.

クリスマスツリー講義

今月(2010年12月)始め, Knuth先生から, いつもの航空便ではなく, 珍しくメイルで返事が来た. その最後に

By the way, my lecture next Monday will probably be webcast live, so you might be able to watch it via Internet in Japan.

と書いてあった. その日(日本時間では7日朝)は所用あって, インターネットも見ずに過ぎたが, ホームページには,

Monday, 06 December, 5:30pm, in the new NVIDIA auditorium (Huang Engineering Center) A Computer Musing entitled ``Why pi?'' [the sixteenth annual Christmas Tree Lecture]

あ, これがあのクリスマスツリー講義(Christmas Tree Lecture)だったのか.

すぐに連想するのは, 元祖「クリスマス講演」である.

「これから皆さんにロウソクのお話をいたそうと思います.」で始まるMichael Faradayの「ロウソクの科学」は, 1860年のクリスマスであった. だから150年前の話だ. ところでこの原題はThe Chemical History of a Candleという.

Royal Institution Christmas LecturesをWikipediaでみると, 1825年に始まり, 第２次世界大戦中を除き, 今年も続けているというから, 英国のこだわりにはまったく脱帽する.

一方, クリスマスツリー講義は, Knuth先生が, 年末に一般向けに講義するものらしい.

TAOCP V4F4の表4に8次のクリスマスツリーパターンという図があり, その脚注に(TAOCPに脚注があるのは異例なことだが),

"This name was chosen for sentimental reasons, because the pattern has a general shape not unlike that of a festive tree, and because it was the subject of the author's ninth annual "Christman Tree Lecture" at Stanford University in December 2002."

と書いてある.

8次は大きすぎるから遠慮し, 6次のクリスマスツリーは以下のように, 6ビットの二進数64個を, ₆C₃=20行, 6+1列に配置する.

左からの各列は, 1の個数が0, 1, ..., 6である. 従って中央の高さは₆C₃である. 同じ行では, 右に行くに従い, 0が1に変っていく. 赤い0は, 次に1になるもの, 青い1は, 前に0だったものだ.

この配置法は, 1951年にde Bruijn, van Ebbenhorst Tengbergen, Kruyswijkが発見した.

                     101010
              101000 101001 101011
                     101100
              100100 100101 101101
              100010 100110 101110
       100000 100001 100011 100111 101111
                     110010
              110000 110001 110011
                     110100
              010100 010101 110101
              010010 010110 110110
       010000 010001 010011 010111 110111
                     111000
              011000 011001 111001
              001010 011010 111010
       001000 001001 001011 011011 111011
              001100 011100 111100
       000100 000101 001101 011101 111101
       000010 000110 001110 011110 111110
000000 000001 000011 000111 001111 011111 111111

これはどうできているかというと, 1次は

  0 1

の1行. これではクリスマスツリーにならない. 2次は

   10
00 10 11

の2行. いささかツリーらしくなる.

さて, n次のツリーの各行を,
σ₁,...,σ_s
とすると, n+1次のツリーは, 各行を
σ₂0,...,σ_s0と
σ₁0,σ₁1,...,σ_s1の
2行にする.

すなわち, 後に0をつけたものと, 後に1をつけたものを作り, 0をつけたものの先頭の1個を1をつけたものの先頭に移動するのである. 先頭を外した後が0個になったら, その行は除く.

Schemeで書くと

(define (next ct)
 (if (null? ct) '()
  (let ((ss0 (map (lambda (s) (string-append s "0"))
　　　　　　　 (car ct)))
        (ss1 (map (lambda (s) (string-append s "1"))
　　　　　　　 (car ct))))
   (set! ss1 (cons (car ss0) ss1))
   (set! ss0 (cdr ss0))
   (if (null? ss0) (cons ss1 (next (cdr ct)))
       (cons ss0 (cons ss1 (next (cdr ct))))))))

である. ctを

(define ct '(("0" "1")))

によって１次のクリスマスツリーとし, ctにnextを順に作用させると,

(("10") ("00" "01" "11"))

(("100" "101") ("010" "110") ("000" "001" "011" "111"))

(("1010") ("1000" "1001" "1011") ("1100") 
　("0100" "0101" "1101") ("0010" "0110" "1110")
  ("0000" "0001" "0011" "0111" "1111"))

が得られる. クリスマスツリーらしいのは, 次数nが偶数の時である.

6次のクリスマスツリーパターンは, 異なる64の要素があるから, それを八卦の64のパターンで置き換えたのか以下である.



これは, 昨年の, 私からKnuth先生へのクリスマスカードであった.

1のかたまり

TAOCPに  A_n=Σ_k=0ⁿ _n-kC_2k  という式があった(演習問題7.1.4--125).

その解答のHistorical Noteに A_ncounts binary x₁...x_n-1 with each 1 next to another と書いてある. なんだろうと思っているうちに, Knuth先生からのある手紙にヒントがあった.

ちなみにA_nの値は

n   1 2 3 4 5  6  7  8  9 ...
An  1 1 2 4 7 12 21 37 65 ... .

とりあえずn=5を考える. するとbinary x₁...x_n-1は

0 0 0 0 *
0 0 0 1
0 0 1 0
0 0 1 1 *
0 1 0 0
0 1 0 1
0 1 1 0 *
0 1 1 1 *
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0 *
1 1 0 1
1 1 1 0 *
1 1 1 1 *

with each 1 next to another は, 1があれば単独では現れないということで, そういうものは, 上で星印をつけた7=A₅個になる. 1は孤立していて失格である. 問題はこのパターンの見つけかたである. 星印のものを取り出すと

0 0 0 0
0 0 1 1
0 1 1 0
0 1 1 1
1 1 0 0
1 1 1 0
1 1 1 1

最初のは1がないから別にして, 残りは1のかたまりが1個ある. 1が孤立するかたまりはないから, 1のかたまりから1個外したパターンを書くと

1 2 3 4
 0 0 1
 0 1 0
 0 1 1
 1 0 0
 1 1 0
 1 1 1

となる. ビットの境界に左から1,2,3,4と番号をつけ, 0と1の境界の位置を書いてみると

3 4
2 3
2 4
1 2
1 3
1 4

となり, これは4個から2個選ぶ数であった. つまり₄C₂=_n-1C₂=6.


同様にして, 1のかたまりが2個あるパターンは, n=7の0 1 1 0 1 1 から考え始めて

1 2 3 4 5
 0 1 0 1    2 3 4 5
 1 0 0 1    1 2 4 5
 1 0 1 0    1 2 3 4
 1 0 1 1    1 2 3 5
 1 1 0 1    1 3 4 5

だから, 右にあるような境界の位置を見れば, ₅C₄=_n-2C₄(1のかたまりが2個の場合).

という次第で, 一般に1のかたまりがk個ある数は_n-kC_2k.
一番上の1のかたまりのないものは_nC₀=1.



2項係数_nC_mは, n<mの時に0だから, かたまりがとれるところまで足せばよく, 1のかたまりの置き方の数になるのであった. 結構むずかしい. 私もヒントなしでは, ここまで辿りつかなかっただろう.

2011

1年ほど前 2010が1から9までを使ったどういう式で表わせるかを計算し, このブログに書いたことがある.

今回は2011である. 28個の解があった.

(+ 1 (* (/ 2 3) (- (* (* (* (+ 4 5) 6) 7) 8) 9)))
(- 1 (* 2 (+ 3 (* (* (- (- (- 4 5) 6) 7) 8) 9))))
(- (* (- (/ 1 2) (* (* (- (- 3 4) 5) 6) 7)) 8) 9)
(+ (* 1 2) (* (+ 3 4) (- (* (+ (* 5 6) 7) 8) 9)))
(* 1 (+ 2 (* (+ 3 4) (- (* (+ (* 5 6) 7) 8) 9))))
(* 1 (- (* (+ (* 2 3) 4) (- (* (* 5 6) 7) 8)) 9))
(- (* (+ (+ (+ 1 2) 3) 4) (- (* (* 5 6) 7) 8)) 9)
(- (* (+ (* (* 1 2) 3) 4) (- (* (* 5 6) 7) 8)) 9)
(- (* (* 1 (+ (* 2 3) 4)) (- (* (* 5 6) 7) 8)) 9)
(- 1 (* (/ 2 3) (- (+ 4 5) (* (* (* 6 7) 8) 9))))
(+ 1 (* (* (/ 2 3) (+ (- 4 5) (* (* 6 7) 8))) 9))
(+ (- (* 1 2) 3) (* 4 (+ (- 5 6) (* (* 7 8) 9))))
(* 1 (+ (- 2 3) (* 4 (+ (- 5 6) (* (* 7 8) 9)))))
(+ (* 1 (- 2 3)) (* 4 (+ (- 5 6) (* (* 7 8) 9))))
(+ (/ 1 (- 2 3)) (* 4 (+ (- 5 6) (* (* 7 8) 9))))
(+ 1 (* (+ 2 (* (- 3 (* 4 (- (/ 5 6) 7))) 8)) 9))
(+ (* 1 2) (* (+ 3 4) (+ 5 (* 6 (- (* 7 8) 9)))))
(* 1 (+ 2 (* (+ 3 4) (+ 5 (* 6 (- (* 7 8) 9))))))
(- (- 1 (* 2 3)) (* (* (* (* 4 (- 5 6)) 7) 8) 9))
(- (- 1 (* 2 3)) (* (* (* (/ 4 (- 5 6)) 7) 8) 9))
(- 1 (* (+ (/ 2 3) (* (* (* 4 (- 5 6)) 7) 8)) 9))
(- 1 (* (+ (/ 2 3) (* (* (/ 4 (- 5 6)) 7) 8)) 9))
(- (* 1 2) (* (+ 3 4) (+ (* (- 5 (* 6 7)) 8) 9)))
(* 1 (- 2 (* (+ 3 4) (+ (* (- 5 (* 6 7)) 8) 9))))
(- 1 (* (* 2 3) (+ (* (- (- 4 5) (* 6 7)) 8) 9)))
(+ 1 (* (* 2 3) (- (* 4 (+ (* 5 6) (* 7 8))) 9)))
(- 1 (* (* (- (/ 2 3) 4) (+ (+ 5 6) (* 7 8))) 9))
(+ (* (+ 1 (* (* 2 (+ 3 (* 4 5))) 6)) 7) (* 8 9))

最後の
(1+2*(3+4*5)*6)*7+8*9
が美しい.

双曲線

円錐曲線の中で, もっとも馴染みがないのが双曲線である. したがってda Vinciも双曲線コンパスは考えなかったかも知れない.

反比例 y=1/xを習うと, この形は双曲線と教わる. 確かにx軸とy軸は漸近線だし, 第1象限と同じ図形が第3象限にもある.

xy=1を x'=√2 x-√2 y, y'=√2 7+√2で置き換える. つまり45度回転すると, 確かにx²/2-y²/2=1となり, 双曲線である.

ところで, 双曲線というと, 以前から気になる文言がある. 高橋秀俊先生の「数理と現象」に

「楕円は丸い茶碗やお盆を横から見たときの形として, 万人の日常接しているところであるが, 放物線と双曲線はそれほど親しみがあるとはいえないかもしれない. しかし, 円錐曲線はすべて円錐の切り口, つまり円形をある方向から見たときの形であって, 誰でも目にふれるはずのものである. すなわち大きい円を近くから見て, 円の一部が眼よりも後に来るような場合は, 円は双曲線(の片側)に見え, ちょうど眼の平面(眼のところを通って視線に垂直な平面)に接する場合は放物線に見えるのである.」

と書いてある. 確かに付随する写真では放物線や双曲線のように見える. これはどういうことか, ずーっと疑問に思っていた.

私は自他ともに認めるPostScript描画大好き人間なので, さっそく図を実際に書いてみることにした.




すなわち, 円Oの中央の真上の点Hから, 水平に置いた円Oを, その円周上で接している面Pに投影し, 得られる(赤線の)図形を描いてみたのである. 特殊な環境だが, 計算式を簡単にしたかったからである.

たしかにHの真横の円の部分は右下, 左下の遠方に投影されるから, 双曲線になりそうである. そして出来た図が下である.






視点HをOの真上にとったのは, 怪我の功名であって, 実はHを頂点とする円錐を平面Pで切ったので, 断面が双曲線なのは当たり前である. 高橋先生がいわれるのは, 円内のもっと一般的なところで見ても双曲線ということで, それには別の視点が必要そうだ.

楕円コンパス(つづき)

Leonardo da Vinciは放物線のためのコンパスも考案した. この方はたまたまウェブに図があった(http://www.japandesign.ne.jp/HTM/REPORT/art_review/38/big/05.html)ので, 借用させていただく.



前回のブログの最後に書いたように, 離心率が大きい(=1に近い)と楕円コンパスは苦しくなる. 放物線は離心率が1なので, 発想の転換が必要だ. そこでda Vinciは別の機構を考えたのであろう.

こちも原理は楕円の場合と同じである. 円錐を母線と平行な面で切ると放物線になる性質を利用している. 前回の図で, 切断面が母線と平行になると, 上の球は作図出来るが, 下の球は存在しない. つまり焦点は1つになる.



放物線コンパスの仕掛けを上の図で説明しよう.

ACは鉛直な回転軸である. Cを頂点とし, 底面が円DQEFの円錐を考える. 回転軸を支えるのに, CD, CE, CFの3本がある. 3本の足は, 別に母線に合っている必要はないが, da Vinciの図がなんとなくそうなっているのに従った.

P点に筆記具をつけた伸縮自在の腕 BPは, 母線に沿って回転し, PはDからスタートしてPへ至り, さらにEまで進む. すると放物線DPEが描けるのである.

円錐の角度を一定に保つために, GHがある. 模型で見るように, 放物線を描く面は, 母線と平行に傾けてある. その面の上をPが伸縮しながら放物線を描くのである. 筆記具を平面に押し付けるためか, CPの中間に錘りがぶら下がっているのも面白い.