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.

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.

Links

Table of n, a(n) for n=1..6.

Zach Wissner-Gross, Can You Make An Unfair Coin Fair?

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

Adjacent sequences: A338769 A338770 A338771 * A338773 A338774 A338775

Keyword

nonn,hard,more

Author

H. Tracy Hall, Nov 08 2020

Status

approved