def MT2(nn):
t=nn-2 # number degree 2 vertices
# states are (0,1), (1,k) and (2,k) where first coordinate i means i of u and v are blue and k = 1,...,t is the # of blue degree 2 vertices
m=zero_matrix(RR,2*t+1) # m is the matrix; use QQ for exact, RR for decimal
d=nn-1 # degree of u and v
# row zero is state (0,1), i.e., neither of u or v blue
# all other states are same.
# the degree 2 blue vertex can force 0, 1, or 2 of u and v
m[0,0]=1/4
m[0,1]=1/2
m[0,t+1]=1/4
# forcing with u blue and v white
# starting with u blue v white, state (1,k) is matrix index k, k=1,...,t
# v will become blue by being forced by a degree 2 vertex
for k in [1..t-1]:
pfu=(k+1)/d # probability of u forcing any one specific vertex
pnfu=1-pfu # probability of u not forcing any one specific verte
for r in [0..t-k]: # r is the number of new blue degree 2 vertices
m[k,t+k+r]=binomial(t-k,r)*pfu^r*pnfu^(t-k-r) # r degree 2 vertices forced
m[t,t+t]=1
# starting with u and v both blue, state (2,k) is matrix index t+1+k, k=0,...,t
for k in [0..t-2]:
pfuv=(k+2)/d # probability of u forcing any one specific degree 2 vertex (same for v)
pnfuv=1-pfuv # probability of u not forcing any one specific degree 2 vertex (same for v)
pnf = (1-pfuv)^2 # probability of neither u nor v forcing any one specific degree 2 vertex
pf = 1-(1-pfuv)^2 # probability any one specific degree 2 vertex being forced
for r in [0..t-k]: # r is the number of new blue degree 2 vertices
m[t+k,t+k+r]=binomial(t-k,r)*pf^r*pnf^(t-k-r) # r degree 2 vertices forced
m[t+t-1,t+t]=1
m[t+t,t+t]=1
return m