A212806 Number of n X n matrices in which each row is a permutation of [1..n] and which contain no column rises.

1, 3, 163, 271375, 21855093751, 128645361626874561, 78785944892341703819175577, 6795588328283070704898044776213094655, 107414633522643325764587104395687638119674465944431, 392471529081605251407320880492124164530148025908765037878553312273, 407934916447631403509359040563002566177814886353044858592046202746464825839911293037

Offset: 1

Author

N. J. A. Sloane, May 27 2012

Keywords

• nonn

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)

Examples

			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)
		

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 and 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.]
• Wikipedia, Partition (number theory).

Crossrefs

A212805 is a lower bound.

Main diagonal of A212855.

Cf. A000041, A070289, A212850, A212851, A212852, A212853, A212854, A212856, A212857, A212858, A212859, A212860, A309951, A325305.

Programs

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 *)
T[n_, k_] := T[n, k] = If[k == 0, 1, -Sum[Binomial[k, j]^n*(-1)^j*T[n, k-j], {j, 1, k}]];
a[n_] := T[n, n];
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

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.

Extensions

Corrected by R. H. Hardin, May 28 2012