(50g) Catalan Transforms, Hankel Transform
01-24-2019, 09:45 PM (This post was last modified: 12-06-2019 10:33 PM by John Keith.)
Post: #1 John Keith Senior Member Posts: 483 Joined: Dec 2013
(50g) Catalan Transforms, Hankel Transform
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   \>> \>>
12-06-2019, 10:53 PM
Post: #2 John Keith Senior Member Posts: 483 Joined: Dec 2013
RE: (50g) Catalan Transforms, Hankel Transform
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.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)