[seqfan] Re: perms and set partitions

[franktaw at netscape.net]

The sum A(n,0) + A(n,1) matches A005802 (Number of permutations in S_n 
with longest increasing subsequence of length <= 3) through n=5, but 
then diverges.

Franklin T. Adams-Watters

-----Original Message-----
From: Joerg Arndt <arndt at jjj.de>

Let ne be the excedance of a permutation p
(i.e. number of positions j where p(j)>j).

Let nt be the (minimal) number of transpositions of p.

We have nt >= ne,  set m:=nt-ne

Let A(n,m) be the number of length-n permutations
with m==nt-ne.  We obtain the following triangle

n:   A(n,0)   A(n,1)   A(n,2)   etc.
1:       1,
2:       2,     0,
3:       5,     1,      0,
4:      15,     8,      1,     0,
5:      52,    51,     16,     1,     0,
6:     203,   312,    172,    32,     1,    0,
7:     877,  1926,   1611,   561,    64,    1,   0,
8:    4140, 12224,  14289,  7744,  1794,  128,   1,  0,
9:   21147, 80401, 124410, 95255, 35755, 5655, 256,  1,  0,

Leftmost column appears to be:
  A000110 Bell or exponential numbers

Is there a combinatorial interpretation of this table?


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/