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

%I #48 Sep 11 2019 10:21:20

%S 1,3,163,271375,21855093751,128645361626874561,

%T 78785944892341703819175577,6795588328283070704898044776213094655,

%U 107414633522643325764587104395687638119674465944431,392471529081605251407320880492124164530148025908765037878553312273,407934916447631403509359040563002566177814886353044858592046202746464825839911293037

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

%C 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 From _Petros Hadjicostas_, Aug 26 2019: (Start)

%C 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 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 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 (End)

%H 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 Milton Abramowitz and Irene A. Stegun, <a href="http://www.cs.bham.ac.uk/~aps/research/projects/as/book.php">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 Morton Abramson, 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>.

%F 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 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 For n=2 the three matrices are [12/21], [21/12], [21/21] (but not [12/12]).

%e From _Petros Hadjicostas_, Aug 26 2019: (Start)

%e 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 It follows that a(n) = (-1)^2 * 1 * 1^3 + (-1)^1 * 2 * 3^3 + (-1)^0 * 1 * 6^3 = 163.

%e (End)

%p A212806 := proc(n) sum(z^k/k!^n, k=0..infinity);

%p series(%^x, z=0, n+1): n!^n*coeff(%,z,n); add(abs(coeff(%,x,k)),k=0..n) end:

%p seq(A212806(n), n=1..11); # _Peter Luschny_, May 27 2017

%t 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_ *)

%Y A212805 is a lower bound.

%Y Main diagonal of A212855.

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

%K nonn

%O 1,2

%A _N. J. A. Sloane_, May 27 2012

%E Corrected by _R. H. Hardin_, May 28 2012

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 16:34 EDT 2024. Contains 371254 sequences. (Running on oeis4.)