Generalized inversions.

[Marko Riedel <mriedel@neuearbeit.de>]

Greetings.

Consider all n-choose-k k-tuples of permutation indices < n, where 0,
1, ... n-1 are the elements being permuted. Let the k-tuple be ordered
in ascending order. Such a tuple is a k-inversion of a permutation p
if the k elements referenced by the indices are out of order.

Problems.

1. Use an elementary counting argument to show that the expected
number of k-inversions in a random permutation is

      k!-1  / n \
      ----  |   |
       k!   \ k /.

Verify this result by computing and evaluating the generating
functions of the k-inversions of a permutation of n elements, n>=k.

2. Compute additional statistics like the variance or factorial
moments.

3. The generating functions for ordinary inversions (k=2) factor very
nicely. What can you say about the factors of the generating functions 
when k>2? Is there a closed form product formula for the generating
functions for k>2?

Here are some sample data.

riedel@linuxfast:combinatorics > geninvs.pl 2
[0 1]
2 1 + z
1/2 0.5
[1 2] [0 2] [0 1]
3 1 + 2z + 2z^2 + z^3
9/6 1.5
[2 3] [1 3] [1 2] [0 3] [0 2] [0 1]
4 1 + 3z + 5z^2 + 6z^3 + 5z^4 + 3z^5 + z^6
72/24 3
riedel@linuxfast:combinatorics > geninvs.pl 3
[0 1 2]
3 1 + 5z
5/6 0.833333333333333
[1 2 3] [0 2 3] [0 1 3] [0 1 2]
4 1 + 3z^2 + 6z^3 + 14z^4
80/24 3.33333333333333
[2 3 4] [1 3 4] [1 2 4] [1 2 3] [0 3 4] [0 2 4] [0 2 3] [0 1 4] [0 1 3] [0 1 2]
5 1 + 4z^3 + 6z^5 + 9z^6 + 7z^7 + 24z^8 + 27z^9 + 42z^10
1000/120 8.33333333333333
[3 4 5] [2 4 5] [2 3 5] [2 3 4] [1 4 5] [1 3 5] [1 3 4] [1 2 5] [1 2 4] [1 2 3] 
[0 4 5] [0 3 5] [0 3 4] [0 2 5] [0 2 4] [0 2 3] [0 1 5] [0 1 4] [0 1 3] [0 1 2]
6 1 + 5z^4 + 8z^7 + 6z^8 + 6z^9 + 16z^10 + 12z^11 + 24z^12 + 32z^13 + 37z^14 + 5
4z^15 + 74z^16 + 70z^17 + 133z^18 + 110z^19 + 132z^20
12000/720 16.6666666666667
riedel@linuxfast:combinatorics > geninvs.pl 4
[0 1 2 3]
4 1 + 23z
23/24 0.958333333333333
[1 2 3 4] [0 2 3 4] [0 1 3 4] [0 1 2 4] [0 1 2 3]
5 1 + 4z^3 + 12z^4 + 103z^5
575/120 4.79166666666667
[2 3 4 5] [1 3 4 5] [1 2 4 5] [1 2 3 5] [1 2 3 4] [0 3 4 5] [0 2 4 5] [0 2 3 5] 
[0 2 3 4] [0 1 4 5] [0 1 3 5] [0 1 3 4] [0 1 2 5] [0 1 2 4] [0 1 2 3]
6 1 + 5z^6 + 8z^9 + 12z^10 + 6z^11 + 10z^12 + 63z^13 + 102z^14 + 513z^15
10350/720 14.375
[3 4 5 6] [2 4 5 6] [2 3 5 6] [2 3 4 6] [2 3 4 5] [1 4 5 6] [1 3 5 6] [1 3 4 6] 
[1 3 4 5] [1 2 5 6] [1 2 4 6] [1 2 4 5] [1 2 3 6] [1 2 3 5] [1 2 3 4] [0 4 5 6] 
[0 3 5 6] [0 3 4 6] [0 3 4 5] [0 2 5 6] [0 2 4 6] [0 2 4 5] [0 2 3 6] [0 2 3 5] 
[0 2 3 4] [0 1 5 6] [0 1 4 6] [0 1 4 5] [0 1 3 6] [0 1 3 5] [0 1 3 4] [0 1 2 6] 
[0 1 2 5] [0 1 2 4] [0 1 2 3]
7 1 + 6z^10 + 10z^16 + 18z^19 + 12z^20 + 13z^22 + 24z^24 + 32z^25 + 72z^26 + 10z
^27 + 46z^28 + 142z^29 + 116z^30 + 146z^31 + 196z^32 + 665z^33 + 770z^34 + 2761z
^35
169050/5040 33.5416666666667
[4 5 6 7] [3 5 6 7] [3 4 6 7] [3 4 5 7] [3 4 5 6] [2 5 6 7] [2 4 6 7] [2 4 5 7] 
[2 4 5 6] [2 3 6 7] [2 3 5 7] [2 3 5 6] [2 3 4 7] [2 3 4 6] [2 3 4 5] [1 5 6 7] 
[1 4 6 7] [1 4 5 7] [1 4 5 6] [1 3 6 7] [1 3 5 7] [1 3 5 6] [1 3 4 7] [1 3 4 6] 
[1 3 4 5] [1 2 6 7] [1 2 5 7] [1 2 5 6] [1 2 4 7] [1 2 4 6] [1 2 4 5] [1 2 3 7] 
[1 2 3 6] [1 2 3 5] [1 2 3 4] [0 5 6 7] [0 4 6 7] [0 4 5 7] [0 4 5 6] [0 3 6 7] 
[0 3 5 7] [0 3 5 6] [0 3 4 7] [0 3 4 6] [0 3 4 5] [0 2 6 7] [0 2 5 7] [0 2 5 6] 
[0 2 4 7] [0 2 4 6] [0 2 4 5] [0 2 3 7] [0 2 3 6] [0 2 3 5] [0 2 3 4] [0 1 6 7] 
[0 1 5 7] [0 1 5 6] [0 1 4 7] [0 1 4 6] [0 1 4 5] [0 1 3 7] [0 1 3 6] [0 1 3 5] 
[0 1 3 4] [0 1 2 7] [0 1 2 6] [0 1 2 5] [0 1 2 4] [0 1 2 3]
8 1 + 7z^15 + 12z^25 + 15z^29 + 10z^31 + 8z^34 + 28z^35 + 40z^38 + 41z^41 + 10z^42 + 24z^43 + 44z^44 + 84z^45 + 24z^46 + 89z^47 + 12z^49 + 142z^50 + 136z^51 + 96z^52 + 115z^53 + 333z^54 + 156z^55 + 112z^56 + 312z^57 + 199z^58 + 600z^59 + 573z^60 + 804z^61 + 503z^62 + 885z^63 + 1782z^64 + 1204z^65 + 2148z^66 + 2477z^67 + 5982z^68 + 5545z^69 + 15767z^70
2704800/40320 67.0833333333333


Regards,

Marko Riedel


----------------------------------------------------------------------

#! /usr/bin/perl -w
#

sub fact {
  my ($n) = @_;

  return 1 if $n==0 or $n==1;

  my ($p) = (1);
  $p*=$n-- while $n>1;

  return $p;
}

sub nchoosek {
  my ($n, $k) = @_;

  return fact($n)/fact($k)/fact($n-$k);
}

sub toarray {
  my ($n, $k, $index) = @_;
  my ($m, $l, $pos, $v, @b) = ($n, $k, 0); 

  while($m>$l){
    $v=nchoosek($m-1, $l);

    $m--;
    if($index>=$v){
      push @b, $pos;
      $l--;
      $index-=$v;
    }
    $pos++;
  }
  push @b, $pos++
    while $l-->0;

  return \@b;
}

sub nextperm {
  my ($n, $i, $j) = @_;
  my (@crep, $rem, @source, @perm, $item);
 
  for($j=1; $j<=$n; $j++){
    $rem=$i%$j;
    unshift @crep, $rem;
    $i=($i-$rem)/$j;
  }

  @source=(0..$n-1);
  for($j=0; $j<$n; $j++){
    $item=splice @source, $crep[$j], 1;
    push @perm, $item;
  }

  return \@perm;
}

sub invtuples {
  my ($n, $k) = @_;
  my ($i, @ituples);
  
  for($i=0; $i<nchoosek($n, $k); $i++){
    push @ituples, toarray($n, $k, $i);
  }

  return \@ituples;
}

sub inversions {
  my ($perm, $k, $ituples) = @_;
  my ($count, $i, $tuple) = (0);

  foreach $tuple (@$ituples){
    for($i=0; $i<$k-1; $i++){
      last if 
	$perm->[$tuple->[$i]]>$perm->[$tuple->[$i+1]];
    }
    $count++ if $i<$k-1;
  }

  return $count;
}

sub gf2string {
  my ($poly, @str, $term) = @_;

  foreach my $i ($poly->[0] .. $poly->[1]){
    if(defined $poly->[2][$i]){
      $term=($i == 0 ? '' : ($i == 1 ? 'z' : "z^$i"));
      push @str, 
      ($poly->[2][$i] == 1 ? 
       ($i==0 ? '1' : '') : "$poly->[2][$i]") .	$term;
    } 
  }

  return join ' + ', @str;
}

sub gfat1 {
  my ($poly, $total, $total1) = (@_, 0, 0);

  foreach my $i ($poly->[0] .. $poly->[1]){
    if(defined $poly->[2][$i]){
      $total  += $poly->[2][$i];
      $total1 += $i * $poly->[2][$i];
    }
  }

  return [$total1, $total];
}



MAIN: {
  my ($deg) = @ARGV;

  die "$0 <n>\n" if not defined $deg;

  for(my $n=$deg; $n<=2*$deg; $n++){
    my ($gf, $ituples, $invs) = 
      ([undef, undef, []], invtuples($n, $deg));

    print join ' ' , map {"[@$_]"} @$ituples;
    print "\n";

    for(my $i=0; $i<fact($n); $i++){
      $invs=inversions(nextperm($n, $i), $deg, $ituples);

      $gf->[0]=$invs 
	if not defined $gf->[0] or $gf->[0]>$invs;
      $gf->[1]=$invs 
	if not defined $gf->[1] or $gf->[1]<$invs;
      $gf->[2][$invs]=0 
	if not defined $gf->[2][$invs];
      $gf->[2][$invs]++;
    }

    print "$n " . gf2string($gf) . "\n";
    my ($at1, $f, $pred) = (gfat1($gf), fact($deg));
    print "$at1->[0]/$at1->[1] ";
    $pred=nchoosek($n, $deg)*($f-1)/$f;
    print "$pred\n";
  }
}