Parking functions, part deux

435 days ago by butler

def green(pref): n = len(pref) spots = set(range(n)) good = [] for i in range(n): x=pref[i] y = min(set(range(x,n)).intersection(spots)) if y == x: good.append([i,x]) spots.discard(y) return good 
       
for n in [1..8]: PF = [0]*n orderedcount = 0 tallys = matrix(n) #all_parking = matrix(n) while True: for C in Permutations(PF): #for i in range(n): # all_parking[i,C[i]]+=1 q = green(C) for s in q: tallys[s[0],s[1]]+=1 for i in range (n): if PF[i]<n-1-i: PF[i] += 1 for j in range(i): PF[j] = PF[i] break else: break print " n =",n,"\n", tallys, "\n\n Row sums\n",list(tallys*vector([1]*n)), "\n\n Column sums\n",list(tallys.transpose()*vector([1]*n)), "\n====================\n" 
        
  n = 1 
[1] 

 Row sums
[1] 

 Column sums
[1] 
====================

  n = 2 
[2 1]
[1 1] 

 Row sums
[3, 2] 

 Column sums
[3, 2] 
====================

  n = 3 
[8 5 3]
[5 4 3]
[3 2 3] 

 Row sums
[16, 12, 8] 

 Column sums
[16, 11, 9] 
====================

  n = 4 
[50 34 25 16]
[35 27 22 16]
[24 17 18 16]
[16  9  9 16] 

 Row sums
[125, 100, 75, 50] 

 Column sums
[125, 87, 74, 64] 
====================

  n = 5 
[432 307 243 189 125]
[324 249 209 173 125]
[240 176 169 154 125]
[175 112 108 128 125]
[125  64  54  64 125] 

 Row sums
[1296, 1080, 864, 648, 432] 

 Column sums
[1296, 908, 783, 708, 625] 
====================

  n = 6 
[4802 3506 2881 2401 1921 1296]
[3773 2909 2484 2148 1796 1296]
[2940 2204 2042 1868 1655 1296]
[2268 1555 1467 1532 1486 1296]
[1728 1025  912  992 1250 1296]
[1296  625  480  480  625 1296] 

 Row sums
[16807, 14406, 12005, 9604, 7203, 4802] 

 Column sums
[16807, 11824, 10266, 9421, 8733, 7776] 
====================

  n = 7 
[65536 48729 40953 35328 30208 24583 16807]
[53248 41243 35627 31502 27662 23287 16807]
[43008 32728 29869 27406 24924 21866 16807]
[34496 24660 22967 22788 21866 20256 16807]
[27440 17712 16055 16608 18138 18312 16807]
[21609 12096 10125 10240 11875 15552 16807]
[16807  7776  5625  5120  5625  7776 16807] 

 Row sums
[262144, 229376, 196608, 163840, 131072, 98304, 65536] 

 Column sums
[262144, 184944, 161221, 148992, 140298, 131632, 117649] 
====================

  n = 8 
[1062882  800738  683089  601441  531441  461441  379793  262144]
[ 885735  689127  600290  538082  484082  429082  362986  262144]
[ 734832  565228  512346  471483  434323  394848  344883  262144]
[ 606528  445669  411849  398940  380692  357840  324984  262144]
[ 497664  338982  309528  310744  319586  316200  302357  262144]
[ 405504  248675  216648  217400  235755  264768  274870  262144]
[ 327680  175273  139968  134000  145000  174960  235298  262144]
[ 262144  117649   81648   70000   70000   81648  117649  262144] 

 Row sums
[4782969, 4251528, 3720087, 3188646, 2657205, 2125764, 1594323, 1062882]


 Column sums
[4782969, 3381341, 2955366, 2742090, 2600879, 2480787, 2342820, 2097152]

====================
  n = 1 
[1] 

 Row sums
[1] 

 Column sums
[1] 
====================

  n = 2 
[2 1]
[1 1] 

 Row sums
[3, 2] 

 Column sums
[3, 2] 
====================

  n = 3 
[8 5 3]
[5 4 3]
[3 2 3] 

 Row sums
[16, 12, 8] 

 Column sums
[16, 11, 9] 
====================

  n = 4 
[50 34 25 16]
[35 27 22 16]
[24 17 18 16]
[16  9  9 16] 

 Row sums
[125, 100, 75, 50] 

 Column sums
[125, 87, 74, 64] 
====================

  n = 5 
[432 307 243 189 125]
[324 249 209 173 125]
[240 176 169 154 125]
[175 112 108 128 125]
[125  64  54  64 125] 

 Row sums
[1296, 1080, 864, 648, 432] 

 Column sums
[1296, 908, 783, 708, 625] 
====================

  n = 6 
[4802 3506 2881 2401 1921 1296]
[3773 2909 2484 2148 1796 1296]
[2940 2204 2042 1868 1655 1296]
[2268 1555 1467 1532 1486 1296]
[1728 1025  912  992 1250 1296]
[1296  625  480  480  625 1296] 

 Row sums
[16807, 14406, 12005, 9604, 7203, 4802] 

 Column sums
[16807, 11824, 10266, 9421, 8733, 7776] 
====================

  n = 7 
[65536 48729 40953 35328 30208 24583 16807]
[53248 41243 35627 31502 27662 23287 16807]
[43008 32728 29869 27406 24924 21866 16807]
[34496 24660 22967 22788 21866 20256 16807]
[27440 17712 16055 16608 18138 18312 16807]
[21609 12096 10125 10240 11875 15552 16807]
[16807  7776  5625  5120  5625  7776 16807] 

 Row sums
[262144, 229376, 196608, 163840, 131072, 98304, 65536] 

 Column sums
[262144, 184944, 161221, 148992, 140298, 131632, 117649] 
====================

  n = 8 
[1062882  800738  683089  601441  531441  461441  379793  262144]
[ 885735  689127  600290  538082  484082  429082  362986  262144]
[ 734832  565228  512346  471483  434323  394848  344883  262144]
[ 606528  445669  411849  398940  380692  357840  324984  262144]
[ 497664  338982  309528  310744  319586  316200  302357  262144]
[ 405504  248675  216648  217400  235755  264768  274870  262144]
[ 327680  175273  139968  134000  145000  174960  235298  262144]
[ 262144  117649   81648   70000   70000   81648  117649  262144] 

 Row sums
[4782969, 4251528, 3720087, 3188646, 2657205, 2125764, 1594323, 1062882] 

 Column sums
[4782969, 3381341, 2955366, 2742090, 2600879, 2480787, 2342820, 2097152] 
====================