login
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.
13
1, 3651, 966751, 158408751, 21855093751, 2801736968751, 347190069843751, 42328368099218751, 5119530150996093751, 616756797369980468751, 74155772004699902343751, 8907394925520999511718751
OFFSET
1,2
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)
LINKS
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).
FORMULA
Empirical: a(n) = 246*a(n-1) -20545*a(n-2) +751800*a(n-3) -12911500*a(n-4) +100380000*a(n-5) -304200000*a(n-6) +216000000*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
EXAMPLE
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
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 *)
KEYWORD
nonn
AUTHOR
R. H. Hardin, May 28 2012
STATUS
approved