ANALYSIS of ALGORITHMS, Bulletin Board

# Quickselect and generalized inversions. (III)

```helmut@gauss.cam.wits.ac.za writes:
> On 26 Jul 2001, at 23:28, Marko Riedel wrote:
>
> >
> > Greetings.
> >
> > Question: what is the pattern in the number of QI inversions? Here are
> > the first few values:
> >
> > 2 1 1
> > 3 3 3
> > 4 13 11
> > 5 71 49
> > 6 461 259
> > 7 3447 1593
> > 8 29093 11227
>
> not enough data for successful guessing...HP
>

Greetings.

Here is the data that you asked for. The recursion is implicit in the
Perl program and was not that hard to find. This sequence is listed in
"The On-Line Encyclopedia of Integer Sequences" at

http://www.research.att.com/~njas/sequences/index.html.

I would also appreciate it if someone were to check the references
given in the encyclopedia, let me know if my recursion formula is
already known and explain how it relates to the construction that is
listed in the encyclopedia.

Best regards,

Marko Riedel

Reference:
http://pauillac.inria.fr/algo/AofA/mailing_list/msg00534.html

----------------------------------------------------------------------
2 +1 +1
1: +1
3 +3 +3
1: +2
2: +1
4 +13 +11
1: +6
2: +2
3: +3
5 +71 +49
1: +24
2: +6
3: +6
4: +13
6 +461 +259
1: +120
2: +24
3: +18
4: +26
5: +71
7 +3447 +1593
1: +720
2: +120
3: +72
4: +78
5: +142
6: +461
8 +29093 +11227
1: +5040
2: +720
3: +360
4: +312
5: +426
6: +922
7: +3447
9 +273343 +89537
1: +40320
2: +5040
3: +2160
4: +1560
5: +1704
6: +2766
7: +6894
8: +29093
10 +2829325 +799475
1: +362880
2: +40320
3: +15120
4: +9360
5: +8520
6: +11064
7: +20682
8: +58186
9: +273343
11 +31998903 +7917897
1: +3628800
2: +362880
3: +120960
4: +65520
5: +51120
6: +55320
7: +82728
8: +174558
9: +546686
10: +2829325
12 +392743957 +86257643
1: +39916800
2: +3628800
3: +1088640
4: +524160
5: +357840
6: +331920
7: +413640
8: +698232
9: +1640058
10: +5658650
11: +31998903
13 +5201061455 +1025959345
1: +479001600
2: +39916800
3: +10886400
4: +4717440
5: +2862720
6: +2323440
7: +2481840
8: +3491160
9: +6560232
10: +16975950
11: +63997806
12: +392743957
14 +73943424413 +13234866787
1: +6227020800
2: +479001600
3: +119750400
4: +47174400
5: +25764480
6: +18587520
7: +17372880
8: +20946960
9: +32801160
10: +67903800
11: +191993418
12: +785487914
13: +5201061455
15 +1123596277863 +184078090137
1: +87178291200
2: +6227020800
3: +1437004800
4: +518918400
5: +257644800
6: +167287680
7: +138983040
8: +146628720
9: +196806960
10: +339519000
11: +767973672
12: +2356463742
13: +10402122910
14: +73943424413
16 +18176728317413 +2746061570587
1: +1307674368000
2: +87178291200
3: +18681062400
4: +6227020800
5: +2834092800
6: +1672876800
7: +1250847360
8: +1173029760
9: +1377648720
10: +2037114000
11: +3839868360
12: +9425854968
13: +31206368730
14: +147886848826
15: +1123596277863
17 +311951144828863 +43736283267137
1: +20922789888000
2: +1307674368000
3: +261534873600
4: +80951270400
5: +34009113600
6: +18401644800
7: +12508473600
8: +10557267840
9: +11021189760
10: +14259798000
11: +23039210160
12: +47129274840
13: +124825474920
14: +443660546478
15: +2247192555726
16: +18176728317413
18 +5661698774848621 +740674930879379
1: +355687428096000
2: +20922789888000
3: +3923023104000
4: +1133317785600
5: +442118476800
6: +220819737600
7: +137593209600
8: +105572678400
9: +99190707840
10: +114078384000
11: +161274471120
12: +282775649040
13: +624127374600
14: +1774642185912
15: +6741577667178
16: +36353456634826
17: +311951144828863
19 +108355864447215063 +13289235961616937
1: +6402373705728000
2: +355687428096000
3: +62768369664000
4: +16999766784000
5: +6189658675200
6: +2870656588800
7: +1651118515200
8: +1161299462400
9: +991907078400
10: +1026705456000
11: +1290195768960
12: +1979429543280
13: +3744764247600
14: +8873210929560
15: +26966310668712
16: +109060369904478
17: +623902289657726
18: +5661698774848621
20 +2181096921557783605 +251805086618856395
1: +121645100408832000
2: +6402373705728000
3: +1067062284288000
4: +271996268544000
5: +92844880128000
6: +40189192243200
7: +21464540697600
8: +13935593548800
9: +10910977862400
10: +10267054560000
11: +11611761920640
12: +15835436346240
13: +26213349733200
14: +53239265577360
15: +134831553343560
16: +436241479617912
17: +1871706868973178
18: +11323397549697242
19: +108355864447215063
21 +46066653228356851631 +5024288943352588369
1: +2432902008176640000
2: +121645100408832000
3: +19207121117184000
4: +4623936565248000
5: +1485518082048000
6: +602837883648000
7: +300503569766400
8: +181162716134400
9: +130931734348800
10: +112937600160000
11: +116117619206400
12: +142518927116160
13: +209706797865600
14: +372674859041520
15: +808989320061360
16: +2181207398089560
17: +7486827475892712
18: +33970192649091726
19: +216711728894430126
20: +2181096921557783605
22 +1018705098450570562877 +105295629327037117123
1: +51090942171709440000
2: +2432902008176640000
3: +364935301226496000
4: +83230858174464000
5: +25253807394816000
6: +9645406138368000
7: +4507553546496000
8: +2536278025881600
9: +1702112546534400
10: +1355251201920000
11: +1277293811270400
12: +1425189271161600
13: +1887361180790400
14: +2981398872332160
15: +5662925240429520
16: +13087244388537360
17: +37434137379463560
18: +135880770596366904
19: +650135186683290378
20: +4362193843115567210
21: +46066653228356851631
23 +23539631662517304379719 +2312385076367672260281
1: +1124000727777607680000
2: +51090942171709440000
3: +7298706024529920000
4: +1581386305314816000
5: +454568533106688000
6: +163971904352256000
7: +72120856743936000
8: +38044170388224000
9: +23829575651481600
10: +17618265624960000
11: +15327525735244800
12: +15677081982777600
13: +18873611807904000
14: +26832589850989440
15: +45303401923436160
16: +91610710719761520
17: +224604824276781360
18: +679403852981834520
19: +2600540746733161512
20: +13086581529346701630
21: +92133306456713703262
22: +1018705098450570562877
24 +567347013156626397484421 +53101388576613041875579
1: +25852016738884976640000
2: +1124000727777607680000
3: +153272826515128320000
4: +31627726106296320000
5: +8636802129027072000
6: +2951494278340608000
7: +1226054564646912000
8: +608706726211584000
9: +357443634772224000
10: +246655718749440000
11: +199257834558182400
12: +188124983793331200
13: +207609729886944000
14: +268325898509894400
15: +407730617310925440
16: +732885685758092160
17: +1572233769937469520
18: +4076423117891007120
19: +13002703733665807560
20: +52346326117386806520
21: +276399919370141109786
22: +2037410196901141125754
23: +23539631662517304379719
----------------------------------------------------------------------
#! /usr/bin/perl -w
#

use Math::BigInt;

{ my (@table);
sub qiinvs {
my (\$n) = @_;

if(not defined \$table[\$n]){
if(\$n==2){
\$table[\$n] =  # QI, NQI
[(new Math::BigInt '1'),
(new Math::BigInt '1')];
}
else{
my (\$prev, @cur, \$i) =
(qiinvs(\$n-1), (new Math::BigInt '0') x \$n);

\$cur[0] = \$prev->[0]*(\$n - 1);
\$cur[\$n-1] = \$prev->[0];

for(\$i=1; \$i<=\$n-2; \$i++){
\$cur[0]  += \$prev->[\$i]*\$i;
\$cur[\$i] += \$prev->[\$i]*(\$n - \$i);
}

\$table[\$n] = \@cur;
}
}

return \$table[\$n];
}
}

MAIN: {
my (\$upper) = @ARGV;

if(not defined \$upper or
\$upper < 2){
print "\$0 <upper> where <upper> > 1\n";
exit -1;
}

for(my \$n=2; \$n<=\$upper; \$n++){
my (\$dist, \$sum, \$k) = (qiinvs(\$n), 0);

map { \$sum += \$_ } @\$dist[1..\$#\$dist];
print "\$n \$dist->[0] \$sum\n";
for(\$k=1; \$k<=\$#\$dist; \$k++){
print "   \$k: \$dist->[\$k]\n";
}
}
}
```

Date Prev | Date Next | Date Index | Thread Index