# A003316

David W. Wilson wilson at aprisma.com
Fri Sep 7 16:31:36 CEST 2001

```Olivier Gerard wrote:
>
> David, if you re read the definition you will understand it better:
>
> 1 = 1*1
> 3 = 2*1 + 1*1
> 12 = 3*1 + 4*2 + 1*1
> 55 = 4*1 + 6*3 + 16*2 + 1*1
> etc...

Precisely.  I get a(4) = 55 whereas the current sequence has a(4) = 58.
So where does the 58 come from?

>
> 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.
> >

```