(50g) Catalan Transforms, Hankel Transform

[John Keith]

NOTE: The first two programs should be considered obsolete. See following post for replacements.


Some more useful transforms for integer sequences. Many OEIS pages refer to these transforms.

The first two programs can be made to run on the HP48G with some minor modifications:

• Remove every I\->R and R\->I.
• Change UNROT to ROT ROT.
• Change PICK3 to 3 PICK.
  

The first two programs take a list of integers and return a list of the same length.

First, the Catalan transform. Very informative paper here.

Code:


\<< DUP SIZE 1. - \-> s
  \<< DUP HEAD SWAP 1 s R\->I
    FOR n 0 0 n
      FOR k n DUP 2 * k SWAP OVER - 1 - UNROT - COMB k * PICK3 k 1 + GET * n / +
      NEXT SWAP
    NEXT DROP s 1 + \->LIST
  \>>
\>>

Next, the inverse Catalan transform, also discussed in the paper linked above.

Code:


\<< DUP HEAD SWAP TAIL DUP SIZE \-> s
  \<< 1 s R\->I
    FOR n 0 0 n I\->R 2. / IP R\->I
      FOR k n k - DUP k COMB 4. PICK ROT GET * k I\->R 2. MOD { - } { + } IFTE
      NEXT SWAP
    NEXT DROP s 1. + \->LIST
  \>>
\>>

Finally the Hankel transform. Some info here.

This program requires a list of integers on level 2 and an integer n (the number of terms in the output list) on level 1. The list on level 2 must have at least 2*n-1 terms.

Code:


\<< I\->R \-> n
  \<< DUP HEAD SWAP 2. n
    FOR j DUP 1 j 2. * 1. - SUB j
      \<< j \->LIST
      \>> DOSUBS AXL DET SWAP
    NEXT DROP n \->LIST
  \>>
\>>