cp's OEIS Frontend

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.

%I A212853 #43 Jul 14 2025 15:20:54
%S A212853 1,90921,179781181,191740223841,164481310134301,128645361626874561,
%T A212853 96426023622482278621,70816637331790329140481,
%U A212853 51492108377805402906874141,37256471170472317193421713601,26890352949868734582700237312861
%N 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.
%C A212853 Column 6 of A212855.
%C A212853 From _Petros Hadjicostas_, Sep 08 2019: (Start)
%C A212853 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.
%C A212853 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.
%C A212853 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.)
%C A212853 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.
%C A212853 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.
%C A212853 (End)
%H A212853 R. H. Hardin, <a href="/A212853/b212853.txt">Table of n, a(n) for n = 1..210</a>
%H A212853 Milton Abramowitz and Irene A. Stegun, <a href="https://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">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 A212853 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 A212853 Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>.
%H A212853 Wikipedia, <a href="https://en.wikipedia.org/wiki/Multinomial_theorem">Multinomial theorem</a>.
%F A212853 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.]
%F A212853 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
%e A212853 Some solutions for n=3:
%e A212853   0 3 1 4 2 5   0 3 1 4 2 5   0 3 1 4 2 5   0 3 1 4 2 5
%e A212853   3 0 2 4 5 1   1 3 0 4 5 2   4 0 3 1 2 5   0 1 5 2 3 4
%e A212853   1 2 4 0 3 5   5 0 4 2 3 1   2 1 5 4 3 0   3 1 5 0 4 2
%t A212853 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 A212853 a[n_] := T[n, 6];
%t A212853 Table[a[n], {n, 1, 12}] (* _Jean-François Alcover_, Apr 01 2024, after _Alois P. Heinz_ in A212855 *)
%Y A212853 Cf. A000041, A070289, A212850, A212851, A212852, A212854, A212855, A212856, A212857, A309951, A325305.
%K A212853 nonn
%O A212853 1,2
%A A212853 _R. H. Hardin_, May 28 2012