Opened 4 years ago

Last modified 4 years ago

#17161 new enhancement

Implement the unsigned Lah numbers

Reported by: pluschny Owned by:
Priority: minor Milestone: sage-6.4
Component: combinatorics Keywords: Lah numbers
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Implement the unsigned Lah numbers which for n>=1, k>=1 are the number of ways a set of n elements can be partitioned into k nonempty linearly ordered subsets.

Lah numbers are defined for all integers n, k by the following formula if the Stirling numbers are extended to negative integers n, k in the way it is recommended by Graham/Knuth/Patashnik? in 'Concrete Mathematics' Section 6.1 (see Table 253). (This extension is implemented in GAP’s Stirling functions.)

def Lah(n,k):
    return sum(stirling_number1(n,j)*stirling_number2(j,k,"gap") for j in (k..n))

(Note how inconsistently at present this formula has to be written to get consistent results (because stirling_number1 and stirling_number2 are based on different, non-compatible algorithms! See also ticket #17159)

for n in (-6..6):
    print [Lah(n,k) for k in (-6..6)]    

    1,   .,  ., ., ., ., .,   .,    .,    .,   .,  ., .,
   30,   1,  ., ., ., ., .,   .,    .,    .,   .,  ., .,
  300,  20,  1, ., ., ., .,   .,    .,    .,   .,  ., .,
 1200, 120, 12, 1, ., ., .,   .,    .,    .,   .,  ., .,
 1800, 240, 36, 6, 1, ., .,   .,    .,    .,   .,  ., .,
  720, 120, 24, 6, 2, 1, .,   .,    .,    .,   .,  ., .,
    .,   .,  ., ., ., ., 1,   .,    .,    .,   .,  ., .,
    .,   .,  ., ., ., ., .,   1,    .,    .,   .,  ., .,
    .,   .,  ., ., ., ., .,   2,    1,    .,   .,  ., .,
    .,   .,  ., ., ., ., .,   6,    6,    1,   .,  ., .,
    .,   .,  ., ., ., ., .,  24,   36,   12,   1,  ., .,
    .,   .,  ., ., ., ., ., 120,  240,  120,  20,  1, .,
    .,   .,  ., ., ., ., ., 720, 1800, 1200, 300, 30, 1,

Change History (1)

comment:1 Changed 4 years ago by pluschny

A possible implementation could be based on:

def lah_number(n, k):
    if n == k: return 1
    if n<0 and k<0: return lah_number(-k, -n)
    if k<0 or  k>n: return 0    
    return (k*n*gamma(n)^2)/(gamma(k+1)^2*gamma(n-k+1))
Note: See TracTickets for help on using tickets.