[seqfan] perms and set partitions

Joerg Arndt arndt at jjj.de
Mon Jun 8 04:00:16 CEST 2009


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?




More information about the SeqFan mailing list