|
| |
|
|
A212855
|
|
T(n,k) = number of n X k arrays with rows being permutations of 0..k-1 and no column j greater than column j-1 in all rows (n, k >= 1).
|
|
20
|
|
|
|
1, 1, 1, 1, 3, 1, 1, 19, 7, 1, 1, 211, 163, 15, 1, 1, 3651, 8983, 1135, 31, 1, 1, 90921, 966751, 271375, 7291, 63, 1, 1, 3081513, 179781181, 158408751, 7225951, 45199, 127, 1, 1, 136407699, 53090086057, 191740223841, 21855093751, 182199871, 275563, 255, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
In other words, there are no "column rises", where a "column rise" means a pair of adjacent columns where each entry in the left column is strictly less than the adjacent entry in the right column.
This is R(n,k,0) in [Abramson-Promislow].
As stated above, in the notation of Abramson and Promislow (1978), we have T(n,k) = R(n, k, t=0).
Let P_k be the set of all lists a = (a_1, a_2, ..., a_k) of integers a_i >= 0, i = 1, ..., k, such that 1*a_1 + 2*a_2 + ... + k*a_k = k; i.e., P_k is the set all integer partitions of k. Then |P_k| = A000041(k).
From Eq. (6), p. 248, in Abramson and Promislow (1978), with t=0, we get T(n,k) = Sum_{a in P_k} (-1)^(k - Sum_{j=1..k} a_j) * (a_1 + a_2 + ... + a_k)!/(a_1! * a_2! * ... * a_k!) * (k! / ((1!)^a_1 * (2!)^a_2 * ... * (k!)^a_k))^n.
The integer partitions of k = 1..10 are listed on pp. 831-832 of Abramowitz and Stegun (1964). We see that, for k = 1..6, the corresponding multinomial coefficients k! / ((1!)^a_1 * (2!)^a_2 * ... * (k!)^a_k) are all distinct; that is, A070289(k) = A000041(k) and A309951(k,s) = A325305(k,s) for s = 0..A000041(k). For 7 <= k <= 10, this is not true anymore; i.e., A070289(k) < A000041(k) for 7 <= k <= 10 (and we conjecture that this is the case for all k >= 7).
From the theory of difference equations, we see that Abramson and Promislow's Eq. (6) on p. 248 (with t=0) implies that Sum_{s = 0..A070289(k)} (-1)^s * A325305(k,s) * T(n-s,k) = 0 for n >= A070289(k) + 1. For k = 1..5, these recurrences give R. H. Hardin's empirical recurrences shown in the Formula section below.
We also have Sum_{s = 0..A000041(k)} (-1)^s * A309951(k,s) * T(n-s,k) = 0 for n >= A000041(k) + 1, but for k >= 7, the recurrence we get (for column k) may not necessarily be minimal.
To derive the recurrence for row n, let y=0 in Eq. (8), p. 249, of Abramson and Promislow (1978). We get 1 + Sum_{k >= 1} T(n,k)*x^k/(k!)^n = 1/f_n(-x), where f_n(x) = Sum_{i >= 0} (x^i/(i!)^n). Matching coefficients, we get Sum_{s = 1..k} T(n,s) * (-1)^(s-1) * binomial(k,s)^n = 1, from which the recurrence in the Formula section follows.
(End)
|
|
|
LINKS
|
Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250. MR0469773 (57 #9554); see Eqs. (6) on p. 248 and (8) on p. 249 with t=0.
|
|
|
FORMULA
|
Empirical recurrence for column k:
k=1: a(n) = 1*a(n-1).
k=2: a(n) = 3*a(n-1) - 2*a(n-2).
k=3: a(n) = 10*a(n-1) - 27*a(n-2) + 18*a(n-3).
k=4: a(n) = 47*a(n-1) - 718*a(n-2) + 4416*a(n-3) - 10656*a(n-4) + 6912*a(n-5).
k=5: a(n) = 246*a(n-1) - 20545*a(n-2) + 751800*a(n-3) - 12911500*a(n-4) + 100380000*a(n-5) - 304200000*a(n-6) + 216000000*a(n-7).
[All the "empirical" recurrences above are correct. See the comments above.]
T(n,1) = T(1,n) = 1.
T(n,2) = 2^n - 1 since the only n X 2 matrix with rows permutations of {0,1} which has a column rise is the one where all rows are [0,1].
(k!)^n*(1 - (k-1)/2^n) <= T(n,k) <= (k!)^n (the first inequality is (11) in the Abramson-Promislow reference, the second is trivial). (End)
For r >= 1, A(n, r) = Sum_{k=0..n} |[x^k] n!^r [z^n] S(r, z)^x| where S(r, z) = Sum_{k>=0} z^k/k!^r. - Peter Luschny, Feb 27 2018
Recurrence for column k: Sum_{s = 0..A070289(k)} (-1)^s * A325305(k,s) * T(n-s,k) = 0 for n >= A070289(k) + 1.
Recurrence for row n: T(n,k) = (-1)^(k-1) + Sum_{s = 1..k-1} T(n,s) * (-1)^(k-s-1) * binomial(k,s)^n for k >= 1.
(End)
Sum_{k>=1} T(n,k)*z^k/(k!)^n = 1/E_n(-z) -1 where E_n(z) = Sum_{k>=0} z^k/(k!)^n. - Geoffrey Critzer, Apr 28 2023
|
|
|
EXAMPLE
|
Some solutions for n=3 and k=4:
2 1 3 0 1 3 0 2 3 0 2 1 1 3 0 2 1 3 2 0
2 0 1 3 1 3 0 2 3 1 2 0 1 0 3 2 1 3 0 2
2 3 0 1 3 0 2 1 2 3 1 0 2 0 3 1 3 1 0 2
Table starts:
1 1 1 1 1 1 1
1 3 19 211 3651 90921 3081513
1 7 163 8983 966751 179781181 53090086057
1 15 1135 271375 158408751 191740223841 429966316953825
1 31 7291 7225951 21855093751 164481310134301 2675558106868421881
1 63 45199 182199871 2801736968751 128645361626874561 14895038886845467640193
|
|
|
MAPLE
|
A212855_row := proc(m, len) proc(n, m) sum(z^k/k!^m, k = 0..infinity);
series(%^x, z=0, n+1): n!^m*coeff(%, z, n); [seq(coeff(%, x, k), k=0..n)] end;
seq(add(abs(k), k=%(j, m)), j=1..len) end:
# second Maple program:
T:= proc(n, k) option remember; `if`(k=0, 1, -add(
binomial(k, j)^n*(-1)^j*T(n, k-j), j=1..k))
end:
|
|
|
MATHEMATICA
|
rows = 9;
row[m_, len_] := Module[{p, s0, s1, s2}, p = Function[{n, m0}, s0 = Sum[ z^k/k!^m0, {k, 0, n}]; s1 = Series[s0^x, {z, 0, n+1}] // Normal; s2 = n!^m0*Coefficient[s1, z, n]; Table[Coefficient[s2, x, k], {k, 0, n}]]; Table[Sum[Abs[k], {k, p[j, m]}], {j, 1, len}]];
T = Table[row[n, rows+1], {n, 1, rows}];
Table[T[[n-k+1, k]], {n, 1, rows}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Feb 27 2018, after Peter Luschny *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
