|
| |
|
|
A134057
|
|
a(n) = binomial(2^n-1,2).
|
|
9
|
|
|
|
0, 0, 3, 21, 105, 465, 1953, 8001, 32385, 130305, 522753, 2094081, 8382465, 33542145, 134193153, 536821761, 2147385345, 8589737985, 34359345153, 137438167041, 549754241025, 2199020109825, 8796086730753, 35184359505921
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
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.
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
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
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = (1/2)*(4^n - 3*2^n + 2) = 3*(Stirling2(n+1,4) + Stirling2(n+1,3)).
a(n) = Stirling2(2^n - 1,2^n - 2).
G.f.: 3*x^2/(1-x)/(1-2*x)/(1-4*x). - Colin Barker, Feb 22 2012
E.g.f.: exp(x)*(exp(x) - 1)^2*(exp(x) + 2)/2. - Stefano Spezia, Apr 06 2022
|
|
|
EXAMPLE
|
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.
|
|
|
MAPLE
|
|
|
|
MATHEMATICA
|
|
|
|
PROG
|
(Python)
print([(2**n-1)*(2**(n-1)-1) for n in range(23)])
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
