@vv

You're one hundred percent right if S is the power set of { {}, a1, ..., an } , and also probaly right if nops(S) is large enough.

I even feel that your guess could reduce to nops(S) > n given the "the generators (are) to be mutually disjoint" requirement that @Christian Wolinski just came to indicate.

**Reverse problem:**

Let G(N) = {a_{n}, n=1..N} the set of generators, PG(N) the power set of G(N) (empty set discarded) and S(N, K) a subset of cardinal K of elements of PG(N).

Let T(N, K) the set of all pairwise intersections of elements of S(N, K).

Let **T**(N, K) the set of all T(N, K) obtained for all the **combinat:-numbcomb(2^N-1, K)** different sets S(N,K).

**Question** : What how sets in **T**(N, K) contain the set {{}, {a_{1}}, ..., {a_{N}}} ?

This number is the an inferior bound if the number of times your hypothesis is verified.

Example:

As I use Maple 2015 I can't use the **Iterator** package to do an exhaustive computation, so I did the things statistically (I had in mind to do this for higher values of N and I used this strategy in the example below even if it is stupid).

restart:
G := N -> {seq(a__||n, n=1..N)}:
PG := N -> combinat:-powerset(G(N)) minus {{}}:
S := (N, K) -> { combinat:-randperm(PG(N))[1..K][] }:
n := 3:
k := 5:
count := table([]):
for rep from 1 to 10^4 do
s := S(n, k);
T := {}:
for n1 from 1 to nops(s) do
for n2 from n1+1 to nops(s) do
T := T union {`intersect`(s[n1], s[n2])}
end do:
end do:
nt := nops~([T[]]);
if member(nt, {indices(count, nolist)}) then
count[%] := count[%] +1:
else
count[%] := 1:
end if:
end do:
eval(count):
for i in {indices(count, nolist)} do
printf(cat("%", 6*n+3, "a : %d\n"), i, count[i])
end do:
[0, 1, 1, 1] : 2862
[0, 1, 1, 1, 2] : 1434
[0, 1, 1, 2, 2] : 2828
[0, 1, 1, 1, 2, 2] : 1423
[0, 1, 1, 1, 2, 2, 2] : 1453
add(map(u -> if ListTools:-Occurrences(1, u)=n then count[u] end if, [indices(count, nolist)]))
7172

Your hypothesis is verified at least 7172 times (plus probably some more time for some [0, 1, 1, 2, 2] configurations can be generated by {{}, {a_{1}}, ..., {a_{N}}} (Christian Wolinski's problem).

Here are a few other results (P is the inferior bound for the the number of times your hypothesis is verified)

n k P
5, 6, 383;
5, 6, 1001;
5, 8, 2285;
5, 9, 3636;
5, 10, 5111;
n k P
6, 7, 191;
6, 8, 563;
6, 9, 1108;
6, 10, 1987;
6, 11, 2885;
6, 12, 3937;
6, 13, 4966

Inference: there is at least 50% of chances that a "good candidate" (as you said) is {{}, {a_{1}}, ..., {a_{N}}} as soon as K > 2*N

(or nops(S) > n with your notations)

**EDITED:**

Introducing the procedure that Christian Wolinski just delivered;

restart:
#Christian Wolinski's procedure
F := proc ()
local S, E, L, Lexc, Linc, i, s;
E, S := selectremove(type, {args}, identical({}));
L := [op](S);
S := NULL;
for i to nops(L) do
Linc, Lexc := selectremove(member, L[i], `union`(S));
if Linc = {} then S := S, Lexc
else S := seq(
proc ()
local X;
X := [`intersect`, `minus`](s, Linc);
if X[1] = {} then E := {{}} end if;
op(remove(type, X, identical({})))
end proc(),
s = [S]), `if`(Lexc <> {}, Lexc, NULL)
end if
end do;
op(`union`({S},E))
end proc:
#--------------------
G := N -> {$1..N}:
PG := N -> combinat:-powerset(G(N)) minus {{}}:
S := (N, K) -> { combinat:-randperm(PG(N))[1..K][] }:
HypothesisVerified := proc(n, k, REP)
local count, rep, s, T, nt:
count := table([]):
for rep from 1 to REP do
s := S(n, k);
T := F(op(s));
nt := nops~([T[]]);
if member(nt, {indices(count, nolist)}) then
count[%] := count[%] +1:
else
count[%] := 1:
end if:
end do:
add(map(u -> if ListTools:-Occurrences(1, u)=n then count[u] end if, [indices(count, nolist)]))
end proc:
HypothesisVerified(6, 8, 10^4);
9584
HypothesisVerified(8, 10, 10^4);
9702
HypothesisVerified(15, 16, 10^4);
9980

**A statistical hypothesis**:

Given S(N,K) randomly choosen, the probability that {{}, {a_{1}}, ..., {a_{N}}} is a good candidate for F(S(N, K)) goes to 1 when n -> +oo and K/N -> 1^{+}.