(50g) Catalan Transforms, Hankel Transform

[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.