Lah numbers: Difference between revisions
m (→{{header|Haskell}}: Restored OP's formatting style.) |
m (Phix/mpfr) |
||
Line 818:
=={{header|Phix}}==
{{libheader|Phix/mpfr}}
{{trans|Go}}
<lang Phix>include mpfr.e
|
Revision as of 11:25, 25 May 2020
You are encouraged to solve this task according to the task description, using any language you may know.
Lah numbers, sometimes referred to as Stirling numbers of the third kind, are coefficients of polynomial expansions expressing rising factorials in terms of falling factorials.
Unsigned Lah numbers count the number of ways a set of n elements can be partitioned into k non-empty linearly ordered subsets.
Lah numbers are closely related to Stirling numbers of the first & second kinds, and may be derived from them.
Lah numbers obey the identities and relations:
L(n, 0), L(0, k) = 0 # for n, k > 0 L(n, n) = 1 L(n, 1) = n! L(n, k) = ( n! * (n - 1)! ) / ( k! * (k - 1)! ) / (n - k)! # For unsigned Lah numbers or L(n, k) = (-1)**n * ( n! * (n - 1)! ) / ( k! * (k - 1)! ) / (n - k)! # For signed Lah numbers
- Task
-
- Write a routine (function, procedure, whatever) to find unsigned Lah numbers. There are several methods to generate unsigned Lah numbers. You are free to choose the most appropriate for your language. If your language has a built-in, or easily, publicly available library implementation, it is acceptable to use that.
- Using the routine, generate and show here, on this page, a table (or triangle) showing the unsigned Lah numbers, L(n, k), up to L(12, 12). it is optional to show the row / column for n == 0 and k == 0. It is optional to show places where L(n, k) == 0 (when k > n).
- If your language supports large integers, find and show here, on this page, the maximum value of L(n, k) where n == 100.
- See also
- Related Tasks
C
<lang c>#include <stdint.h>
- include <stdio.h>
uint64_t factorial(uint64_t n) {
uint64_t res = 1; if (n == 0) return res; while (n > 0) res *= n--; return res;
}
uint64_t lah(uint64_t n, uint64_t k) {
if (k == 1) return factorial(n); if (k == n) return 1; if (k > n) return 0; if (k < 1 || n < 1) return 0; return (factorial(n) * factorial(n - 1)) / (factorial(k) * factorial(k - 1)) / factorial(n - k);
}
int main() {
int row, i;
printf("Unsigned Lah numbers: L(n, k):\n"); printf("n/k "); for (i = 0; i < 13; i++) { printf("%10d ", i); } printf("\n"); for (row = 0; row < 13; row++) { printf("%-3d", row); for (i = 0; i < row + 1; i++) { uint64_t l = lah(row, i); printf("%11lld", l); } printf("\n"); }
return 0;
}</lang>
- Output:
Unsigned Lah numbers: L(n, k): n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1
C#
<lang csharp>using System; using System.Linq; using System.Numerics;
namespace LahNumbers {
class Program { static BigInteger Factorial(BigInteger n) { if (n == 0) return 1; BigInteger res = 1; while (n > 0) { res *= n--; } return res; }
static BigInteger Lah(BigInteger n, BigInteger k) { if (k == 1) return Factorial(n); if (k == n) return 1; if (k > n) return 0; if (k < 1 || n < 1) return 0; return (Factorial(n) * Factorial(n - 1)) / (Factorial(k) * Factorial(k - 1)) / Factorial(n - k); }
static void Main() { Console.WriteLine("Unsigned Lah numbers: L(n, k):"); Console.Write("n/k "); foreach (var i in Enumerable.Range(0, 13)) { Console.Write("{0,10} ", i); } Console.WriteLine(); foreach (var row in Enumerable.Range(0, 13)) { Console.Write("{0,-3}", row); foreach (var i in Enumerable.Range(0, row + 1)) { var l = Lah(row, i); Console.Write("{0,11}", l); } Console.WriteLine(); } Console.WriteLine("\nMaximum value from the L(100, *) row:"); var maxVal = Enumerable.Range(0, 100).Select(a => Lah(100, a)).Max(); Console.WriteLine(maxVal); } }
}</lang>
- Output:
0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the L(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
C++
<lang cpp>// Reference: https://en.wikipedia.org/wiki/Lah_number#Identities_and_relations
- include <algorithm>
- include <iomanip>
- include <iostream>
- include <map>
- include <gmpxx.h>
using integer = mpz_class;
class unsigned_lah_numbers { public:
integer get(int n, int k);
private:
std::map<std::pair<int, int>, integer> cache_;
};
integer unsigned_lah_numbers::get(int n, int k) {
if (k == n) return 1; if (k == 0 || k > n) return 0; auto p = std::make_pair(n, k); auto i = cache_.find(p); if (i != cache_.end()) return i->second; integer result = (n - 1 + k) * get(n - 1, k) + get(n - 1, k - 1); cache_.emplace(p, result); return result;
}
void print_lah_numbers(unsigned_lah_numbers& uln, int n) {
std::cout << "Unsigned Lah numbers up to L(12,12):\nn/k"; for (int j = 1; j <= n; ++j) std::cout << std::setw(11) << j; std::cout << '\n'; for (int i = 1; i <= n; ++i) { std::cout << std::setw(2) << i << ' '; for (int j = 1; j <= i; ++j) std::cout << std::setw(11) << uln.get(i, j); std::cout << '\n'; }
}
int main() {
unsigned_lah_numbers uln; print_lah_numbers(uln, 12); std::cout << "Maximum value of L(n,k) where n == 100:\n"; integer max = 0; for (int k = 0; k <= 100; ++k) max = std::max(max, uln.get(100, k)); std::cout << max << '\n'; return 0;
}</lang>
- Output:
Unsigned Lah numbers up to L(12,12): n/k 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 2 1 3 6 6 1 4 24 36 12 1 5 120 240 120 20 1 6 720 1800 1200 300 30 1 7 5040 15120 12600 4200 630 42 1 8 40320 141120 141120 58800 11760 1176 56 1 9 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value of L(n,k) where n == 100: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
D
<lang d>import std.algorithm : map; import std.bigint; import std.range; import std.stdio;
BigInt factorial(BigInt n) {
if (n == 0) return BigInt(1); BigInt res = 1; while (n > 0) { res *= n--; } return res;
}
BigInt lah(BigInt n, BigInt k) {
if (k == 1) return factorial(n); if (k == n) return BigInt(1); if (k > n) return BigInt(0); if (k < 1 || n < 1) return BigInt(0); return (factorial(n) * factorial(n - 1)) / (factorial(k) * factorial(k - 1)) / factorial(n - k);
}
auto max(R)(R r) if (isInputRange!R) {
alias T = ElementType!R; T v = T.init;
while (!r.empty) { if (v < r.front) { v = r.front; } r.popFront; }
return v;
}
void main() {
writeln("Unsigned Lah numbers: L(n, k):"); write("n/k "); foreach (i; 0..13) { writef("%10d ", i); } writeln(); foreach (row; 0..13) { writef("%-3d", row); foreach (i; 0..row+1) { auto l = lah(BigInt(row), BigInt(i)); writef("%11d", l); } writeln(); } writeln("\nMaximum value from the L(100, *) row:"); auto lambda = (int a) => lah(BigInt(100), BigInt(a)); writeln(iota(0, 100).map!lambda.max);
}</lang>
- Output:
Unsigned Lah numbers: L(n, k): n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the L(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Factor
<lang factor>USING: combinators combinators.short-circuit formatting infix io kernel locals math math.factorials math.ranges prettyprint sequences ; IN: rosetta-code.lah-numbers
! Yes, Factor can do infix arithmetic with local variables! ! This is a good use case for it.
INFIX:: (lah) ( n k -- m )
( factorial(n) * factorial(n-1) ) / ( factorial(k) * factorial(k-1) ) / factorial(n-k) ;
- lah ( n k -- m )
{ { [ k 1 = ] [ n factorial ] } { [ k n = ] [ 1 ] } { [ k n > ] [ 0 ] } { [ k 1 < n 1 < or ] [ 0 ] } [ n k (lah) ] } cond ;
"Unsigned Lah numbers: n k lah:" print "n\\k" write 13 dup [ "%11d" printf ] each-integer nl
<iota> [
dup dup "%-2d " printf [0,b] [ lah "%11d" printf ] with each nl
] each nl
"Maximum value from the 100 _ lah row:" print 100 [0,b] [ 100 swap lah ] map supremum .</lang>
- Output:
Unsigned Lah numbers: n k lah: n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the 100 _ lah row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Fōrmulæ
In this page you can see the solution of this task.
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition.
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
Go
<lang go>package main
import (
"fmt" "math/big"
)
func main() {
limit := 100 last := 12 unsigned := true l := make([][]*big.Int, limit+1) for n := 0; n <= limit; n++ { l[n] = make([]*big.Int, limit+1) for k := 0; k <= limit; k++ { l[n][k] = new(big.Int) } l[n][n].SetInt64(int64(1)) if n != 1 { l[n][1].MulRange(int64(2), int64(n)) } } var t big.Int for n := 1; n <= limit; n++ { for k := 1; k <= n; k++ { t.Mul(l[n][1], l[n-1][1]) t.Quo(&t, l[k][1]) t.Quo(&t, l[k-1][1]) t.Quo(&t, l[n-k][1]) l[n][k].Set(&t) if !unsigned && (n%2 == 1) { l[n][k].Neg(l[n][k]) } } } fmt.Println("Unsigned Lah numbers: l(n, k):") fmt.Printf("n/k") for i := 0; i <= last; i++ { fmt.Printf("%10d ", i) } fmt.Printf("\n--") for i := 0; i <= last; i++ { fmt.Printf("-----------") } fmt.Println() for n := 0; n <= last; n++ { fmt.Printf("%2d ", n) for k := 0; k <= n; k++ { fmt.Printf("%10d ", l[n][k]) } fmt.Println() } fmt.Println("\nMaximum value from the l(100, *) row:") max := new(big.Int).Set(l[limit][0]) for k := 1; k <= limit; k++ { if l[limit][k].Cmp(max) > 0 { max.Set(l[limit][k]) } } fmt.Println(max) fmt.Printf("which has %d digits.\n", len(max.String()))
}</lang>
- Output:
Unsigned Lah numbers: l(n, k): n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 ------------------------------------------------------------------------------------------------------------------------------------------------- 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the l(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000 which has 164 digits.
Haskell
<lang haskell>import Text.Printf (printf) import Control.Monad (when)
factorial :: Integral n => n -> n factorial 0 = 1 factorial n = product [1..n]
lah :: Integral n => n -> n -> n lah n k
| k == 1 = factorial n | k == n = 1 | k > n = 0 | k < 1 || n < 1 = 0 | otherwise = f n `div` f k `div` factorial (n - k) where f = (*) =<< (^ 2) . factorial . pred
printLah :: (Word, Word) -> IO () printLah (n, k) = do
when (k == 0) (printf "\n%3d" n) printf "%11d" (lah n k)
main :: IO () main = do
printf "Unsigned Lah numbers: L(n, k):\nn/k" mapM_ (printf "%11d") zeroToTwelve mapM_ printLah $ (,) <$> zeroToTwelve <*> zeroToTwelve printf "\nMaximum value from the L(100, *) row:\n%d\n" (maximum $ lah 100 <$> ([0..100] :: [Integer])) where zeroToTwelve = [0..12]</lang>
- Output:
Unsigned Lah numbers: L(n, k): n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 2 1 0 0 0 0 0 0 0 0 0 0 3 0 6 6 1 0 0 0 0 0 0 0 0 0 4 0 24 36 12 1 0 0 0 0 0 0 0 0 5 0 120 240 120 20 1 0 0 0 0 0 0 0 6 0 720 1800 1200 300 30 1 0 0 0 0 0 0 7 0 5040 15120 12600 4200 630 42 1 0 0 0 0 0 8 0 40320 141120 141120 58800 11760 1176 56 1 0 0 0 0 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 0 0 0 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 0 0 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 0 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the L(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
J
<lang J> NB. use: k lah n lah=: ! :(!&<: * %&!~)&x: NB. `%~' is shorter than `*inv'
NB. wory_lah translates lah to algebraic English. Monad =: :[: NB. permit only a y argument Dyad =: [: : NB. require x and y arguments but_1st =: & decrement =: <: Monad
NB. ! means either factorial or combinations (just as - means negate or subtract) factorial =: ! Monad combinations =: ! Dyad
into =: *inv Dyad times =: * Dyad extend_precision =: x: Monad wordy_lah =: ((combinations but_1st decrement) times (into but_1st factorial))but_1st extend_precision Dyad </lang>
lah&>~table~>:i.12 +------+---------------------------------------------------------------------------------------------------+ |lah&>~| 1 2 3 4 5 6 7 8 9 10 11 12| +------+---------------------------------------------------------------------------------------------------+ | 1 | 1 0 0 0 0 0 0 0 0 0 0 0| | 2 | 2 1 0 0 0 0 0 0 0 0 0 0| | 3 | 6 6 1 0 0 0 0 0 0 0 0 0| | 4 | 24 36 12 1 0 0 0 0 0 0 0 0| | 5 | 120 240 120 20 1 0 0 0 0 0 0 0| | 6 | 720 1800 1200 300 30 1 0 0 0 0 0 0| | 7 | 5040 15120 12600 4200 630 42 1 0 0 0 0 0| | 8 | 40320 141120 141120 58800 11760 1176 56 1 0 0 0 0| | 9 | 362880 1451520 1693440 846720 211680 28224 2016 72 1 0 0 0| |10 | 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 0 0| |11 | 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 0| |12 |479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1| +------+---------------------------------------------------------------------------------------------------+ wordy_lah f. [: :(([: :!&(<: :[:) [: :* [: :(*^:_1)&(! :[:))&(x: :[:)) lah NB. 1 or 2 arguments are clear from the context ! :(!&<: * %&!~)&x: (lah/ -: wordy_lah/)~>:i.12 NB. the lah and wordy_lah tables agree 1 NB. maximum Lah value with n = 100 >./(lah~ >:@:i.)100 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Java
<lang java> import java.math.BigInteger; import java.util.HashMap; import java.util.Map;
public class LahNumbers {
public static void main(String[] args) { System.out.println("Show the unsigned Lah numbers up to n = 12:"); for ( int n = 0 ; n <= 12 ; n++ ) { System.out.printf("%5s", n); for ( int k = 0 ; k <= n ; k++ ) { System.out.printf("%12s", lahNumber(n, k)); } System.out.printf("%n"); } System.out.println("Show the maximum value of L(100, k):"); int n = 100; BigInteger max = BigInteger.ZERO; for ( int k = 0 ; k <= n ; k++ ) { max = max.max(lahNumber(n, k)); } System.out.printf("%s", max); } private static Map<String,BigInteger> CACHE = new HashMap<>(); private static BigInteger lahNumber(int n, int k) { String key = n + "," + k; if ( CACHE.containsKey(key) ) { return CACHE.get(key); } // L(n,0) = 0; BigInteger result; if ( n == 0 && k == 0 ) { result = BigInteger.ONE; } else if ( k == 0 ) { result = BigInteger.ZERO; } else if ( k > n ) { result = BigInteger.ZERO; } else if ( n == 1 && k == 1 ) { result = BigInteger.ONE; } else { result = BigInteger.valueOf(n-1+k).multiply(lahNumber(n-1,k)).add(lahNumber(n-1,k-1)); } CACHE.put(key, result); return result; }
} </lang>
- Output:
Show the unsigned Lah numbers up to n = 12: 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Show the maximum value of L(100, k): 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Julia
<lang julia>using Combinatorics
function lah(n::Integer, k::Integer, signed=false)
if n == 0 || k == 0 || k > n return zero(n) elseif n == k return one(n) elseif k == 1 return factorial(n) else unsignedvalue = binomial(n, k) * binomial(n - 1, k - 1) * factorial(n - k) if signed && isodd(n) return -unsignedvalue else return unsignedvalue end end
end
function printlahtable(kmax)
println(" ", mapreduce(i -> lpad(i, 12), *, 0:kmax))
sstring(n, k) = begin i = lah(n, k); lpad(k > n && i == 0 ? "" : i, 12) end
for n in 0:kmax println(rpad(n, 2) * mapreduce(k -> sstring(n, k), *, 0:kmax)) end
end
printlahtable(12)
println("\nThe maxiumum of lah(100, _) is: ", maximum(k -> lah(BigInt(100), BigInt(k)), 1:100))
</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 The maxiumum of lah(100, _) is: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Kotlin
<lang scala>import java.math.BigInteger
fun factorial(n: BigInteger): BigInteger {
if (n == BigInteger.ZERO) return BigInteger.ONE if (n == BigInteger.ONE) return BigInteger.ONE var prod = BigInteger.ONE var num = n while (num > BigInteger.ONE) { prod *= num num-- } return prod
}
fun lah(n: BigInteger, k: BigInteger): BigInteger {
if (k == BigInteger.ONE) return factorial(n) if (k == n) return BigInteger.ONE if (k > n) return BigInteger.ZERO if (k < BigInteger.ONE || n < BigInteger.ONE) return BigInteger.ZERO return (factorial(n) * factorial(n - BigInteger.ONE)) / (factorial(k) * factorial(k - BigInteger.ONE)) / factorial(n - k)
}
fun main() {
println("Unsigned Lah numbers: L(n, k):") print("n/k ") for (i in 0..12) { print("%10d ".format(i)) } println() for (row in 0..12) { print("%-3d".format(row)) for (i in 0..row) { val l = lah(BigInteger.valueOf(row.toLong()), BigInteger.valueOf(i.toLong())) print("%11d".format(l)) } println() } println("\nMaximum value from the L(100, *) row:") println((0..100).map { lah(BigInteger.valueOf(100.toLong()), BigInteger.valueOf(it.toLong())) }.max())
}</lang>
- Output:
Unsigned Lah numbers: L(n, k): n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the L(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Perl
<lang perl>use strict; use warnings; use feature 'say'; use ntheory qw(factorial); use List::Util qw(max);
sub Lah {
my($n, $k) = @_; return factorial($n) if $k == 1; return 1 if $k == $n; return 0 if $k > $n; return 0 if $k < 1 or $n < 1; (factorial($n) * factorial($n - 1)) / (factorial($k) * factorial($k - 1)) / factorial($n - $k)
}
my $upto = 12; my $mx = 1 + length max map { Lah(12,$_) } 0..$upto;
say 'Unsigned Lah numbers: L(n, k):'; print 'n\k' . sprintf "%${mx}s"x(1+$upto)."\n", 0..1+$upto;
for my $row (0..$upto) {
printf '%-3d', $row; map { printf "%${mx}d", Lah($row, $_) } 0..$row; print "\n";
}
say "\nMaximum value from the L(100, *) row:"; say max map { Lah(100,$_) } 0..100;</lang>
- Output:
Unsigned Lah numbers: L(n, k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 Maximum value from the L(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Phix
<lang Phix>include mpfr.e
constant lim = 100,
lim1 = lim+1, last = 12
sequence l = repeat(0,lim1) for n=1 to lim1 do
l[n] = mpz_inits(lim1) mpz_set_si(l[n][n],1) if n!=2 then mpz_fac_ui(l[n][2],n-1) end if
end for mpz {t, m100} = mpz_inits(2) for n=1 to lim do
for k=1 to n do mpz_mul(t,l[n+1][2],l[n][2]) mpz_fdiv_q(t, t, l[k+1][2]) mpz_fdiv_q(t, t, l[k][2]) mpz_fdiv_q(l[n+1][k+1], t, l[n-k+1][2]) end for
end for printf(1,"Unsigned Lah numbers: l(n, k):\n n k:") for i=0 to last do
printf(1,"%6d ", i)
end for printf(1,"\n--- %s\n",repeat('-',last*11+6)) for n=0 to last do
printf(1,"%2d ", n) for k=1 to n+1 do mpfr_printf(1,"%10Zd ", l[n+1][k]) end for printf(1,"\n")
end for for k=1 to lim1 do
mpz l100k = l[lim1][k] if mpz_cmp(l100k,m100) > 0 then mpz_set(m100,l100k) end if
end for printf(1,"\nThe maximum l(100,k): %s\n",shorten(mpz_get_str(m100)))</lang>
- Output:
Unsigned Lah numbers: l(n, k): n k: 0 1 2 3 4 5 6 7 8 9 10 11 12 --- ------------------------------------------------------------------------------------------------------------------------------------------ 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 The maximum l(100,k): 4451900544899314481...0000000000000000000 (164 digits)
Prolog
<lang prolog>% Reference: https://en.wikipedia.org/wiki/Lah_number#Identities_and_relations
- - dynamic unsigned_lah_number_cache/3.
unsigned_lah_number(N, N, 1):-!. unsigned_lah_number(_, 0, 0):-!. unsigned_lah_number(N, K, 0):- K > N, !. unsigned_lah_number(N, K, L):- unsigned_lah_number_cache(N, K, L), !. unsigned_lah_number(N, K, L):- N1 is N - 1, K1 is K - 1, unsigned_lah_number(N1, K, L1), unsigned_lah_number(N1, K1, L2), !, L is (N1 + K) * L1 + L2, assertz(unsigned_lah_number_cache(N, K, L)).
print_unsigned_lah_numbers(N):- between(1, N, K), unsigned_lah_number(N, K, L), writef('%11r', [L]), fail. print_unsigned_lah_numbers(_):- nl.
print_unsigned_lah_numbers:- between(1, 12, N), print_unsigned_lah_numbers(N), fail. print_unsigned_lah_numbers.
max_unsigned_lah_number(N, Max):-
aggregate_all(max(L), (between(1, N, K), unsigned_lah_number(N, K, L)), Max).
main:- writeln('Unsigned Lah numbers up to L(12,12):'), print_unsigned_lah_numbers, writeln('Maximum value of L(n,k) where n = 100:'), max_unsigned_lah_number(100, M), writeln(M).</lang>
- Output:
Unsigned Lah numbers up to L(12,12): 1 2 1 6 6 1 24 36 12 1 120 240 120 20 1 720 1800 1200 300 30 1 5040 15120 12600 4200 630 42 1 40320 141120 141120 58800 11760 1176 56 1 362880 1451520 1693440 846720 211680 28224 2016 72 1 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value of L(n,k) where n = 100: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Python
<lang python>def factorial(n):
if n == 0: return 1 res = 1 while n > 0: res *= n n -= 1 return res
def lah(n,k):
if k == 1: return factorial(n) if k == n: return 1 if k > n: return 0 if k < 1 or n < 1: return 0 return (factorial(n) * factorial(n - 1)) / (factorial(k) * factorial(k - 1)) / factorial(n - k)
def main():
print "Unsigned Lah numbers: L(n, k):" print "n/k ", for i in xrange(13): print "%11d" % i, print for row in xrange(13): print "%-4d" % row, for i in xrange(row + 1): l = lah(row, i) print "%11d" % l, print print "\nMaximum value from the L(100, *) row:" maxVal = max([lah(100, a) for a in xrange(100)]) print maxVal
main()</lang>
- Output:
Unsigned Lah numbers: L(n, k): n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the L(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Raku
(formerly Perl 6)
<lang perl6>constant @factorial = 1, |[\*] 1..*;
sub Lah (Int \n, Int \k) {
return @factorial[n] if k == 1; return 1 if k == n; return 0 if k > n; return 0 if k < 1 or n < 1; (@factorial[n] * @factorial[n - 1]) / (@factorial[k] * @factorial[k - 1]) / @factorial[n - k]
}
my $upto = 12;
my $mx = (1..$upto).map( { Lah($upto, $_) } ).max.chars;
put 'Unsigned Lah numbers: L(n, k):'; put 'n\k', (0..$upto)».fmt: "%{$mx}d";
for 0..$upto -> $row {
$row.fmt('%-3d').print; put (0..$row).map( { Lah($row, $_) } )».fmt: "%{$mx}d";
}
say "\nMaximum value from the L(100, *) row:"; say (^100).map( { Lah 100, $_ } ).max;</lang>
- Output:
Unsigned Lah numbers: L(n, k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the L(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
REXX
Some extra code was added to minimize the column widths in the displaying of the numbers.
Also, code was added to use memoization of the factorial calculations. <lang rexx>/*REXX pgm computes & display (unsigned) Stirling numbers of the 3rd kind (Lah numbers).*/ parse arg lim . /*obtain optional argument from the CL.*/ if lim== | lim=="," then lim= 12 /*Not specified? Then use the default.*/ olim= lim /*save the original value of LIM. */ lim= abs(lim) /*only use the absolute value of LIM. */ numeric digits max(9, 4*lim) /*(over) specify maximum number in grid*/ max#.= 0 !.=. @.= /* [↓] calculate values for the grid. */
do n=0 to lim; nm= n - 1 do k=0 to lim; km= k - 1 if k==1 then do; @.n.k= !(n); call maxer; iterate; end if k==n then do; @.n.k= 1 ; iterate; end if k>n | k==0 | n==0 then do; @.n.k= 0 ; iterate; end @.n.k = (!(n) * !(nm)) % (!(k) * !(km)) % !(n-k) /*calculate a # in the grid.*/ call maxer /*find max # " " " */ end /*k*/ end /*n*/
do k=0 for lim+1 /*find max column width for each column*/ max#.a= max#.a + length(max#.k) end /*k*/ /* [↓] only show the maximum value ? */
w= length(max#.b) /*calculate max width of all numbers. */ if olim<0 then do; say 'The maximum value (which has ' w " decimal digits):"
say max#.b /*display maximum number in the grid. */ exit /*stick a fork in it, we're all done. */ end /* [↑] the 100th row is when LIM is 99*/
wi= max(3, length(lim+1) ) /*the maximum width of the grid's index*/ say 'row' center('columns', max(9, max#.a + lim), '═') /*display header of the grid.*/
do r=0 for lim+1; $= /* [↓] display the grid to the term. */ do c=0 for lim+1 until c>=r /*build a row of grid, 1 col at a time.*/ $= $ right(@.r.c, length(max#.c) ) /*append a column to a row of the grid.*/ end /*c*/ say right(r,wi) strip(substr($,2), 'T') /*display a single row of the grid. */ end /*r*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ !: parse arg z; if !.z\==. then return !.z; !=1; do f=2 to z; !=!*f; end; !.z=!; return ! maxer: max#.k= max(max#.k, @.n.k); max#.b= max(max#.b, @.n.k); return</lang>
- output when using the default input:
row ══════════════════════════════════════════════columns═══════════════════════════════════════════════ 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1
- output when using the input of: -100
The maximum value (which has 164 decimal digits): 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Sidef
<lang ruby>func lah(n, k) {
stirling3(n, k) #binomial(n-1, k-1) * n!/k! # alternative formula
}
const r = (0..12)
var triangle = r.map {|n| 0..n -> map {|k| lah(n, k) } } var widths = r.map {|n| r.map {|k| (triangle[k][n] \\ 0).len }.max }
say ('n\k ', r.map {|n| "%*s" % (widths[n], n) }.join(' '))
r.each {|n|
var str = ('%-3s ' % n) str += triangle[n].map_kv {|k,v| "%*s" % (widths[k], v) }.join(' ') say str
}
with (100) {|n|
say "\nMaximum value from the L(#{n}, *) row:" say { lah(n, _) }.map(^n).max
}</lang>
- Output:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the L(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Swift
<lang swift>import BigInt import Foundation
@inlinable public func factorial<T: BinaryInteger>(_ n: T) -> T {
guard n != 0 else { return 1 }
return stride(from: n, to: 0, by: -1).reduce(1, *)
}
@inlinable public func lah<T: BinaryInteger>(n: T, k: T) -> T {
if k == 1 { return factorial(n) } else if k == n { return 1 } else if k > n { return 0 } else if k < 1 || n < 1 { return 0 } else { let a = (factorial(n) * factorial(n - 1)) let b = (factorial(k) * factorial(k - 1)) let c = factorial(n - k)
return a / b / c }
}
print("Unsigned Lah numbers: L(n, k):") print("n\\k", terminator: "")
for i in 0...12 {
print(String(format: "%10d", i), terminator: " ")
}
print()
for row in 0...12 {
print(String(format: "%-2d", row), terminator: "")
for i in 0...row { lah(n: BigInt(row), k: BigInt(i)).description.withCString {str in print(String(format: "%11s", str), terminator: "") } }
print()
}
let maxLah = (0...100).map({ lah(n: BigInt(100), k: BigInt($0)) }).max()!
print("Maximum value from the L(100, *) row: \(maxLah)")</lang>
- Output:
Unsigned Lah numbers: L(n, k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Maximum value from the L(100, *) row: 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
Tcl
<lang Tcl>proc prod {from to} {
set r 1 if {$from <= $to} { set r $from while {[incr from] <= $to} { set r [expr {$r * $from}] } } return $r
}
proc US3 {n k} {
if {$n < 0 || $k < 0} { error "US3(): negative arg ($n,$k)" } ## L(0,0) = 1 ## L(n,0) = 0 if 0 < n ## L(0,k) = 0 if 0 < k ## L(n,k) = 0 if n < k ## L(n,n) = 1 if {$n == $k} { return 1 } if {$n == 0 || $k == 0} { return 0 } if {$n < $k} { return 0 }
set nk [list $n $k] if {[info exists ::US3cache($nk)]} { return $::US3cache($nk) } if {$k == 1} { ## L(n,1) = n! set r [prod 2 $n] } else { ## k > 1 ## L(n,k) = L(n,k-1) * (n - (k-1)) / ((k-1)*k) set k1 [expr {$k - 1}] set r [expr {([US3 $n $k1] * ($n - $k1)) / ($k * $k1)}] } set ::US3cache($nk) $r
}
proc main {} {
puts "Unsigned Lah numbers L(n,k):" set max 12 ;# last n,k to print set L 10 ;# space to use for 1 number set minn 1 ;# first row to print set mink 1 ;# first column to print puts -nonewline "n\\k" for {set n $minn} {$n <= $max} {incr n} { puts -nonewline " [format %${L}d $n]" } puts "" for {set n $minn} {$n <= $max} {incr n} { puts -nonewline [format %3d $n] for {set k $mink} {$k <= $n} {incr k} { puts -nonewline " [format %${L}s [US3 $n $k]]" } puts "" } set n 100 puts "The maximum value of L($n, k) = " set maxv 0 set maxk -1 for {set k 0} {$k <= $n} {incr k} { set v [US3 $n $k] if {$v > $maxv} { set maxv $v set maxk $k } } puts $maxv puts "([string length $maxv] digits, k=$maxk)"
} main </lang>
- Output:
Unsigned Lah numbers L(n,k): n\k 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 2 1 3 6 6 1 4 24 36 12 1 5 120 240 120 20 1 6 720 1800 1200 300 30 1 7 5040 15120 12600 4200 630 42 1 8 40320 141120 141120 58800 11760 1176 56 1 9 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 The maximum value of L(100, k) = 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000 (164 digits, k=10)
zkl
<lang zkl>fcn lah(n,k,fact=fcn(n){ [1..n].reduce('*,1) }){
if(n==k) return(1); if(k==1) return(fact(n)); if(n<1 or k<1) return(0); (fact(n)*fact(n - 1)) /(fact(k)*fact(k - 1)) /fact(n - k)
}</lang> <lang zkl>// calculate entire table (quick), find max, find num digits in max N,mx := 12, [1..N].apply(fcn(n){ [1..n].apply(lah.fp(n)) }).flatten() : (0).max(_); fmt:="%%%dd".fmt("%d".fmt(mx.numDigits + 1)).fmt; // "%9d".fmt println("Unsigned Lah numbers: L(n,k):"); println("n\\k",[0..N].pump(String,fmt)); foreach row in ([0..N]){
println("%3d".fmt(row), [0..row].pump(String, lah.fp(row), fmt));
}</lang>
- Output:
Unsigned Lah numbers: L(n,k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 1 0 1 2 0 2 1 3 0 6 6 1 4 0 24 36 12 1 5 0 120 240 120 20 1 6 0 720 1800 1200 300 30 1 7 0 5040 15120 12600 4200 630 42 1 8 0 40320 141120 141120 58800 11760 1176 56 1 9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1 10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1 12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1
GNU Multiple Precision Arithmetic Library
<lang zkl>var [const] BI=Import("zklBigNum"); // libGMP N=100; L100:=[1..N].apply(lah.fpM("101",BI(N),fcn(n){ BI(n).factorial() }))
.reduce(fcn(m,n){ m.max(n) });
println("Maximum value from the L(%d, *) row (%d digits):".fmt(N,L100.numDigits)); println(L100);</lang>
- Output:
Maximum value from the L(100, *) row (164 digits): 44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000