number_of_mXn_arrays_with_rows_being_permutations.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# Date: 23 February 2018
# https://github.com/trizen

# A new recurrence for computing the number of mXn arrays with rows being
# permutations of 0..n-1 and no column j greater than column j-1 in all rows.

# Special case formula for m = 3: (OEIS: A212856)
#   a(n) = f(n) * n!, where f(0) = 1, f(n) = Sum_{k=0..n-1} (-1)^(n+k+1) * f(k) * binomial(n, k)^2 / (n-k)!. - Daniel Suteu, Feb 23 2018

# OEIS sequences:
#   m = 2: https://oeis.org/A000275
#   m = 3: https://oeis.org/A212856
#   m = 4: https://oeis.org/A212857
#   m = 5: https://oeis.org/A212858

func a3(n) {

    func f((0)) { 1 }
    func f(n) is cached {
        sum(^n, {|k|
            (-1)**(n+k+1) * f(k) * binomial(n,k)**2 / (n-k)!
        })
    }

    f(n) * n!
}

say 10.of { a3(_+1) }   #=> [1, 7, 163, 8983, 966751, 179781181, 53090086057, 23402291822743, 14687940716402023]
say '-'*80

# Generalized formula by Petros Hadjicostas, Sep 08 2019 (OEIS: A212857)
#   a(n) = (-1)^(n-1) + Sum_{s = 1..n-1} a(s) * (-1)^(n-s-1) * binomial(n,s)^m for n >= 2 with a(1) = 1. For m >= 1.

func a(n, m) is cached {
    return 1 if (n == 0)
     sum(0..n-1, {|k|
        a(k, m) * (-1)**(n+k+1) * binomial(n, k)**m
    })
}

say 10.of { a(_+1, 2) }  #=> [1, 3, 19, 211, 3651, 90921, 3081513, 136407699, 7642177651, 528579161353]
say 10.of { a(_+1, 3) }  #=> [1, 7, 163, 8983, 966751, 179781181, 53090086057, 23402291822743, 14687940716402023, 12645496977257273257]
say 10.of { a(_+1, 4) }  #=> [1, 15, 1135, 271375, 158408751, 191740223841, 429966316953825, 1644839120884915215, 10079117505143103766735, 94135092186827772028779265]
say 10.of { a(_+1, 5) }  #=> [1, 31, 7291, 7225951, 21855093751, 164481310134301, 2675558106868421881, 84853928323286139485791, 4849446032811641059203617551, 469353176282647626764795665676281]