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

1, 1, 3, 35, 1365, 169911, 67945521, 89356415775, 396861704798625, 6098989894499557055, 331001552386330913728641, 64483955378425999076128999167, 45677647585984911164223317311276545, 118839819203635450208125966070067352769535, 1144686912178270649701033287538093722740144666625

Offset

0,3

Comments

Number of n x n binary matrices without zero rows and with distinct rows up to permutation of rows, cf. A014070.

Row 0 of square array A136555.

From Gus Wiseman, Dec 19 2023: (Start)

Also the number of n-element sets of nonempty subsets of {1..n}, or set-systems with n vertices and n edges (not necessarily covering). The covering case is A054780. For example, the a(3) = 35 set-systems are:

{1}{2}{3} {1}{2}{12} {1}{2}{123} {1}{12}{123} {12}{13}{123}

{1}{2}{13} {1}{3}{123} {1}{13}{123} {12}{23}{123}

{1}{2}{23} {1}{12}{13} {1}{23}{123} {13}{23}{123}

{1}{3}{12} {1}{12}{23} {2}{12}{123}

{1}{3}{13} {1}{13}{23} {2}{13}{123}

{1}{3}{23} {2}{3}{123} {2}{23}{123}

{2}{3}{12} {2}{12}{13} {3}{12}{123}

{2}{3}{13} {2}{12}{23} {3}{13}{123}

{2}{3}{23} {2}{13}{23} {3}{23}{123}

{3}{12}{13} {12}{13}{23}

{3}{12}{23}

{3}{13}{23}

Of these, only {{1},{2},{1,2}}, {{1},{3},{1,3}}, and {{2},{3},{2,3}} do not cover the vertex set.

(End)

Links

G. C. Greubel, Table of n, a(n) for n = 0..50

Formula

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(2^n,k).

a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n,k) * (2^n-1)^k.

G.f.: Sum_{n>=0} log(1 + 2^n*x)^n / (n! * (1 + 2^n*x)).

a(n) ~ 2^(n^2)/n!. - Vaclav Kotesovec, Jul 02 2016

Example

G.f.: A(x) = 1 + x + 3*x^2 + 35*x^3 + 1365*x^4 + 169911*x^5 +...
A(x) = 1/(1+x) + log(1+2*x)/(1+2*x) + log(1+4*x)^2/(2!*(1+4*x)) + log(1+8*x)^3/(3!*(1+8*x)) + log(1+16*x)^4/(4!*(1+16*x)) + log(1+32*x)^5/(5!*(1+32*x)) +...

Maple

A136556:= n-> binomial(2^n-1, n); seq(A136556(n), n=0..20); # G. C. Greubel, Mar 14 2021

Mathematica

f[n_] := Binomial[2^n - 1, n]; Array[f, 12] (* Robert G. Wilson v *)
Table[Length[Subsets[Rest[Subsets[Range[n]]], {n}]], {n, 0, 4}] (* Gus Wiseman, Dec 19 2023 *)

Prog

(PARI) {a(n) = binomial(2^n-1, n)}
for(n=0, 20, print1(a(n), ", "))
(PARI) /* As coefficient of x^n in the g.f.: */
{a(n) = polcoeff( sum(i=0, n, 1/(1 + 2^i*x +x*O(x^n)) * log(1 + 2^i*x +x*O(x^n))^i/i!), n)}
for(n=0, 20, print1(a(n), ", "))
(Sage) [binomial(2^n -1, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021
(Magma) [Binomial(2^n -1, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021
(Python)
from math import comb
def A136556(n): return comb((1<<n)-1, n) # Chai Wah Wu, Jan 02 2024

Crossrefs

Sequences of the form binomial(2^n +p*n +q, n): this sequence (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), A060690 (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).

Cf. A066384, A136555, A136557.

The covering case A054780 has binomial transform A367916, ranks A367917.

Connected graphs of this type are A057500, unlabeled A001429.

Graphs of this type are A116508, covering A367863, unlabeled A006649.

A003465 counts set-systems covering {1..n}, unlabeled A055621.

A058891 counts set-systems, connected A323818, without singletons A016031.

Cf. A055154, A059201, A133686, A367862, A367902, A367903.

Sequence in context: A279377 A215582 A136525 * A006098 A320845 A012499

Adjacent sequences: A136553 A136554 A136555 * A136557 A136558 A136559

Keyword

nonn

Author

Paul D. Hanna, Jan 07 2008; Paul Hanna and Vladeta Jovovic, Jan 15 2008

Extensions

Edited by N. J. A. Sloane, Jan 26 2008

Status

approved