A120732 Number of square matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.

1, 1, 3, 15, 107, 991, 11267, 151721, 2360375, 41650861, 821881709, 17932031225, 428630422697, 11138928977049, 312680873171465, 9428701154866535, 303957777464447449, 10431949496859168189, 379755239311735494421

Offset

0,3

Links

G. C. Greubel, Table of n, a(n) for n = 0..250

Formula

a(n) = (1/n!)*Sum_{k=0..n} (-1)^(n-k)*Stirling1(n,k)*A048144(k).

G.f.: Sum_{n>=0} Sum_{j=0..n} (-1)^(n-j)*binomial(n,j)*((1-x)^(-j)-1)^n.

a(n) ~ c * n! / (sqrt(n) * (log(2))^(2*n)), where c = 0.4670932578797312973586879293426... . - Vaclav Kotesovec, May 07 2014

In closed form, c = 2^(log(2)/2-2) / (log(2) * sqrt(Pi*(1-log(2)))). - Vaclav Kotesovec, May 03 2015

G.f.: Sum_{n>=0} (1-x)^n * (1 - (1-x)^n)^n. - Paul D. Hanna, Mar 26 2018

Example

From Gus Wiseman, Nov 14 2018: (Start)
The a(3) = 15 matrices:
  [3]
.
  [2 0] [1 1] [1 1] [1 0] [1 0] [0 2] [0 1] [0 1]
  [0 1] [1 0] [0 1] [1 1] [0 2] [1 0] [2 0] [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[(-1)^(n-k)*StirlingS1[n, k]*Sum[(m!)^2*StirlingS2[k, m]^2, {m, 0, k}], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, May 07 2014 *)
multsubs[set_, k_]:=If[k==0, {{}}, Join@@Table[Prepend[#, set[[i]]]&/@multsubs[Drop[set, i-1], k-1], {i, Length[set]}]]; Table[Length[Select[multsubs[Tuples[Range[n], 2], n], Union[First/@#]==Union[Last/@#]==Range[Max@@First/@#]&]], {n, 5}] (* Gus Wiseman, Nov 14 2018 *)

Crossrefs

Cf. A007716, A048291, A054976, A057149, A057150, A057151, A104601, A104602, A120733, A138178, A316983, A319616.

Sequence in context: A349874 A074519 A105618 * A245835 A362354 A090351

Adjacent sequences: A120729 A120730 A120731 * A120733 A120734 A120735

Keyword

nonn

Author

Vladeta Jovovic, Aug 18 2006

Status

approved