|
|
A008300
|
|
Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= n) gives number of {0,1} n X n matrices with all row and column sums equal to k.
|
|
26
|
|
|
1, 1, 1, 1, 2, 1, 1, 6, 6, 1, 1, 24, 90, 24, 1, 1, 120, 2040, 2040, 120, 1, 1, 720, 67950, 297200, 67950, 720, 1, 1, 5040, 3110940, 68938800, 68938800, 3110940, 5040, 1, 1, 40320, 187530840, 24046189440, 116963796250, 24046189440, 187530840, 40320, 1, 1, 362880, 14398171200, 12025780892160, 315031400802720, 315031400802720, 12025780892160, 14398171200, 362880, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Or, triangle of multipermutation numbers T(n,k), n >= 0, 0 <= k <= n: number of relations on an n-set such that all vertical sections and all horizontal sections have k elements.
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 236, P(n,k).
|
|
LINKS
|
|
|
FORMULA
|
Comtet quotes Everett and Stein as showing that T(n,k) ~ (kn)!(k!)^(-2n) exp( -(k-1)^2/2 ) for fixed k as n -> oo.
T(n,k) = T(n,n-k).
|
|
EXAMPLE
|
Triangle begins:
1;
1, 1;
1, 2, 1;
1, 6, 6, 1;
1, 24, 90, 24, 1;
1, 120, 2040, 2040, 120, 1;
1, 720, 67950, 297200, 67950, 720, 1;
1, 5040, 3110940, 68938800, 68938800, 3110940, 5040, 1;
...
|
|
PROG
|
(PARI)
T(n, k)={
local(M=Map(Mat([n, 1])));
my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
my(recurse(i, p, v, e) = if(i<0, if(!e, acc(p, v)), my(t=polcoef(p, i)); for(j=0, min(t, e), self()(i-1, p+j*(x-1)*x^i, binomial(t, j)*v, e-j))));
for(r=1, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], recurse(k-1, src[i, 1], src[i, 2], k))); vecsum(Mat(M)[, 2]);
|
|
CROSSREFS
|
Cf. A000142 (column 1), A001499 (column 2), A001501 (column 3), A058528 (column 4), A075754 (column 5), A172544 (column 6), A172541 (column 7), A172536 (column 8), A172540 (column 9), A172535 (column 11), A172534 (column 12), A172538 (column 13), A172537 (column 14).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|