A101370 - OEIS

%I #48 Nov 18 2024 15:59:07

%S 1,4,24,196,2016,24976,361792,5997872,111969552,2324081728,

%T 53089540992,1323476327488,35752797376128,1040367629940352,

%U 32441861122796672,1079239231677587264,38151510015777089280,1428149538870997774080,56435732691153773665280

%N Number of zero-one matrices with n ones and no zero rows or columns.

%C 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]

%D 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]

%H Alois P. Heinz, <a href="/A101370/b101370.txt">Table of n, a(n) for n = 1..400</a>

%H P. J. Cameron, D. A. Gewurz and F. Merola, <a href="http://www.maths.qmw.ac.uk/~pjc/preprints/product.pdf">Product action</a>, Discrete Math., 308 (2008), 386-394.

%H Giulio Cerbai and Anders Claesson, <a href="https://arxiv.org/abs/2411.08426">Enumerative aspects of Caylerian polynomials</a>, arXiv:2411.08426 [math.CO], 2024. See pp. 3, 19.

%H M. Maia and M. Mendez, <a href="https://arxiv.org/abs/math/0503436">On the arithmetic product of combinatorial species</a>, arXiv:math/0503436 [math.CO], 2005.

%F 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.

%F 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

%F Inverse binomial transform of A007322. - _Vladeta Jovovic_, Aug 17 2006

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

%F 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

%F a(n) ~ n! / (2^(2+log(2)/2) * (log(2))^(2*(n+1))). - _Vaclav Kotesovec_, Dec 31 2013

%e a(2)=4:

%e [1 1] [1] [1 0] [0 1]

%e ..... [1] [0 1] [1 0]

%e From _Gus Wiseman_, Nov 14 2018: (Start)

%e The a(3) = 24 matrices:

%e   [111]

%e .

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

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

%e .

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

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

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

%e (End)

%t 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.  *)

%t 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 *)

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

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

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

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

%o /* _Paul D. Hanna_, Nov 07 2009 */

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

%K easy,nonn

%O 1,2

%A _Peter J. Cameron_, Jan 14 2005