A212852 Number of n X 5 arrays with rows being permutations of 0..4 and no column j greater than column j-1 in all rows.

1, 3651, 966751, 158408751, 21855093751, 2801736968751, 347190069843751, 42328368099218751, 5119530150996093751, 616756797369980468751, 74155772004699902343751, 8907394925520999511718751

Offset: 1

Author

R. H. Hardin, May 28 2012

Keywords

• nonn

Comments

Column 5 of A212855.

From Petros Hadjicostas, Sep 06 2019: (Start)

Let P_5 be the set of all lists b = (b_1, b_2, b_3, b_4, b_5) of integers b_i >= 0, i = 1, ..., 5, such that 1*b_1 + 2*b_2 + 3*b_3 + 4*b_4 + 5*b_5 = 5; i.e., P_5 is the set all integer partitions of 5. Then |P_5| = A000041(5) = 7.

From Eq. (6), p. 248, in Abramson and Promislow (1978), we get a(n) = A212855(n,5) = Sum_{b in P_5} (-1)^(5 - Sum_{j=1..5} b_j) * (b_1 + b_2 + b_3 + b_4 + b_5)!/(b_1! * b_2! * b_3! * b_4! * b_5!) * (5! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5))^n.

The integer partitions of 5 are listed on p. 831 of Abramowitz and Stegun (1964). We see that the corresponding multinomial coefficients 5! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5) are all distinct; that is, A070289(5) = A000041(5) = 7.

Using the integer partitions of 5 and the above formula for a(n), we may derive R. J. Mathar's formula below.

(End)

Examples

			Some solutions for n=3
..0..3..1..2..4....0..2..4..1..3....0..1..4..3..2....0..2..3..4..1
..1..0..4..3..2....1..0..3..2..4....1..3..0..4..2....0..4..3..1..2
..2..4..1..3..0....1..2..0..4..3....3..1..4..0..2....4..0..1..3..2
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..210
• 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; see Eq. (6), p. 248 (with t=0).
• Wikipedia, Multinomial coefficients.
• Wikipedia, Partition (number theory).

Crossrefs

Cf. A000041, A070289, A212850, A212851, A212853, A212854, A212855, A212856, A309951, A325305.

Programs

Mathematica

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, 5];
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

Formula

Empirical: a(n) = 246*a(n-1) -20545*a(n-2) +751800*a(n-3) -12911500*a(n-4) [phone]*a(n-5) -304200000*a(n-6) [phone]*a(n-7).

Empirical: a(n) = -2*5^n + 3*20^n - 4*60^n + 120^n + 3*30^n - 2*10^n + 1. R. J. Mathar, Jun 25 2012

Sum_{s = 0..7} (-1)^s * A325305(5, s) * a(n-s) = 0 for n >= 8. (This is the same as R. H. Hardin's recurrence above, and it follows from Eq. (6) (with t=0), p. 248, in Abramson and Promislow (1978).) - Petros Hadjicostas, Sep 06 2019