[jira] [Commented] (NUMBERS-191) Stirling number of the first kind

["Alex Herbert (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/NUMBERS-191?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17631034#comment-17631034 ] 

Alex Herbert commented on NUMBERS-191:
--------------------------------------

Some useful [simple s1 identities|https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind#Simple_identities] are listed on Wikipedia:
{noformat}
s(n, n-1) = -binom(n, 2)
s(n, n-2) = (3n-1) * binom(n, 3) / 4
s(n, n-3) = -binom(n, 2) * binom(n, 4)
{noformat}
Where {{binom}} is the binomial coefficient. These are useful as these cases allow large n and computation using recursion requires many iterations. The limits of a 64-bit long are:
{noformat}
// Upper limits for n with k in [n-9, n-1]
35, 26, -5576855646887454930
44, 36, 6364808704290634598
61, 54, -8424028440309413250
95, 89, 8864929183170733205
181, 176, -8872439767850041020
495, 491, 9161199664152744351
2761, 2758, -9205676356399769400
92682, 92680, 9223080114771128550
2147483647, 2147483646, -2305843005992468481{noformat}
Care must be taken when computing {{(3n-1) * binom(n, 3) / 4}} to avoid intermediate overflow. This can be done by dividing an even mutiplicand by 2, and their product by 2, e.g.
{noformat}
long a = ...
long b = ...
return (b & 1) == 0
  ? ((b >>> 1) * a) >>> 1
  : ((a >>> 1) * b) >>> 1;{noformat}
 

> Stirling number of the first kind
> ---------------------------------
>
>                 Key: NUMBERS-191
>                 URL: https://issues.apache.org/jira/browse/NUMBERS-191
>             Project: Commons Numbers
>          Issue Type: New Feature
>          Components: combinatorics
>    Affects Versions: 1.1
>            Reporter: Alex Herbert
>            Assignee: Alex Herbert
>            Priority: Minor
>             Fix For: 1.2
>
>
> Add computation of the [Stirling number of the first kind|https://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html]: s(n, k).
> This can be performed using the recurrence relation:
> {noformat}
> s(n + 1, k) = s(n, k - 1) - n * s(n, k)
> {noformat}



--
This message was sent by Atlassian Jira
(v8.20.10#820010)