cp's OEIS Frontend

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

%I A212806 #59 Jul 14 2025 15:20:54
%S A212806 1,3,163,271375,21855093751,128645361626874561,
%T A212806 78785944892341703819175577,6795588328283070704898044776213094655,
%U A212806 107414633522643325764587104395687638119674465944431,392471529081605251407320880492124164530148025908765037878553312273,407934916447631403509359040563002566177814886353044858592046202746464825839911293037
%N A212806 Number of n X n matrices in which each row is a permutation of [1..n] and which contain no column rises.
%C A212806 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.
%C A212806 From _Petros Hadjicostas_, Aug 26 2019: (Start)
%C A212806 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).
%C A212806 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.
%C A212806 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.
%C A212806 (End)
%H A212806 Alois P. Heinz, <a href="/A212806/b212806.txt">Table of n, a(n) for n = 1..30</a> (first 18 terms from R. H. Hardin)
%H A212806 Milton Abramowitz and Irene A. Stegun, <a href="https://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables</a>, National Bureau of Standards (Applied Mathematics Series, 55), 1964; see pp. 831-832 for the multinomial coefficients of integer partitions of n = 1..10.
%H A212806 Morton Abramson and David Promislow, <a href="https://doi.org/10.1016/0097-3165(78)90012-2">Enumeration of arrays by column rises</a>, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250. MR0469773 (57 #9554). [Their a(5) on p. 250 is wrong; see A212845.]
%H A212806 Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>.
%F A212806 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:
%F A212806 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.
%e A212806 For n=2 the three matrices are [12/21], [21/12], [21/21] (but not [12/12]).
%e A212806 From _Petros Hadjicostas_, Aug 26 2019: (Start)
%e A212806 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.
%e A212806 It follows that a(n) = (-1)^2 * 1 * 1^3 + (-1)^1 * 2 * 3^3 + (-1)^0 * 1 * 6^3 = 163.
%e A212806 (End)
%p A212806 A212806 := proc(n) sum(z^k/k!^n, k=0..infinity);
%p A212806 series(%^x, z=0, n+1): n!^n*coeff(%,z,n); add(abs(coeff(%,x,k)),k=0..n) end:
%p A212806 seq(A212806(n), n=1..11); # _Peter Luschny_, May 27 2017
%t A212806 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 A212806 T[n_, k_] := T[n, k] = If[k == 0, 1, -Sum[Binomial[k, j]^n*(-1)^j*T[n, k-j], {j, 1, k}]];
%t A212806 a[n_] := T[n, n];
%t A212806 Table[a[n], {n, 1, 12}] (* _Jean-François Alcover_, Apr 01 2024, after _Alois P. Heinz_ in A212855 *)
%Y A212806 A212805 is a lower bound.
%Y A212806 Main diagonal of A212855.
%Y A212806 Cf. A000041, A070289, A212850, A212851, A212852, A212853, A212854, A212856, A212857, A212858, A212859, A212860, A309951, A325305.
%K A212806 nonn
%O A212806 1,2
%A A212806 _N. J. A. Sloane_, May 27 2012
%E A212806 Corrected by _R. H. Hardin_, May 28 2012