[seqfan] Re: perms and set partitions

[Joerg Arndt]

* Joerg Arndt <arndt at jjj.de> [Jun 08. 2009 12:00]:
> [...]
> 
> Is there a combinatorial interpretation of this table?

Well, m==0 are the permutations whose cycle form is a
valid set partition (elements in cycles increasing),
m==1 has one decreasing part in some cycle, etc.:

With n==4, we have (omitting fixed points from cycle form,
lex order):

   0:    [ 0 1 2 3 ]    nt=0  ne=0  m=0   
   1:    [ 0 1 3 2 ]    nt=1  ne=1  m=0    (2, 3)
   2:    [ 0 2 1 3 ]    nt=1  ne=1  m=0    (1, 2)
   3:    [ 0 2 3 1 ]    nt=2  ne=2  m=0    (1, 2, 3)
   4:    [ 0 3 1 2 ]    nt=2  ne=1  m=1    (1, 3, 2)
   5:    [ 0 3 2 1 ]    nt=1  ne=1  m=0    (1, 3)
   6:    [ 1 0 2 3 ]    nt=1  ne=1  m=0    (0, 1)
   7:    [ 1 0 3 2 ]    nt=2  ne=2  m=0    (0, 1) (2, 3)
   8:    [ 1 2 0 3 ]    nt=2  ne=2  m=0    (0, 1, 2)
   9:    [ 1 2 3 0 ]    nt=3  ne=3  m=0    (0, 1, 2, 3)
  10:    [ 1 3 0 2 ]    nt=3  ne=2  m=1    (0, 1, 3, 2)
  11:    [ 1 3 2 0 ]    nt=2  ne=2  m=0    (0, 1, 3)
  12:    [ 2 0 1 3 ]    nt=2  ne=1  m=1    (0, 2, 1)
  13:    [ 2 0 3 1 ]    nt=3  ne=2  m=1    (0, 2, 3, 1)
  14:    [ 2 1 0 3 ]    nt=1  ne=1  m=0    (0, 2)
  15:    [ 2 1 3 0 ]    nt=2  ne=2  m=0    (0, 2, 3)
  16:    [ 2 3 0 1 ]    nt=2  ne=2  m=0    (0, 2) (1, 3)
  17:    [ 2 3 1 0 ]    nt=3  ne=2  m=1    (0, 2, 1, 3)
  18:    [ 3 0 1 2 ]    nt=3  ne=1  m=2    (0, 3, 2, 1)
  19:    [ 3 0 2 1 ]    nt=2  ne=1  m=1    (0, 3, 1)
  20:    [ 3 1 0 2 ]    nt=2  ne=1  m=1    (0, 3, 2)
  21:    [ 3 1 2 0 ]    nt=1  ne=1  m=0    (0, 3)
  22:    [ 3 2 0 1 ]    nt=3  ne=2  m=1    (0, 3, 1, 2)
  23:    [ 3 2 1 0 ]    nt=2  ne=2  m=0    (0, 3) (1, 2)

stats: 15, 8, 1, 0,   tot=24