A305737 Number of subsets S of vectors in GF(2)^n such that span(S) = GF(2)^n.

1, 2, 8, 184, 62464, 4293001088, 18446743803209556992, 340282366920938461120638132973980614656, 115792089237316195423570985008687907766497981100801256254562260326801824546816

Offset: 0

Author

Geoffrey Critzer, Jun 22 2018

Keywords

• nonn

Comments

Asymptotic to A001146(n) = 2^(2^n).

References

• R. P. Stanley, Enumerative Combinatorics Vol 1, Cambridge, 1997, page 127.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..10
• Tilman Piesk, relationship to Boolean functions (Wikiversity)

Crossrefs

Cf. A001146, A022166, A158474, A051179.

Programs

Mathematica

Table[Sum[QBinomial[n, k, q] (-1)^(n - k) q^Binomial[n - k, 2] (2^(q^k) - 1) /. q -> 2, {k, 0, n}], {n, 0, 8}]

PARI

\\ here U(n,k) is A022166(n,k).
U(n,k)={polcoeff(x^k/prod(j=0, k, 1-2^j*x+x*O(x^n)), n)}
a(n)={sum(k=0, n, U(n,k)*(-1)^(n-k)*2^binomial(n-k,2)*(2^(2^k)-1))} \\ Andrew Howroyd, Mar 01 2020

Formula

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

Sum_{k=0..n} a(k)* A022166(n,k) = 2^(2^n) - 1. - Geoffrey Critzer, Apr 25 2024

a(n) = Sum_{k=0..n} A158474(n,k) * A051179(n-k). - Tilman Piesk, Mar 12 2025

Extensions

a(8) corrected by Andrew Howroyd, Mar 01 2020