login
A338772
The number of different probabilities p for which a coin that lands heads with probability p can, using n flips, perfectly model one flip of a fair coin.
0
1, 3, 19, 271, 8635, 623533
OFFSET
1,2
COMMENTS
This counts the distinct roots in the range 0 to 1 occurring among a set of degree-n polynomials the number of which is given by A055612. The 2^n possible outcomes of n coin flips are divided into n + 1 classes depending on how many times heads comes up, and there is one polynomial for each way of deciding how many of each class goes on which side of the partition of outcomes that will model a fair coin flip.
EXAMPLE
For n = 2 the a(2) = 3 different values of p are, in increasing order:
1 - sqrt(1/2), which can model a fair flip with the partition (HH, HT, TH), (TT);
1/2, which can model a fair flip with the partition (HH, HT), (TH, TT) (i.e., by ignoring the second flip); and
sqrt(1/2), which can model a fair flip with the partition (HH), (HT, TH, TT).
PROG
(SageMath)
P.<p> = QQ[]
def polystream(nn, pol=P(0), kk=0):
if kk >= nn:
yield pol - 1
else:
for ii in sxrange(binomial(nn, kk) + 1):
for xx in polystream(nn, pol + 2 * ii * p^kk * (1-p)^(nn-kk), kk + 1):
yield xx
def calculate(nn):
solutions = Set()
for pol in polystream(nn):
rootlist = [xx[0] for xx in pol.roots(ring=QQbar)]
for root in rootlist:
if root.real() == root and 0 <= root <= 1:
solutions += Set([root])
return len(solutions)
CROSSREFS
Sequence in context: A233240 A173799 A003011 * A376011 A231620 A268646
KEYWORD
nonn,hard,more
AUTHOR
H. Tracy Hall, Nov 08 2020
STATUS
approved