A212854 - OEIS

%I #60 Apr 01 2024 06:27:53

%S 1,3081513,53090086057,429966316953825,2675558106868421881,

%T 14895038886845467640193,78785944892341703819175577,

%U 406643086764765052892275303425,2073826171428339544452057104498041

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

%C From _Petros Hadjicostas_, Aug 25 2019: (Start)

%C We have a(m) = R(m,n=7,t=0) = A212855(m,7) for m >= 1, where R(m,n,t) = LHS of Eq. (6) of Abramson and Promislow (1978, p. 248).

%C Let P_7 be the set of all lists b = (b_1, b_2,..., b_7) of integers b_i >= 0, i = 1, ..., 7 such that 1*b_1 + 2*b_2 + ... + 7*b_7 = 7; i.e., P_7 is the set all integer partitions of 7. Then |P_7| = A000041(7) = 15.

%C We have a(m) = A212855(m,7) = Sum_{b in P_7} (-1)^(7 - Sum_{j=1..7} b_j) * (b_1 + b_2 + ... + b_7)!/(b_1! * b_2! * ... * b_7!) * (7! / ((1!)^b_1 * (2!)^b_2 * ... * (7!)^b_7))^m.

%C The integer partitions of 7 are listed on p. 831 of Abramowitz and Stegun (1964). We see that, when (b_1, b_2, ..., b_7) = (0, 2, 1, 0, 0, 0, 0) or (3, 0, 0, 1, 0, 0, 0) (i.e., we have the partitions 2+2+3 and 1+1+1+4), the corresponding multinomial coefficients are 210 = 7!/(2!2!3!) = 7!/(1!1!1!4!), so the number of terms in the expression for a(m) is |P_7| - 1 = 15 - 1 = 14 (see below in the Formula section).

%C Let M_7 := [1, 7, 21, 35, 42, 105, 140, 210, 420, 630, 840, 1260, 2520, 5040] be the A070289(7) = 15 - 1 = 14 distinct multinomial coefficients corresponding to the 15 integer partitions of 7 in P_7. The characteristic equation of the recurrence for a(m) is f(x) := Product_{r in M_7} (x-r) = Sum_{i = 0..14} (-1)^{14-i} * c_i * x^i. It turns out that c_{14} = 1, c_{13} = 11271, c_{12} = 46169368, c_{11} = 92088653622, and so on (see _R. H. Hardin_'s recurrence below), and c_0 = 2372695722072874920960000000000 = product of elements in M_7.

%C It follows that a(m) satisfies the recurrence Sum_{i = 0..14} (-1)^{14-i} * c_i * a(m-i) = 0, which is equivalent to  _R. H. Hardin_'s empirical recurrence below.

%C If we count the multinomial coefficient 210 twice in the characteristic equation (since it corresponds to two different integer partitions of 7) then we get (x-210)*f(x) = Sum_{i = 0..15} (-1)^{15-i} * d_i * x^i, where (d_0, d_1, ..., d_15) is row k = 7 in irregular triangular array A309951. We have d_{15} = 1, d_{14} = 11481, ..., d_0 = 498266101635303733401600000000000 (see _Alois P. Heinz_'s b-file for A309951 with entries 37 to 52). Note that d_0 = 210 * c_0.

%C We then have Sum_{s = 0..15} (-1)^s * A309951(7, s) * a(m-s) = 0 for m >= 16. The latter recurrence is of order 15, and it is not minimal (as opposed to the one below by _R. H. Hardin_, which is of order 14 and minimal).

%C (End)

%H R. H. Hardin, <a href="/A212854/b212854.txt">Table of n, a(n) for n = 1..210</a>

%H Milton Abramowitz and Irene A. Stegun, <a href="http://www.cs.bham.ac.uk/~aps/research/projects/as/book.php">Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables</a>, National Bureau of Standards (Applied Mathematics Series, 55), 1964; see pp. 831-832 for the multinomial coefficients of integer partitions of n = 1..10.

%H Morton Abramson and David Promislow, <a href="https://doi.org/10.1016/0097-3165(78)90012-2">Enumeration of arrays by column rises</a>, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250; see Eq. (6) (with t=0), p. 248, and the comments above.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>.

%F Empirical: a(n) = 11271*a(n-1) -46169368*a(n-2) +92088653622*a(n-3) -100896701243149*a(n-4) +64220064122517975*a(n-5) -24283767237355832850*a(n-6) +5479502670227877007500*a(n-7) -734487423806273666445000*a(n-8) +57519812656973505919500000*a(n-9) -2547756421856270328438000000*a(n-10) +60760702040873540340600000000*a(n-11) -700874827794270417254400000000*a(n-12) +3015300813467611878720000000000*a(n-13) -2372695722072874920960000000000*a(n-14). [It is correct; see the comments above and one of the formulas below.]

%F a(n) = 1 - 2*7^n - 2*21^n - 2*35^n + 3*42^n + 6*105^n + 3*140^n - 210^n - 12*420^n - 4*630^n + 5*840^n + 10*1260^n - 6*2520^n + 5040^n. - _Petros Hadjicostas_, Aug 25 2019

%F Sum_{s = 0..14} (-1)^s * A325305(7, s) * a(n-s) = 0 for n >= 15. (This is the same as _R. H. Hardin_'s recurrence above, and it follows from Eq. (6), p. 248, in Abramson and Promislow (1978) with t=0.) - _Petros Hadjicostas_, Sep 06 2019

%e Some solutions for n=3

%e ..0..3..4..1..5..2..6....0..3..4..1..5..2..6....0..3..4..1..5..2..6

%e ..1..0..3..5..2..6..4....1..0..3..2..4..5..6....1..0..4..2..5..6..3

%e ..5..2..1..0..6..3..4....4..6..5..1..0..3..2....2..4..0..6..3..5..1

%t T[n_, k_] := T[n, k] = If[k == 0, 1, -Sum[Binomial[k, j]^n*(-1)^j*T[n, k - j], {j, 1, k}]];

%t a[n_] := T[n, 7];

%t Table[a[n], {n, 1, 12}] (* _Jean-François Alcover_, Apr 01 2024, after _Alois P. Heinz_ in A212855 *)

%Y Column 7 of A212855.

%Y Cf. A000041, A070289, A212850, A212851, A212852, A212853, A212856, A309951, A325305.

%K nonn

%O 1,2

%A _R. H. Hardin_, May 28 2012