7
$\begingroup$

Consider a matrix $A$ of size $n\times n$. I want to fill it with one and zero such that there are exactly two entries one in each row and each column, and the other entries are zero.
In how many different ways I can fill $A$?

  • 2
    I don't see much relation to matrices or permutations here. It's mostly combinatorics, ways to order things under certain constraints.2011-04-25
  • 0
    Well, I can see a relation to matrices and permutations and I do not see the utility of removing the tags.2011-04-25
  • 0
    @user9325: You can always put them back, but in case you do - please elaborate why.2011-04-25
  • 2
    @Asaf I think that the onus is on you to justify why you took them away instead of asking me to elaborate. The number is related to derangements, the matrices are *matrices* that are a direct generalization of *permutation* matrices, the column number in each row can be chained together to form a fixed-point free *permutation* and I find it highly ironic to say that you do not see the relation to permutations because it is only about the ways to order things.2011-04-25
  • 0
    There is also the question what tags are good for. I think that "permutation" and "matrix" is exactly what comes to mind if one tries to find this question. (I certainly do not disagree with the tag combinatorics.)2011-04-25
  • 0
    @user9325: Had the question been imposed as "Find the set of all matrices such that ..." would you have tagged it under set theory (or elementary set theory)? I would certainly not.2011-04-25
  • 0
    @Asaf No, I wouldn't, but the analogue of "set theory" is "linear algebra".2011-04-25
  • 0
    (I added the tags again, but I will certainly not interfere if someone else takes them off again. I am somewhat unhappy that other people do not weigh in. The tag "matrices" has no descriptions and tags have contradictory purposes.)2011-04-25
  • 0
    I took the terminology I added to the title from Mathworld, which certainly calls them matrices. I would include all three tags.2011-04-26

1 Answers 1

10

You find your series in the online encyclopedia of integer series.

http://oeis.org/A001499

Note that the given formulas are all recursive, sums or asymptotic results.

In particular, the generating function is related to the generating functions of derangements, permutations without fixed points.

  • 0
    Finding this is not too hard. Calculating by had the numbers 0,1,6,90 for orders 1-4 brings it right up.2011-04-25
  • 2
    I'll just note the closed form $n(n-1)\frac{(2n-2)!}{2^{2n-2}}{}_1 F_1\left(2-n;\frac32-n;-\frac12\right)$ listed in the OEIS.2011-04-25
  • 0
    Asymptotically, it is $$\frac{n!^2}{\sqrt{n\pi e}}$$2011-04-26