login
Number of symmetric, reflexive, non-transitive relations on n elements.
0

%I #14 Feb 26 2015 09:55:51

%S 0,0,3,49,972,32565,2096275,268431316,68719455589,35184371972857,

%T 36028797018285398,73786976294833992867,302231454903657266032107,

%U 2475880078570760549607349126,40564819207303340847893119613487,1329227995784915872903807049800202429

%N Number of symmetric, reflexive, non-transitive relations on n elements.

%C Of the values shown, only 3 is prime. Are there any other prime values in the sequence? - _Jonathan Vos Post_, Dec 29 2011

%F a(n) = 2^(n*(n-1)/2) - A000110(n) = A006125(n) - A000110(n).

%e The first symmetric, reflexive, nontransitive relation occurs for n=3: omitting a non-identical couple (a,b) from the total relation gives such a relation (and for n=3, this is the only way). There are 3 ways to choose this couple.

%o (Sage) def a(n): return 2^(n*(n-1)/2) - bell_number(n)

%K nonn

%O 1,3

%A _Bert Seghers_, Dec 20 2011