login
A104602
Number of square (0,1)-matrices with exactly n entries equal to 1 and no zero row or columns.
21
1, 1, 2, 10, 70, 642, 7246, 97052, 1503700, 26448872, 520556146, 11333475922, 270422904986, 7016943483450, 196717253145470, 5925211960335162, 190825629733950454, 6543503207678564364, 238019066600097607402, 9153956822981328930170, 371126108428565106918404
OFFSET
0,3
COMMENTS
Number of square (0,1)-matrices with exactly n entries equal to 1 and no zero row or columns, up to row and column permutation, is A057151(n). - Vladeta Jovovic, Mar 25 2006
LINKS
H. Cheballah, S. Giraudo, R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013-2015.
M. Maia and M. Mendez, On the arithmetic product of combinatorial species, arXiv:math/0503436 [math.CO], 2005.
FORMULA
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n,k)*A048144(k). - Vladeta Jovovic, Mar 25 2006
G.f.: Sum_{n>=0} Sum_{j=0..n} (-1)^(n-j)*binomial(n,j)*((1+x)^j-1)^n. - Vladeta Jovovic, Mar 25 2006
a(n) ~ c * n! / (sqrt(n) * (log(2))^(2*n)), where c = 0.28889864564457451375789435201798... . - Vaclav Kotesovec, May 07 2014
In closed form, c = 1 / (log(2) * 2^(log(2)/2+2) * sqrt(Pi*(1-log(2)))). - Vaclav Kotesovec, May 03 2015
G.f.: Sum_{n>=0} ((1+x)^n - 1)^n / (1+x)^(n*(n+1)). - Paul D. Hanna, Mar 26 2018
EXAMPLE
From Gus Wiseman, Nov 14 2018: (Start)
The a(3) = 10 matrices:
[1 1] [1 1] [1 0] [0 1]
[1 0] [0 1] [1 1] [1 1]
.
[1 0 0] [1 0 0] [0 1 0] [0 1 0] [0 0 1] [0 0 1]
[0 1 0] [0 0 1] [1 0 0] [0 0 1] [1 0 0] [0 1 0]
[0 0 1] [0 1 0] [0 0 1] [1 0 0] [0 1 0] [1 0 0]
(End)
MATHEMATICA
Table[1/n!*Sum[StirlingS1[n, k]*Sum[(m!)^2*StirlingS2[k, m]^2, {m, 0, k}], {k, 0, n}], {n, 1, 20}] (* Vaclav Kotesovec, May 07 2014 *)
Table[Length[Select[Subsets[Tuples[Range[n], 2], {n}], Union[First/@#]==Union[Last/@#]==Range[Max@@First/@#]&]], {n, 5}] (* Gus Wiseman, Nov 14 2018 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Ralf Stephan, Mar 27 2005
EXTENSIONS
More terms from Vladeta Jovovic, Mar 25 2006
a(0)=1 prepended by Alois P. Heinz, Jan 14 2015
STATUS
approved