login
A212853
Number of n X 6 arrays with rows being permutations of 0..5 and no column j greater than column j-1 in all rows.
13
1, 90921, 179781181, 191740223841, 164481310134301, 128645361626874561, 96426023622482278621, 70816637331790329140481, 51492108377805402906874141, 37256471170472317193421713601, 26890352949868734582700237312861
OFFSET
1,2
COMMENTS
Column 6 of A212855.
From Petros Hadjicostas, Sep 08 2019: (Start)
Let P_6 be the set of all lists b = (b_1, b_2, b_3, b_4, b_5, b_6) of integers b_i >= 0, i = 1, ..., 6, such that 1*b_1 + 2*b_2 + 3*b_3 + 4*b_4 + 5*b_5 + 6*b_6 = 6; i.e., P_6 is the set all integer partitions of 6. Then |P_6| = A000041(6) = 11.
From Eq. (6), p. 248, in Abramson and Promislow (1978), with t=0, we get a(n) = A212855(n,6) = Sum_{b in P_6} (-1)^(6-Sum_{j=1..6} b_j) * (b_1 + b_2 + b_3 + b_4 + b_5 + b_6)!/(b_1! * b_2! * b_3! * b_4! * b_5! * b_6!) * (6! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5 * (6!)^b_6))^n.
The integer partitions of 6 are listed on p. 831 of Abramowitz and Stegun (1964). We see that the corresponding multinomial coefficients 6! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5 * (6!)^b_6) are all distinct; that is, A070289(6) = A000041(6) = 11 and A309951(6,s) = A325305(6,s) for s = 0..11. (Compare with the comments for A212854.)
Using the information about partitions of 6 in Eq. (6) (with t=0), p. 248, of Abramson and Promislow (1978), we may derive the explicit equation for a(n) shown below.
Using standard results from the theory of difference equations (since the solution is known explicitly), we may derive R. H. Hardin's empirical recurrence. The recurrence is equivalent to Sum_{s = 0..11} (-1)^s * A325305(6,s) * a(n-s) = 0 for n >= 12.
(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) (with t=0), p. 248, and the comments above.
FORMULA
Empirical: a(n) = 1602*a(n-1) - 929171*a(n-2) + 260888070*a(n-3) - 39883405500*a(n-4) + 3492052425000*a(n-5) - 177328940580000*a(n-6) + 5153150631600000*a(n-7) - 82577533320000000*a(n-8) + 669410956800000000*a(n-9) - 2224399449600000000*a(n-10) + 1632586752000000000*a(n-11) for n >= 12. [It is correct; see the comments above.]
a(n) = -1 + 2*6^n + 2*15^n + 20^n - 3*30^n - 6*60^n - 90^n + 4*120^n + 6*180^n - 5*360^n + 720^n for n >= 1. - Petros Hadjicostas, Sep 08 2019
EXAMPLE
Some solutions for n=3:
0 3 1 4 2 5 0 3 1 4 2 5 0 3 1 4 2 5 0 3 1 4 2 5
3 0 2 4 5 1 1 3 0 4 5 2 4 0 3 1 2 5 0 1 5 2 3 4
1 2 4 0 3 5 5 0 4 2 3 1 2 1 5 4 3 0 3 1 5 0 4 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, 6];
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