(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
  \>>
\>>

[John Keith]

First, new programs for the Catalan and inverse Catalan transforms. The new programs are significantly faster, especially for the Catalan transform.

Catalan transform:

Code:


\<< DUP SIZE \-> n
  \<< DUP 1. 2. SUB SWAP TAIL { 1 } 2. n 1. -
    FOR k 0 + :: + Scanl1 OVER 1. k SUB REVLIST
OVER * \GSLIST 4. ROLL SWAP + UNROT
    NEXT DROP2
  \>>
\>>

Inverse Catalan transform:

Code:


\<< DUP 1. 3. SUB EVAL OVER - 3. \->LIST
SWAP TAIL DUP SIZE \-> b n
  \<< { 1 } -1 OVER + 3. n
    FOR k SWAP 0 + OVER SWAP - 0 SWAP + DUP
b 1. k SUB * \GSLIST 4. ROLL SWAP + UNROT
    NEXT DROP2
  \>>
\>>

Next, the ballot transform and the inverse ballot transform. These two transforms are described in the linked paper in the post above. They are related to the Catalan and binomial transforms by the following identities:

The ballot transform is equivalent to the binomial transform followed by the Catalan transform.

The inverse ballot transform is equivalent to the inverse Catalan transform followed by the inverse binomial transform.


Ballot transform:

Code:


\<< DUP SIZE \-> n
  \<< DUP 1. 2. SUB EVAL OVER +
2. \->LIST { 1 1 } 3. n
    FOR k DUP 1. 2. SUB EVAL + SWAP 0 + 3.
      \<< SWAP 2 * + +
      \>> DOSUBS + 1 + PICK3 1. k SUB
OVER * \GSLIST ROT SWAP + SWAP
    NEXT DROP NIP
  \>>
\>>

Inverse ballot transform:

Code:


\<< DUP SIZE \-> b n
  \<< { 1 } -1 OVER + b 1. 2. SUB EVAL
OVER - 2. \->LIST UNROT 3. n
    FOR k SWAP OVER 2.
      \<< -2 * +
      \>> DOSUBS SWAP LPOP UNROT 0 + - + 1 + b 1. k SUB
OVER * \GSLIST 4. ROLL SWAP + UNROT
    NEXT DROP2
  \>>
\>>

The Catalan transform program requires GoferLists, and the inverse ballot transform requires ListExt.