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

1, 1, 63, 45199, 182199871, 2801736968751, 128645361626874561, 14895038886845467640193, 3842738508408709445398181439, 2009810719756197663340563540778591, 1977945985139308994141721986912910579313, 3448496643225334129810790241492300508936547073

Offset: 0

Author

R. H. Hardin, May 28 2012

Keywords

• nonn

Comments

From Petros Hadjicostas, Sep 08 2019: (Start)

We generalize Daniel Suteu's recurrence from A212856. Notice first that, in the notation of Abramson and Promislow (1978), we have a(n) = R(m=6, n, t=0).

Letting y=0 in Eq. (8), p. 249, of Abramson and Promislow (1978), we get 1 + Sum_{n >= 1} R(m,n,t=0)*x^n/(n!)^m = 1/f(-x), where f(x) = Sum_{i >= 0} (x^i/(i!)^m). Matching coefficients, we get Sum_{s = 1..n} R(m, s, t=0) * (-1)^(s-1) * binomial(n,s)^m = 1, from which the recurrence in the Formula section follows.

(End)

Examples

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

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..104 (terms n=1..19 from R. H. Hardin)
• Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250; see Eq. (8) on p. 249.

Crossrefs

Row 6 of A212855.

Cf. A000012, A000225, A000275, A212850, A212851, A212852, A212853, A212854, A212856, A212857, A212858, A212860.

Programs

Maple

A212859 := proc(n) sum(z^k/k!^6, k = 0..infinity);
series(%^x, z=0, n+1): n!^6*coeff(%,z,n); add(abs(coeff(%,x,k)), k=0..n) end:
seq(A212859(n), n=1..11); # Peter Luschny, May 27 2017

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

Formula

a(n) = (-1)^(n-1) + Sum_{s = 1..n-1} a(s) * (-1)^(n-s-1) * binomial(n,s)^m for n >= 2 with a(1) = 1. Here m = 6. - Petros Hadjicostas, Sep 08 2019

a(n) = (n!)^6 * [x^n] 1 / (1 + Sum_{k>=1} (-x)^k / (k!)^6). (see Petros Hadjicostas's comment on Sep 08 2019) - Seiichi Manyama, Jul 18 2020

Extensions

a(0)=1 prepended by Seiichi Manyama, Jul 18 2020