login
A101370
Number of zero-one matrices with n ones and no zero rows or columns.
28
1, 4, 24, 196, 2016, 24976, 361792, 5997872, 111969552, 2324081728, 53089540992, 1323476327488, 35752797376128, 1040367629940352, 32441861122796672, 1079239231677587264, 38151510015777089280, 1428149538870997774080, 56435732691153773665280
OFFSET
1,2
COMMENTS
a(n) = (1/(4*n!)) * Sum_{r, s>=0} (r*s)_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
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 A362355 A099021
KEYWORD
easy,nonn
AUTHOR
Peter J. Cameron, Jan 14 2005
STATUS
approved