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

1, 211, 8983, 271375, 7225951, 182199871, 4479288703, 108787179775, 2626338801151, 63217691436031, 1519452489242623, 36493601345048575, 876167372044132351, 21031868446675976191, 504811062363654815743, 12116020140998121291775, 290791139166323355287551

Offset: 1

Author

R. H. Hardin, May 28 2012

Keywords

• nonn

Comments

Column 4 of A212855.

From Petros Hadjicostas, Aug 25 2019: (Start)

All formulas below follow from the theory in the documentation of array A309951.

We have Sum_{s = 0..A000041(4)} (-1)^s * A309951(4,s) * a(n-s) = 0, i.e., a(n) - 47*a(n-1) + 718*a(n-2) - 4416*a(n-3) + 10656*a(n-4) - 6912*a(n-5) = 0 for n >= 6. This is a consequence of Eq. (6) on p. 248 of Abramson and Promislow (1978).

Note that in R. J. Mathar's formula a(n) = 24^n + 6^n - 3*12^n + 2*4^n - 1^n, the numbers 1, 4, 12, 6, and 24 (that are raised to the n-th power) are the multinomial coefficients of the A000041(4) = 5 integer partitions of 4: 4!/4! = 1, 4!/(1!3!) = 4, 12 = 4!/(1!1!2!), 6 = 4!/(2!2!), 24 = 4!/(1!1!1!1!).

Note also that these numbers appear also in the denominator of the Colin Barker's g.f.: (1 - x)*(1 - 4*x)*(1 - 6*x)*(1 - 12*x)*(1 - 24*x) = 1 - 47*x + 718*x^2 - 4416*x^3 + 10656*x^4 - 6912*x^5. (End)

Examples

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

Links

• R. H. Hardin, Table of n, a(n) for n = 1..210
• Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250; see Eq. (6) on p. 248 (set t:=0).

Crossrefs

Cf. A000041, A212850, A212852, A212853, A212854, A212855, A212856, A309951.

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

Formula

Empirical: a(n) = 47*a(n-1) - 718*a(n-2) + 4416*a(n-3) - 10656*a(n-4) + 6912*a(n-5).

Empirical: a(n) = 24^n + 6^n - 3*12^n + 2*4^n - 1. R. J. Mathar, Jun 25 2012

Empirical g.f.: x*(1 + 164*x - 216*x^2 - 3744*x^3) / ((1 - x)*(1 - 4*x)*(1 - 6*x)*(1 - 12*x)*(1 - 24*x)). - Colin Barker, Jul 21 2018