login
This site is supported by donations 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. 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.

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.]

Wikipedia, Partition (number theory).

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.

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

Sequence in context: A157586 A042439 A212845 * A030258 A154737 A285488

Adjacent sequences:  A212803 A212804 A212805 * A212807 A212808 A212809

KEYWORD

nonn,changed

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 19 08:28 EDT 2019. Contains 327187 sequences. (Running on oeis4.)