login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A212806 Number of n X n matrices in which each row is a permutation of [1..n] and which contain no column rises. 5
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.
From Petros Hadjicostas, Aug 26 2019: (Start)
Let R(m,n) := R(m,n,t=0) = A212855(m,n) for m,n >= 1, where R(m,n,t) = LHS of Eq. (6) of Abramson and Promislow (1978, p. 248).
Let P_n be the set of all lists b = (b_1, b_2,..., b_n) of integers b_i >= 0, i = 1,..., n, such that 1*b_1 + 2*b_2 + ... + n*b_n = n; i.e., P_n is the set all integer partitions of n. Then |P_n| = A000041(n) for n >= 0.
We have a(n) = R(n,n) = A212855(n,n) = Sum_{b in P_n} (-1)^(n - Sum_{j=1..n} b_j) * (b_1 + b_2 + ... + b_n)!/(b_1! * b_2! * ... * b_n!) * (n! / ((1!)^b_1 * (2!)^b_2 * ... * (n!)^b_n)^n.
(End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..30 (first 18 terms from R. H. Hardin)
Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards (Applied Mathematics Series, 55), 1964; see pp. 831-832 for the multinomial coefficients of integer partitions of n = 1..10.
Morton Abramson, David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250. MR0469773 (57 #9554). [Their a(5) on p. 250 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]).
From Petros Hadjicostas, Aug 26 2019: (Start)
For example, when n = 3, the integer partitions of 3 are 3, 1+2, and 1+1+1, with corresponding (b_1, b_2, b_3) notation (0,0,1), (1,1,0), and (3,0,0). The corresponding multinomial coefficients are 3!/3! = 1, 3!/(1!2!) = 3, and 3!/(1!1!1!) = 6, while the corresponding quantities (b_1 + b_2 + b_3)!/(b_1!*b_2!*b_3!) are 1, 2, and 1. The corresponding exponents of -1 (i.e., n - Sum_{j = 1..n} b_j}) are 3 -(0+0+1) = 2, 3 - (1+1+0) = 1, and 3 - (3+0+0) = 0.
It follows that a(n) = (-1)^2 * 1 * 1^3 + (-1)^1 * 2 * 3^3 + (-1)^0 * 1 * 6^3 = 163.
(End)
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.
Main diagonal of A212855.
Sequence in context: A042439 A364302 A212845 * A368600 A030258 A154737
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, May 27 2012
EXTENSIONS
Corrected by R. H. Hardin, May 28 2012
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 17:42 EDT 2024. Contains 371254 sequences. (Running on oeis4.)