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.

1, 90921, 179781181, 191740223841, 164481310134301, 128645361626874561, 96426023622482278621, 70816637331790329140481, 51492108377805402906874141, 37256471170472317193421713601, 26890352949868734582700237312861

Offset: 1

Author

R. H. Hardin, May 28 2012

Keywords

• nonn

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)

Examples

			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
		

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) (with t=0), p. 248, and the comments above.
• Wikipedia, Partition (number theory).
• Wikipedia, Multinomial theorem.

Crossrefs

Cf. A000041, A070289, A212850, A212851, A212852, A212854, A212855, A212856, A212857, 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, 6];
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

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