A003316

[Olivier Gerard]

David, if you re read the definition you will understand it better:

1 = 1*1
3 = 2*1 + 1
12 = 3*1 + 4*2 + 1
55 = 4*1 + 6*3 + 16*2 + 1

etc...

Olivier


On Fri, Sep 07, 2001 at 09:29:52AM -0400, David W. Wilson wrote:
> 
> 
> %N A003316 Sum of lengths of longest increasing subsequences of all permutations
>  of n elements.
> %S A003316 1,3,12,58,335,2261,17465,152020,1473057,15730705,183571817,
> %T A003316 2324298010,31737207026,464904410985,7272666016725,121007866402968
> 
> When I classify permutations by longest increasing subsequence, I get
> 
>      n     1     2     3     4     5     6     7 perms   sum
>      1     1                                         1     1
>      2     1     1                                   2     3
>      3     1     4     1                             6    12
>      4     1    16     6     1                      24    55
>      5     1    69    41     8     1               120   299
>      6     1   348   293    67    10     1         720  1900
>      7     1  2016  2309   602    99    12     1  5040 13942
> 
> My table is in agreement with A008304, but my sums are not in agreement
> with A003316 above.
>