ANALYSIS of ALGORITHMS, Bulletin Board

# Generalized inversions.

```
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";
}
}
```

Date Prev | Date Next | Date Index | Thread Index