|
| |
|
|
A212806
|
|
Number of n X n matrices in which each row is a permutation of [1..n] and which contain no column rises.
|
|
4
|
|
|
|
1, 3, 163, 271375, 21855093751, 128645361626874561, 78785944892341703819175577, 6795588328283070704898044776213094655, 107414633522643325764587104395687638119674465944431, 392471529081605251407320880492124164530148025908765037878553312273, 407934916447631403509359040563002566177814886353044858592046202746464825839911293037
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
A column rise in a matrix M=(m_{i,j}) is a value of j such that m_{i,j} < m_{i,j+1} for all i = 1..n.
|
|
|
LINKS
|
R. H. Hardin, Table of n, a(n) for n = 1..18
Morton Abramson, David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24 (1978), no. 2, 247--250. MR0469773 (57 #9554). [their a(5) is wrong, see A212845]
|
|
|
FORMULA
|
Abramson and Promislow give a g.f. for R(m,n,t), the number of m X n matrices in which each row is a permutation of [1..n] and which contain exactly t column rises:
1 + Sum_{n>=1} Sum_{t=0..n-1} R(m,n,t) y^t x^n/(n!)^m = (y-1)/(y-f(x(y-1))) where f(x) = Sum_{i>=0} x^i/(i!)^m.
|
|
|
EXAMPLE
|
For n=2 the three matrices are [12/21], [21/12], [21/21] (but not [12/12]).
|
|
|
MAPLE
|
A212806 := proc(n) sum(z^k/k!^n, k=0..infinity);
series(%^x, z=0, n+1): n!^n*coeff(%, z, n); add(abs(coeff(%, x, k)), k=0..n) end:
seq(A212806(n), n=1..11); # Peter Luschny, May 27 2017
|
|
|
MATHEMATICA
|
a[n_] := Module[{s0, s1, s2}, s0 = Sum[z^k/k!^n, {k, 0, n}]; s1 = Series[s0^x, {z, 0, n + 1}] // Normal; s2 = n!^n*Coefficient[s1, z, n]; Sum[Abs[Coefficient[s2, x, k]], {k, 0, n}]]; Array[a, 11] (* Jean-François Alcover, Feb 27 2018, after Peter Luschny *)
|
|
|
CROSSREFS
|
A212805 is a lower bound.
Diagonal of A212855.
Sequence in context: A157586 A042439 A212845 * A030258 A154737 A285488
Adjacent sequences: A212803 A212804 A212805 * A212807 A212808 A212809
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
N. J. A. Sloane, May 27 2012
|
|
|
EXTENSIONS
|
Corrected by R. H. Hardin, May 28 2012
|
|
|
STATUS
|
approved
|
| |
|
|
