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!)
A101370 Number of zero-one matrices with n ones and no zero rows or columns. 27
1, 4, 24, 196, 2016, 24976, 361792, 5997872, 111969552, 2324081728, 53089540992, 1323476327488, 35752797376128, 1040367629940352, 32441861122796672, 1079239231677587264, 38151510015777089280, 1428149538870997774080, 56435732691153773665280 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

a(n) = (1/(4n!)) * Sum_{r, s>=0} (rs)_n / 2^(r+s) }, where (m)_n is the falling factorial m * (m-1) * ... * (m-n+1). [Maia and Mendez]

REFERENCES

Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, p. 435 (IV, 4. Mitteilungen zur Lehre vom Transfiniten, VIII Nr. 13), Springer, Berlin. [Rainer Rosenthal, Apr 10 2007]

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..400

P. J. Cameron, D. A. Gewurz and F. Merola, Product action, Discrete Math., 308 (2008), 386-394.

M. Maia and M. Mendez, On the arithmetic product of combinatorial species, arXiv:math/0503436 [math.CO], 2005.

FORMULA

a(n) = (Sum s(n, k) * P(k)^2)/n!, where P(n) is the number of labeled total preorders on {1, ..., n} (A000670), s are signed Stirling numbers of the first kind.

G.f.: Sum_{m>=0,n>=0} Sum_{j=0..n} (-1)^(n-j)*binomial(n,j)*((1+x)^j-1)^m. - Vladeta Jovovic, Mar 25 2006

Inverse binomial transform of A007322. - Vladeta Jovovic, Aug 17 2006

G.f.: Sum_{n>=0} 1/(2-(1+x)^n)/2^(n+1). - Vladeta Jovovic, Sep 23 2006

G.f.: Sum_{n>=0} A000670(n)^2*log(1+x)^n/n! where 1/(1-x) = Sum_{n>=0} A000670(n)*log(1+x)^n/n!. - Paul D. Hanna, Nov 07 2009

a(n) ~ n! / (2^(2+log(2)/2) * (log(2))^(2*(n+1))). - Vaclav Kotesovec, Dec 31 2013

EXAMPLE

a(2)=4:

[1 1] [1] [1 0] [0 1]

..... [1] [0 1] [1 0]

From Gus Wiseman, Nov 14 2018: (Start)

The a(3) = 24 matrices:

  [111]

.

  [11][11][110][101][10][100][011][01][010][001]

  [10][01][001][010][11][011][100][11][101][110]

.

  [1][10][10][10][100][100][01][01][010][01][010][001][001]

  [1][10][01][01][010][001][10][10][100][01][001][100][010]

  [1][01][10][01][001][010][10][01][001][10][100][010][100]

(End)

MATHEMATICA

m = 17; a670[n_] = Sum[ StirlingS2[n, k]*k!, {k, 0, n}]; Rest[ CoefficientList[ Series[ Sum[ a670[n]^2*(Log[1 + x]^n/n!), {n, 0, m}], {x, 0, m}], x]] (* Jean-Fran├žois Alcover, Sep 02 2011, after g.f.  *)

Table[Length[Select[Subsets[Tuples[Range[n], 2], {n}], And[Union[First/@#]==Range[Max@@First/@#], Union[Last/@#]==Range[Max@@Last/@#]]&]], {n, 5}] (* Gus Wiseman, Nov 14 2018 *)

PROG

(GAP) P:=function(n) return Sum([1..n], x->Stirling2(n, x)*Factorial(x)); end;

(GAP) F:=function(n) return Sum([1..n], x->(-1)^(n-x)*Stirling1(n, x)*P(x)^2)/Factorial(n); end;

(PARI) {A000670(n)=sum(k=0, n, stirling(n, k, 2)*k!)}

{a(n)=polcoeff(sum(m=0, n, A000670(m)^2*log(1+x+x*O(x^n))^m/m!), n)}

/* Paul D. Hanna, Nov 07 2009 */

CROSSREFS

Cf. A000670 (the sequence (P(n)), A049311 (row and column permutations allowed), A120733, A122725, A135589, A283877, A321446, A321587.

Sequence in context: A305988 A219530 A291819 * A201338 A099021 A220690

Adjacent sequences:  A101367 A101368 A101369 * A101371 A101372 A101373

KEYWORD

easy,nonn,changed

AUTHOR

Peter J. Cameron, Jan 14 2005

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 August 4 10:06 EDT 2021. Contains 346447 sequences. (Running on oeis4.)