OFFSET
2,2
COMMENTS
This refers to the "friendship paradox" which goes back to S. L. Feld's 1991 article claiming that persons have fewer friends than their friends have. In contrast to Feld's results based on averages for numbers of friends and friends' friends, this sequence sets a stricter criterion and takes a direct and literally view of Feld's claim, only based on counting.
The total numbers of social networks as defined by Feld are given by A006129. For n>3, the proportion a(n)/A006129(n) is considerably below 0.5 and does not support Feld's claim. For 7<n<400, simulations show that the proportion is increasing but stays below 0.5. Even n give lower proportions because there appear many ties (statement is true for half of the n persons).
a(n) can be defined in graph theoretic terms. The "network" is a labeled simple graph with n unisolated nodes, n>1.
If d_m(i) = degree of node i in the m-th graph, i = 1,..., n, m = 1,..., A006129(n), d_m(i,j) = degree of j-th node connected with node i, j = 1,..., d_m(i), n_m(i) = #{ j | d_m(i,j) > d_m(i)}, and n_m = #{ i | n_m(i) > d_m(i)/2}, then a(n) = #{ m | n_m > n/2}.
LINKS
Scott L. Feld, Why Your Friends Have More Friends Than You Do, Am. J. Sociol. 96(6) (1991), p. 1464-1477.
EXAMPLE
There are 41 networks with 4 nodes (=A006129(4)). Only 4 of them meet the requirement, making a(4)=4; the edges are:
1-2, 1-3, 1-4;
2-1, 2-3, 2-4;
3-1, 3-2, 3-4;
4-1, 4-2, 4-3.
MATHEMATICA
nmax = 7; a = {};
Do[an = 0; t = Tuples[{0, 1}, n (n - 1)/2];
Do[v = t[[j]]; m = {ConstantArray[0, n]};
Do[la = Last[NestList[Append[#, 0] &, Take[v, i], n - i]];
m = Join[m, {la}]; v = Drop[v, i], {i, n - 1}];
m = m + Transpose[m]; pr = Product[Total[m[[i]]], {i, n}];
If[pr != 0, di = Table[Total[m[[j]]], {j, n}];
dij = Table[Cases[Table[di[[i]] m[[j]][[i]], {i, n}], Except[0]], {j, n}];
sd = Sign[dij - di];
nI = Table[If[Count[sd[[i]], 1] > Length[sd[[i]]]/2, 1, 0], {i, n}];
If[Total[nI] > n/2, an++]], {j, 2^(n (n - 1)/2)}];
a = Join[a, {an}], {n, 2, nmax}]; a
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Manfred Boergens, Mar 29 2026
EXTENSIONS
a(8)-a(9) from Sean A. Irvine, Apr 05 2026
a(10) from Bert Dobbelaere, Apr 06 2026
a(11) from Bert Dobbelaere, Apr 08 2026
a(12) from Manfred Boergens, Apr 09 2026
STATUS
approved