| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 |
- #!/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]
|
