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

Author

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

Keywords

• nonn

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)

Examples

			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)) +...
		

Links

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

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.

Programs

Magma

[Binomial(2^n -1, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021

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 *)

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), ", "))

Python

from math import comb
def A136556(n): return comb((1<Chai Wah Wu, Jan 02 2024

Sage

[binomial(2^n -1, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021

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

Extensions

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