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

Author

Pontus von Brömssen, Mar 23 2025

Keywords

• nonn

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.

Examples

			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}
		

Crossrefs

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

Programs

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

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.

Extensions

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