login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A035348 Triangle of a(n,k) = number of k-member minimal covers of an n-set (n >= k >= 1). 13
1, 1, 1, 1, 6, 1, 1, 25, 22, 1, 1, 90, 305, 65, 1, 1, 301, 3410, 2540, 171, 1, 1, 966, 33621, 77350, 17066, 420, 1, 1, 3025, 305382, 2022951, 1298346, 100814, 988, 1, 1, 9330, 2619625, 47708115, 83384427, 18151560, 549102, 2259, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

These are what Clarke calls "Minimal disordered k-covers of labeled n-set".

LINKS

Alois P. Heinz, Rows n = 1..75, flattened

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.

T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.

A. J. Macula, Lewis Carroll and the enumeration of minimal covers, Math. Mag., 68 (1995), 269-274.

Eric Weisstein's World of Mathematics, Minimal Cover

FORMULA

a(n,k) = Sum_{j >= 0} (-1)^j * binomial(k,j) * (2^k-1-j)^n. [Hearne-Wagner]

a(n,k) = (1/k!) * Sum_{j >= k} binomial(2^k-k-1,j-k)*j!*Stirling2(n,j). [Macula]

E.g.f.: Sum_{n>=0} (exp(y)-1)^n*exp(y*(2^n-n-1))*x^n/n!. - Vladeta Jovovic, May 08 2004

EXAMPLE

Triangle begins:

  1;

  1,    1;

  1,    6,      1;

  1,   25,     22,       1;

  1,   90,    305,      65,       1,

  1,  301,   3410,    2540,     171,      1;

  1,  966,  33621,   77350,   17066,    420,   1;

  1, 3025, 305382, 2022951, 1298346, 100814, 988,  1;

  ...

MAPLE

a:= (n, k)-> add(binomial(2^k-k-1, m-k)*m!

    *Stirling2(n, m), m=k..min(n, 2^k-1))/k!:

seq(seq(a(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Jul 02 2013

MATHEMATICA

a[n_, k_] := Sum[ (-1)^i*(2^k-i-1)^n / (i!*(k-i)!), {i, 0, k}]; Flatten[ Table[ a[n, k], {n, 1, 9}, {k, 1, n}]] (* Jean-Fran├žois Alcover, Dec 13 2011, after PARI *)

PROG

(PARI) {a(n, k) = sum(i=0, k, (-1)^i * binomial(k, i) * (2^k-1-i)^n) / k!} /* Michael Somos, Aug 05 1999 */

CROSSREFS

Row sums are A046165. Cf. A049055, A003465, A002177.

Sequence in context: A173882 A174045 A169660 * A140945 A141688 A166960

Adjacent sequences:  A035345 A035346 A035347 * A035349 A035350 A035351

KEYWORD

nonn,tabl,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Entry improved by Michael Somos

Explicit formulas added by N. J. A. Sloane, Aug 05 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 11:30 EDT 2021. Contains 343995 sequences. (Running on oeis4.)