(49g/50g) Gaussian Binomial Triangles and Transforms

[John Keith]

This group of programs compute the Gaussian binomial coefficients and the q-Stirling numbers which are closely related.

The first four programs return triangles as lists of lists. For each program, the integer on level 2 is the number of rows to return(*). The number on level 1 is the parameter q as described in the Wikipedia link. q is normally an integer but these programs will also accept real, complex or rational (e.g. '1/2') numbers.

(*) By convention, binomial coefficients start with row 0 while Stirling numbers usually start with row 1. Therefor the Stirling programs will return n rows while the binomial programs return n+1 rows (0 through n).


The next four programs implement integer transforms based on the above triangles. These are the q-analogs of the binomial, inverse binomial, Stirling S2 and Stirling S1 transforms respectively. Level 2 should have a list of numbers, and level 1 should have the parameter q as above.

For the programs listed above, if q = 1, the "standard" triangles will be returned (Pascal's triangle, it's inverse, the Stirling numbers of the 2nd kind and the Stirling numbers of the 1st kind respectively.)

The last program takes the integers n and k, and the parameter q and returns the individual Gaussian binomial coefficient [n, k]q. As above q can be any numeric type and also symbolic (e.g. 'x'), but cannot be either 1 or -1.

Some of the programs require the ListExt Library. The programs are being posted as a directory for convenience but no program is dependent on any others and unwanted programs can be removed to save space.

Code:


DIR
  GBTRI
  \<< SWAP I\->R \-> q n
    \<< { 1 } 1 OVER + 1 2 n
      START DUP q * EVAL
      NEXT n \->LIST 2. n
      FOR k DUP2 1. k SUB * 0 + PICK3 0 SWAP + 2.
        \<< + EVAL
        \>> DOLIST SWAP
      NEXT DROP n 1 + \->LIST
    \>>
  \>>
  IGBTRI
  \<< 1 \-> n q m
    \<< { 1 } -1 OVER + 2 n
      START m q * EVAL 'm' STO 0 OVER + 2.
        \<< m * - EVAL
        \>> DOSUBS 1 +
      NEXT n 1 + \->LIST
    \>>
  \>>
  QS2TRI
  \<< SWAP I\->R 1. - \-> q n
    \<< { 1 } 1 OVER + 1 2 n
      START DUP q * EVAL
      NEXT n \->LIST { + EVAL } LSCAN 2. n
      FOR k DUP2 1. k SUB * 0 + PICK3 0 SWAP + 2.
        \<< + EVAL
        \>> DOLIST SWAP
      NEXT DROP n 1. + \->LIST
    \>>
  \>>
  QS1TRI
  \<< 1 \-> n q m
    \<< { 1 } -1 OVER + 3 n
      START m q * 1 + EVAL 'm' STO 0 OVER + 2.
        \<< m * - EVAL
        \>> DOSUBS 1 +
      NEXT n \->LIST
    \>>
  \>>
  GBXF
  \<< OVER SIZE \-> b q n
    \<< b 1. 2. SUB EVAL OVER + 1 2. n
      START DUP q * EVAL
      NEXT n \->LIST { 1 1 } 3. n
      FOR k OVER 1. k 1 - SUB OVER * 0 + 0 ROT + 2.
        \<< + EVAL
        \>> DOLIST b 1. k SUB OVER * \GSLIST EVAL UNROT
      NEXT DROP2 n \->LIST
    \>>
  \>>
  IGBXF
  \<< OVER SIZE 1 \-> q n m
    \<< DUP 1. 2. SUB EVAL OVER - ROT { -1 1 } 3. n
      FOR k m q * EVAL 'm' STO 0 SWAP + 2.
        \<< m * - EVAL
        \>> DOSUBS 1 + OVER 1. k SUB OVER * \GSLIST EVAL UNROT
      NEXT DROP2 n \->LIST
    \>>
  \>>
  QS2XF
  \<< OVER SIZE \-> b q n
    \<< b 1. 2. SUB EVAL OVER + 1 2 n
      START DUP q * EVAL
      NEXT n \->LIST { + EVAL } LSCAN { 1 1 } 3. n
      FOR k OVER 1. k 1 - SUB OVER * 0 + 0 ROT + 2.
        \<< + EVAL
        \>> DOLIST b 1. k SUB OVER * \GSLIST EVAL UNROT
      NEXT DROP2 n \->LIST
    \>>
  \>>
  QS1XF
  \<< OVER SIZE 1 \-> a q n m
    \<< a 1. 2. SUB EVAL OVER - { -1 1 } 3. n
      FOR k m q * 1 + EVAL 'm' STO 0 SWAP + 2.
        \<< m * - EVAL
        \>> DOSUBS 1 + a 1. k SUB OVER * \GSLIST EVAL SWAP
      NEXT DROP n \->LIST
    \>>
  \>>
  GBC
  \<< PICK3 I\->R PICK3 I\->R DUP2 SAME OVER 0. SAME OR NOT
      { DUP2 2. * <
        { - R\->I 2. UNPICK }
        { DROP2 } IFTE \-> n k q
          \<< 1 q n -1 k LASEQ ^ - LPROD 1 q k LSEQ ^ - LPROD / EVAL
          \>> }
      { 5. DROPN 1 } IFTE
  \>>
END

[John Keith]

Updating to add another program to compute the q-Catalan numbers. Specifically, these are referred to as the "Carlitz-Riordan q-Catalan numbers". There are other types but they seem to be of little interest. For further information, search OEIS for "q-Catalan".

With an integer n on level 2 and q on level 1, the program will return a list of q-Catalan numbers from 0 to n. q may be any numeric data type or a name (e.g. 'x').

Code:


\<< SWAP I\->R \-> q n
  \<< 1 2. n
    START DUP q * EVAL
    NEXT n \->LIST { 1 1 } 2. n
    FOR k OVER 1. k SUB OVER DUP REVLIST * * \GSLIST EVAL +
    NEXT NIP
  \>>
\>>