A382383 Number of distinct variances of nonempty subsets of {1, ..., n}.

0, 1, 2, 4, 7, 13, 23, 40, 68, 124, 208, 368, 559, 918, 1352, 2017, 2891, 4122, 5506, 7458, 9623, 12620, 16125, 20626, 25401, 31513, 38587, 47244, 56592, 68021, 80503, 95859, 112137, 131986, 153353, 178434, 205627, 236266, 269884, 307167, 346844, 394924, 445797, 501739

Offset

0,3

Comments

The variance of a nonempty set X is (Sum_{x in X} (x-m)^2)/|X|, where m is the average of X and |X| is the size of X.

Links

Table of n, a(n) for n=0..43.

Formula

a(n) <= 1 + Sum_{k=1..n-1} A005418(k). The smallest positive n for which strict inequality holds is n = 7. This is because there exist subsets of {1, ..., 7} which are not translates or reflections of each other, but nonetheless have the same variance. For example, {1,5}, {1,3,4,5,7}, and {1,2,3,4,5,6,7} all have variance 4, and {1,2,6} and {1,2,3,5,6,7} both have variance 14/3.

Example

For n = 4, the following a(4) = 7 variances occur for subsets of {1, 2, 3, 4}:
   variance | corresponding subsets
   ---------+----------------------
       0    | {1}, {2}, {3}, {4}
      1/4   | {1,2}, {2,3}, {3,4}
      2/3   | {1,2,3}, {2,3,4}
       1    | {1,3}, {2,4}
      5/4   | {1,2,3,4}
     14/9   | {1,2,4}, {1,3,4}
      9/4   | {1,4}

Prog

(Python)
from fractions import Fraction
def A382383_lst(n):
    s, lst=set(), [0]
    for k in range(n):
        s|={ (x+k, x2+k**2, l+1 ) for (x, x2, l) in s }
        s.add( (k, k**2, 1) )
        lst.append(len({ Fraction(x2, l) - Fraction(x, l)**2 for (x, x2, l) in s }))
    return lst # Bert Dobbelaere, Apr 06 2025

Crossrefs

Cf. A005418, A135342, A208531, A382381, A382382.

Sequence in context: A128609 A335471 A168043 * A374764 A374632 A114832

Adjacent sequences: A382380 A382381 A382382 * A382384 A382385 A382386

Keyword

nonn

Author

Pontus von Brömssen, Mar 23 2025

Extensions

a(34)-a(43) from Bert Dobbelaere, Apr 06 2025

Status

approved