|
%I #42 Apr 01 2024 06:27:57
%S 1,90921,179781181,191740223841,164481310134301,128645361626874561,
%T 96426023622482278621,70816637331790329140481,
%U 51492108377805402906874141,37256471170472317193421713601,26890352949868734582700237312861
%N 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 Column 6 of A212855.
%C From _Petros Hadjicostas_, Sep 08 2019: (Start)
%C 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 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 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 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 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 (End)
%H R. H. Hardin, <a href="/A212853/b212853.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>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multinomial_theorem">Multinomial theorem</a>.
%F 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 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 Some solutions for n=3:
%e 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 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 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 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, 6];
%t Table[a[n], {n, 1, 12}] (* _Jean-François Alcover_, Apr 01 2024, after _Alois P. Heinz_ in A212855 *)
%Y Cf. A000041, A070289, A212850, A212851, A212852, A212854, A212855, A212856, A212857, A309951, A325305.
%K nonn
%O 1,2
%A _R. H. Hardin_, May 28 2012
| 