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 takes a direct and literally view on Feld's claim, only based on counting. It sets the strictest criterion ("All friends ...") compared with A394695 ("Most friends ...") and A394696 ("Friends on average ...").
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 suggest that the proportion is decreasing with limit 0. 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)}, 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 768 networks with 5 nodes (=A006129(5)). 205 of them meet the requirement, making a(5)=205. These can be arranged into 6 classes of graphs with degree vectors
(1,1,1,1,4), 5 labelings,
(1,1,1,2,3), 60 labelings,
(1,1,2,3,3), 60 labelings,
(1,2,2,3,4), 60 labelings,
(2,2,2,3,3), 10 labelings,
(2,2,2,4,4), 10 labelings.
The corresponding graphs are:
o o o o o---o o---
| | / \ /|\ | /| /|\ \
o-o-o o-o-o o-o-o-o o-o-o | o | o | o o
| | | |/ | \|/ /
o o o o---o o---
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] == di[[i]], 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, Apr 06 2026
EXTENSIONS
a(8)-a(11) from Bert Dobbelaere, Apr 08 2026
a(12) from Manfred Boergens, Apr 09 2026
STATUS
approved