login
a(n) = binomial(2^n-1,2).
9

%I #67 Sep 21 2022 15:40:29

%S 0,0,3,21,105,465,1953,8001,32385,130305,522753,2094081,8382465,

%T 33542145,134193153,536821761,2147385345,8589737985,34359345153,

%U 137438167041,549754241025,2199020109825,8796086730753,35184359505921

%N a(n) = binomial(2^n-1,2).

%C Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x.

%C Or: Number of connections between the nodes of the perfect depth n binary tree and the nodes of a perfect depth (n-1) binary tree. - _Alex Ratushnyak_, Jun 02 2013

%C a(n) is the number of positive entries in the positive rows and columns of a Walsh matrix of order 2^n. It is also the size of the smallest nontrivial conjugacy class in the general linear group GL(n,2). See the link "3-bit Walsh permutation...". - _Tilman Piesk_, Sep 15 2022

%H Robert Israel, <a href="/A134057/b134057.txt">Table of n, a(n) for n = 0..1600</a>

%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6. - _Ross La Haye_, Feb 22 2009

%H Tilman Piesk, <a href="https://en.wikiversity.org/wiki/3-bit_Walsh_permutation;_conjugacy_class_2%2B2">3-bit Walsh permutation; conjugacy class 2+2</a> (Wikiversity)

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (7,-14,8).

%F a(n) = (1/2)*(4^n - 3*2^n + 2) = 3*(Stirling2(n+1,4) + Stirling2(n+1,3)).

%F a(n) = 3 *A006095(n).

%F a(n) = (2^n-1)*(2^(n-1)-1). - _Alex Ratushnyak_, Jun 02 2013

%F a(n) = Stirling2(2^n - 1,2^n - 2).

%F G.f.: 3*x^2/(1-x)/(1-2*x)/(1-4*x). - _Colin Barker_, Feb 22 2012

%F a(n) = A000225(n)*A000225(n-1). - _Michel Marcus_, Nov 30 2015

%F a(n) = A000217(2^n-2). - _Michel Marcus_, Nov 30 2015

%F a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3). - _Wesley Ivan Hurt_, May 17 2021

%F E.g.f.: exp(x)*(exp(x) - 1)^2*(exp(x) + 2)/2. - _Stefano Spezia_, Apr 06 2022

%e a(2) = 3 because for P(A) = {{},{1},{2},{1,2}} we have for case 0 {{1},{2}} and we have for case 2 {{1},{1,2}}, {{2},{1,2}}. There are 0 {x,y} of P(A) in this example that fall under case 1.

%p seq((2^n-1)*(2^(n-1)-1), n=0..100); # _Robert Israel_, Nov 30 2015

%t Table[Binomial[2^n - 1, 2], {n, 0, 30}] (* _Vincenzo Librandi_, Nov 30 2015 *)

%o (Python)

%o print([(2**n-1)*(2**(n-1)-1) for n in range(23)])

%o # _Alex Ratushnyak_, Jun 02 2013

%o (PARI) a(n) = binomial(2^n-1, 2); \\ _Michel Marcus_, Nov 30 2015

%o (Magma) [Binomial(2^n-1, 2): n in [0..30]]; // _Vincenzo Librandi_, Nov 30 2015

%Y Cf. A000217, A000225, A000392, A032263, A028243, A171477.

%K nonn,easy

%O 0,3

%A _Ross La Haye_, Jan 11 2008, Jun 01 2008