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

1, 19, 163, 1135, 7291, 45199, 275563, 1666495, 10038331, 60348079, 362442763, 2175719455, 13057505371, 78354598159, 470156286763, 2821023814015, 16926401164411, 101559181827439, 609357415487563, 3656151466494175

Offset

1,2

Comments

From Petros Hadjicostas, Aug 25 2019: (Start)

Both formulas below follow from the theory in the documentation of array A309951. We have Sum_{s = 0..A000041(3)} (-1)^s * A309951(3,s) * a(n-s) = 0, i.e., a(n) - 10*a(n-1) - 27*a(n-2) + 18*a(n-3) = 0 for n >= 4. This is a consequence of Eq. (6) on p. 248 of Abramson and Promislow (1978), where we let t=0 in the equation.

In the explicit formula by Vaclav Kotesovec below, a(n) = 6^n - 2*3^n + 1^n, the numbers 1, 3, 6 (that are raised to the n-th power) are the multinomial coefficients of the A000041(3) = 3 integer partitions of 3: 1 = 3!/3!, 3 = 3!/(1!2!), 6 = 3!/(1!1!1!).

(End)

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).

Formula

Empirical: a(n) = 10*a(n-1) - 27*a(n-2) + 18*a(n-3).

Explicit formula: a(n) = 6^n - 2*3^n + 1. - Vaclav Kotesovec, May 31 2012

Example

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

Crossrefs

Column 3 of A212855.

Cf. A000041, A212851, A212852, A212852, A212853, A212854, A212856, A309951.

Sequence in context: A159682 A197500 A341398 * A215115 A142128 A158966

Adjacent sequences: A212847 A212848 A212849 * A212851 A212852 A212853

Keyword

nonn

Author

R. H. Hardin, May 28 2012

Status

approved