Lah numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|REXX}}: truncated column at k == 1)
m (→‎{{header|REXX}}: added code to guarantee enough width to show the header for the columns (for small grids), fixed the omission of finding the maximum column width where K=1.)
Line 231: Line 231:


=={{header|REXX}}==
=={{header|REXX}}==
{{improve|REXX|The column where k equals 1 seems to have been truncated to a single digit}}
<lang rexx>/*REXX pgm computes & display (unsigned) Stirling numbers of the 3rd kind (Lah numbers).*/
<lang rexx>/*REXX pgm computes & display (unsigned) Stirling numbers of the 3rd kind (Lah numbers).*/
parse arg lim . /*obtain optional argument from the CL.*/
parse arg lim . /*obtain optional argument from the CL.*/
Line 243: Line 242:
do n=0 to lim; nm= n - 1
do n=0 to lim; nm= n - 1
do k=0 to lim; km= k - 1
do k=0 to lim; km= k - 1
if k==1 then do; @.n.k= !(n); iterate; end
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 then do; @.n.k= 1 ; iterate; end
if k>n | k==0 | n==0 then do; @.n.k= 0 ; 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.*/
@.n.k = (!(n) * !(nm)) % (!(k) * !(km)) % !(n-k) /*calculate a # in the grid.*/
max#.k= max(max#.k, @.n.k) /*find max # " " " */
call maxer /*find max # " " " */
max#.b= max(max#.b, @.n.k) /*find the maximum value for all rows. */
end /*k*/
end /*k*/
end /*n*/
end /*n*/
Line 262: Line 260:
end /* [↑] the 100th row is when LIM is 99*/
end /* [↑] the 100th row is when LIM is 99*/
wi= max(3, length(lim+1) ) /*the maximum width of the grid's index*/
wi= max(3, length(lim+1) ) /*the maximum width of the grid's index*/
say 'row' center('columns', max#.a + lim, '═') /*display the header of the grid. */
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 r=0 for lim+1; $= /* [↓] display the grid to the term. */
Line 272: Line 270:
exit /*stick a fork in it, we're all done. */
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 !</lang>
!: 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>
{{out|output|text=&nbsp; when using the default input:}}
{{out|output|text=&nbsp; when using the default input:}}
<pre>
<pre>
row ══════════════════════════════════════════════columns═══════════════════════════════════════════════
row ══════════════════════════════════════════columns═══════════════════════════════════════════
0 1
0 1
1 0 1
1 0 1
2 0 2 1
2 0 2 1
3 0 6 6 1
3 0 6 6 1
4 0 4 36 12 1
4 0 24 36 12 1
5 0 0 240 120 20 1
5 0 120 240 120 20 1
6 0 0 1800 1200 300 30 1
6 0 720 1800 1200 300 30 1
7 0 0 15120 12600 4200 630 42 1
7 0 5040 15120 12600 4200 630 42 1
8 0 0 141120 141120 58800 11760 1176 56 1
8 0 40320 141120 141120 58800 11760 1176 56 1
9 0 0 1451520 1693440 846720 211680 28224 2016 72 1
9 0 362880 1451520 1693440 846720 211680 28224 2016 72 1
10 0 0 16329600 21772800 12700800 3810240 635040 60480 3240 90 1
10 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1
11 0 0 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1
11 0 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1
12 0 0 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1
12 0 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1
</pre>
</pre>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> -100 </tt>}}
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> -100 </tt>}}

Revision as of 19:18, 16 August 2019

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



Factor

Works with: Factor version 0.99 development version 2019-07-10

<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

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.

Perl 6

Works with: Rakudo version 2019.07.1

<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

<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
Retrieved from "https://rosettacode.org/wiki/Lah_numbers?oldid=292641"