A Technical Note on Counting Moves for Generalized Towers of Hanoi
Vector 15:4, page 83
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 83
I enjoyed Howard Peelle’s article in Vector Vol.15 No.3 pp.38-46, not least because of its accustomed clarity. Its contents prompt me to make a number of observations.
First, why is there so much about triangles which are structures foreign to J? If Pascal had had J available (and just think how he would have loved it!) I surmise that we would never have heard of his triangle, but rather of his table, defined by Pt=:! ./~@i.) for a given size y. .
Page 43 contains the final version of an algorithm for counting the number of generalized Hanoi moves. In this, the phrase (+/ .* Powers) is used to multiply a vector by successive powers of 2. This can be more readily accomplished by #.&|. thereby making the verb Powers redundant, and incidentally speeding up this part of the algorithm by a factor of two.
On p.45 Howard notes the relation between the Pascal table and the Hanoi table on p.44. Having developed M, this relationship can be demonstrated by an alternative way of generating Hanoi :
To summarise some of the results which we are encouraged to obtain from the Triangle verb
give the final columns (bar the initial items) of Pt m+1 and Pt m+2 ;
+/"1(x 1,:0 0)&Triangle Repeat m gives the powers of x+1, and
+/"1(x 1,:0 1)&Triangle Repeat m gives the scans of the powers of x+1
x must be positive but need not be an integer. These are realisations of the algebraic identities
Next, two small variations in Triangle allow the Stirling numbers of the first and second kinds to be generated by replacing the verb n with s1 and s2 as indicated below.
s1=.#@] NB. Replace n with s1 to obtain Stirling nos. of first kind
s2=:>:@i.@s1 NB. For S. nos. of 2nd kind, also add parens .. ((s2 * Row), a ..
Stirling numbers of the second kind give the number of partitions of \(n\) objects into \(r\) non-empty subsets, and those of the first kind give the numbers of partitions into non-empty cycles. More details can be found in Howard’s reference [0]. The usage is (1 1,:0 0)&Triangle Repeat m . Since the verb n is being replaced, the first of the four integers in the left argument is a dummy, the others must be 1, 0 and 0 as shown.