A178165 -id:A178165 - cp's OEIS frontend

A330964 Array read by antidiagonals: A(n,k) is the number of sets of nonempty subsets of a k-element set where each element appears in at most n subsets.

1, 1, 1, 1, 2, 1, 1, 5, 2, 1, 1, 15, 8, 2, 1, 1, 52, 59, 8, 2, 1, 1, 203, 652, 109, 8, 2, 1, 1, 877, 9736, 3623, 128, 8, 2, 1, 1, 4140, 186478, 200522, 11087, 128, 8, 2, 1, 1, 21147, 4421018, 16514461, 2232875, 21380, 128, 8, 2, 1, 1, 115975, 126317785, 1912959395, 775098224, 15312665, 29228, 128, 8, 2, 1

Offset: 0

Andrew Howroyd, Jan 04 2020

A(n,k) is the number of binary matrices with k columns and any number of nonzero rows with rows in decreasing order and at most n ones in every column.

			Array begins:
==================================================================
n\k | 0 1 2   3     4         5             6                7
----+-------------------------------------------------------------
  0 | 1 1 1   1     1         1             1                1 ...
  1 | 1 2 5  15    52       203           877             4140 ...
  2 | 1 2 8  59   652      9736        186478          4421018 ...
  3 | 1 2 8 109  3623    200522      16514461       1912959395 ...
  4 | 1 2 8 128 11087   2232875     775098224     428188962261 ...
  5 | 1 2 8 128 21380  15312665   22165394234   57353442460140 ...
  6 | 1 2 8 128 29228  70197998  422059040480 5051078354829005 ...
  7 | 1 2 8 128 32297 227731312 5686426671375 ...
      ...
The T(1,2) = 5 set systems are:
  {},
  {{1,2}},
  {{1,2}, {2}},
  {{1},{1,2}},
  {{1}, {2}}.

Andrew Howroyd, Table of n, a(n) for n = 0..209

Rows n=0..4 are A000012, A000110, A178165, A178171, A178173.
Cf. A058891, A188445, A219585, A219727.
Main diagonal gives A374573.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); (vecsum(WeighT(v)) + 1)^k/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))/(1+x))); if(n==0, 1, (-1)^m*sum(j=0, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*q[#q-j])/2)}

Lim_{n->oo} A(n,k) = 2^k.

A178171 Number of collections of nonempty subsets of an n-element set where each element appears in at most 3 subsets.

Original entry on oeis.org

1, 2, 8, 109, 3623, 200522, 16514461, 1912959395, 298569495981, 60701549078701, 15647889334180500, 5003666238486522124, 1948975409748003520112, 910680909359710587298621, 503845222094502583681150340, 326363222435413478204610417626, 245078255691857705139839897934085

Offset: 0

Daniel E. Loeb, Dec 17 2010

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..100

Row n=3 of A330964.

At most 1 subset gives Bell numbers A000110, at most 2 subsets gives A178165.

a(7)-a(8) from Bert Dobbelaere, Sep 10 2019

Terms a(9) and beyond from Andrew Howroyd, Jan 04 2020

A178173 Number of collections of nonempty subsets of an n-element set where each element appears in at most 4 subsets.

Original entry on oeis.org

1, 2, 8, 128, 11087, 2232875, 775098224, 428188962261, 355916994389700, 425272149099677521, 703909738878615927739, 1565842283246869237505246, 4565002967677134523844716754, 17076464900445281560851997140670, 80494979734877344662882495100752511

Offset: 0

Daniel E. Loeb, Dec 17 2010

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50

Row n=4 of A330964.

Replacing limit of 2 with a limit of 1 gives the Bell numbers A000110, limit of 2 gives A178165, limit of 3 gives A178171.

\\ See A330964 for efficient code to compute this sequence. - Andrew Howroyd, Jan 04 2020

from numpy import array
def toBinary(n,k):
    ans=[]
    for i in range(k):
        ans.insert(0,n%2)
        n=n>>1
    return array(ans)
def powerSet(k): return [toBinary(n,k) for n in range(1,2**k)]
def courcelle(maxUses,remainingSets,exact=False):
    if exact and not all(maxUses<=sum(remainingSets)): ans=0
    elif len(remainingSets)==0: ans=1
    else:
        set0=remainingSets[0]
        if all(set0<=maxUses): ans=courcelle(maxUses-set0,remainingSets[1:],exact=exact)
        else: ans=0
        ans+=courcelle(maxUses,remainingSets[1:],exact=exact)
    return ans
for i in range(10):
    print(i, courcelle(array([4]*i),powerSet(i),exact=False))

a(6)-a(8) from Bert Dobbelaere, Sep 10 2019

Terms a(9) and beyond from Andrew Howroyd, Jan 04 2020

cp's OEIS Frontend

A330964 Array read by antidiagonals: A(n,k) is the number of sets of nonempty subsets of a k-element set where each element appears in at most n subsets.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A178171 Number of collections of nonempty subsets of an n-element set where each element appears in at most 3 subsets.

Views

Author

Keywords

Links

Crossrefs

Extensions

A178173 Number of collections of nonempty subsets of an n-element set where each element appears in at most 4 subsets.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Extensions