A212856 -id:A212856 - cp's OEIS frontend

A212860 Number of 7 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, 127, 275563, 4479288703, 347190069843751, 96426023622482278621, 78785944892341703819175577, 163925632052722656731213188429183, 777880066963402408939826643081996101263, 7717574897043522397037273525233635595811018377

Offset: 0

R. H. Hardin, May 28 2012

nonn

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=7, 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)

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

Seiichi Manyama, Table of n, a(n) for n = 0..92 (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.

Row 7 of A212855.

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

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

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

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 = 7. - Petros Hadjicostas, Sep 08 2019

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

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

A325305 Irregular triangular array, read by rows: T(n,k) is the sum of the products of distinct multinomial coefficients (n_1 + n_2 + n_3 + ...)!/(n_1! * n_2! * n_3! * ...) taken k at a time, where (n_1, n_2, n_3, ...) runs over all integer partitions of n (n >= 0, 0 <= k <= A070289(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 2, 1, 10, 27, 18, 1, 47, 718, 4416, 10656, 6912, 1, 246, 20545, 751800, 12911500, 100380000, 304200000, 216000000, 1, 1602, 929171, 260888070, 39883405500, 3492052425000, 177328940580000, 5153150631600000, 82577533320000000, 669410956800000000, 2224399449600000000, 1632586752000000000, 1, 11271

Offset: 0

Petros Hadjicostas, Sep 05 2019

This array was inspired by R. H. Hardin's recurrences for the columns of array A212855. Row n has length A070289(n) + 1.
This array differs from array A309951 starting at row n = 7. Array A309951 calculates a similar sum of products of multinomial coefficients, but the multinomial coefficients do not have to be distinct. Row n of array A309951 has length A000041(n) + 1, i.e., one more than the number of partitions of n.
Let P_n be the set of all lists a = (a_1, a_2,..., a_n) of integers a_i >= 0, i = 1,..., n such that 1*a_1 + 2*a_2 + ... + n*a_n = n; i.e., P_n is the set all integer partitions of n. (We use a different notation for partitions than the one in the name of T(n,k).) Then |P_n| = A000041(n) for n >= 0.
For n = 1..6, all the multinomial coefficients n!/((1!)^a_1 * (2!)^a_2 * ... * (n!)^a^n) corresponding to lists (a_1,...,a_n) in P_n are distinct; that is, A000041(n) = A070289(n) for n = 1..6.
For n = 7, the partitions (a_1, a_2, a_3, a_4, a_5, a_6, a_7) = (0, 2, 1, 0, 0, 0, 0) (i.e., 2 + 2 + 3) and  (a_1, a_2, a_3, a_4, a_5, a_6, a_7) = (3, 0, 0, 1, 0, 0, 0) (i.e., 1 + 1 + 1 + 4) give the same multinomial coefficient: 210 = 7!/(2!2!3!) = 7!/(1!1!1!4!). Hence, A000041(7) > A070289(7).
Looking at the multinomial coefficients of the integer partitions of n = 8, 9, 10 on pp. 831-832 of Abramowitz and Stegun (1964), we see that, even in these cases, we have A000041(n) > A070289(n).

			Triangle begins as follows:
  [n=0]: 1,   1;
  [n=1]: 1,   1;
  [n=2]: 1,   3,     2;
  [n=3]: 1,  10,    27,     18;
  [n=4]: 1,  47,   718,   4416,    10656,      6912;
  [n=5]: 1, 246, 20545, 751800, 12911500, 100380000, 304200000, 216000000;
  ...
For example, when n = 3, the integer partitions of 3 are 3, 1+2, 1+1+1, and the corresponding multinomial coefficients are 3!/3! = 1, 3!/(1!2!) = 3, and 3!/(1!1!1!) = 6. They are all distinct. Then T(n=3, k=0) = 1, T(n=3, k=1) = 1 + 3 + 6 = 10, T(n=3, k=2) = 1*3 + 1*6 + 3*6 = 27, and T(n=3, k=3) = 1*3*6 = 18.
Consider the list [1, 7, 21, 35, 42, 105, 140, 210, 420, 630, 840, 1260, 2520, 5040] of the A070289(7) = 15 - 1 = 14 distinct multinomial coefficients corresponding to the 15 integer partitions of 7. Then  T(7,0) = 1, T(7,1) = 11271 (sum of the coefficients), T(7,2) = 46169368 (sum of products of every two different coefficients), T(7,3) = 92088653622 (sum of products of every three different coefficients), and so on. Finally, T(7,14) = 2372695722072874920960000000000 = product of these coefficients.

Alois P. Heinz, Rows n = 0..15, flattened
Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards (Applied Mathematics Series, 55), 1964; see pp. 831-832 for the multinomial coefficients of integer partitions of n = 1..10.
Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250; see Eq. (6), p. 248.
Wikipedia, Partition (number theory).

Cf. A000012 (column k=0), A000041, A005651, A070289, A212850, A212851, A212852, A212853, A212854, A212855, A212856, A309951, A309972, A325308 (column k=1).

g:= proc(n, i) option remember; `if`(n=0 or i=1, [n!], [{map(x->
      binomial(n, i)*x, g(n-i, min(n-i, i)))[], g(n, i-1)[]}[]])
    end:
b:= proc(n, m) option remember; `if`(n=0, 1,
      expand(b(n-1, m)*(g(m$2)[n]*x+1)))
    end:
T:= n->(p->seq(coeff(p, x, i), i=0..degree(p)))(b(nops(g(n$2)), n)):
seq(T(n), n=0..7);  # Alois P. Heinz, Sep 05 2019

g[n_, i_] := g[n, i] = If[n == 0 || i == 1, {n!}, Union[Map[Function[x, Binomial[n, i] x], g[n - i, Min[n - i, i]]], g[n, i - 1]]];
b[n_, m_] := b[n, m] = If[n == 0, 1, b[n - 1, m] (g[m, m][[n]] x + 1)];
T[n_] := CoefficientList[b[Length[g[n, n]], n], x];
T /@ Range[0, 7] // Flatten (* Jean-François Alcover, May 06 2020, after Maple *)

Sum_{k=0..A070289(n)} (-1)^k * T(n,k) = 0.

A212806 Number of n X n matrices in which each row is a permutation of [1..n] and which contain no column rises.

Original entry on oeis.org

1, 3, 163, 271375, 21855093751, 128645361626874561, 78785944892341703819175577, 6795588328283070704898044776213094655, 107414633522643325764587104395687638119674465944431, 392471529081605251407320880492124164530148025908765037878553312273, 407934916447631403509359040563002566177814886353044858592046202746464825839911293037

Offset: 1

N. J. A. Sloane, May 27 2012

nonn

A column rise in a matrix M = (m_{i,j}) is a value of j such that m_{i,j} < m_{i,j+1} for all i = 1..n.
From Petros Hadjicostas, Aug 26 2019: (Start)
Let R(m,n) := R(m,n,t=0) = A212855(m,n) for m,n >= 1, where R(m,n,t) = LHS of Eq. (6) of Abramson and Promislow (1978, p. 248).
Let P_n be the set of all lists b = (b_1, b_2,..., b_n) of integers b_i >= 0, i = 1,..., n, such that 1*b_1 + 2*b_2 + ... + n*b_n = n; i.e., P_n is the set all integer partitions of n. Then |P_n| = A000041(n) for n >= 0.
We have a(n) = R(n,n) = A212855(n,n) = Sum_{b in P_n} (-1)^(n - Sum_{j=1..n} b_j) * (b_1 + b_2 + ... + b_n)!/(b_1! * b_2! * ... * b_n!) * (n! / ((1!)^b_1 * (2!)^b_2 * ... * (n!)^b_n)^n.
(End)

			For n=2 the three matrices are [12/21], [21/12], [21/21] (but not [12/12]).
From _Petros Hadjicostas_, Aug 26 2019: (Start)
For example, when n = 3, the integer partitions of 3 are 3, 1+2, and 1+1+1, with corresponding (b_1, b_2, b_3) notation (0,0,1), (1,1,0), and (3,0,0). The corresponding multinomial coefficients are 3!/3! = 1, 3!/(1!*2!) = 3, and 3!/(1!*1!*1!) = 6, while the corresponding quantities (b_1 + b_2 + b_3)!/(b_1!*b_2!*b_3!) are 1, 2, and 1. The corresponding exponents of -1 (i.e., n - Sum_{j=1..n} b_j) are 3 - (0+0+1) = 2, 3 - (1+1+0) = 1, and 3 - (3+0+0) = 0.
It follows that a(n) = (-1)^2 * 1 * 1^3 + (-1)^1 * 2 * 3^3 + (-1)^0 * 1 * 6^3 = 163.
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..30 (first 18 terms from R. H. Hardin)
Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards (Applied Mathematics Series, 55), 1964; see pp. 831-832 for the multinomial coefficients of integer partitions of n = 1..10.
Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250. MR0469773 (57 #9554). [Their a(5) on p. 250 is wrong; see A212845.]
Wikipedia, Partition (number theory).

A212805 is a lower bound.
Main diagonal of A212855.
Cf. A000041, A070289, A212850, A212851, A212852, A212853, A212854, A212856, A212857, A212858, A212859, A212860, A309951, A325305.

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

a[n_] := Module[{s0, s1, s2}, s0 = Sum[z^k/k!^n, {k, 0, n}]; s1 =  Series[s0^x, {z, 0, n + 1}] // Normal; s2 = n!^n*Coefficient[s1, z, n]; Sum[Abs[Coefficient[s2, x, k]], {k, 0, n}]]; Array[a, 11] (* Jean-François Alcover, Feb 27 2018, after Peter Luschny *)
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[n, n];
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

Abramson and Promislow give a g.f. for R(m,n,t), the number of m X n matrices in which each row is a permutation of [1..n] and which contain exactly t column rises:

1 + Sum_{n>=1} Sum_{t=0..n-1} R(m,n,t) y^t x^n/(n!)^m = (y-1)/(y-f(x(y-1))) where f(x) = Sum_{i>=0} x^i/(i!)^m.

Corrected by R. H. Hardin, May 28 2012

A287696 Triangle read by rows, T(n,k) = (n!)^3 * [x^k] [z^n] hypergeom([], [1, 1], z)^x for n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 0, -3, 4, 0, 46, -81, 36, 0, -1899, 3916, -2592, 576, 0, 163476, -375375, 305500, -108000, 14400, 0, -25333590, 63002191, -58725000, 26370000, -5832000, 518400, 0, 6412369860, -16976577828, 17470973569, -9168390000, 2636298000, -400075200, 25401600

Offset: 0

Peter Luschny, May 30 2017

The polynomials Sum_{k=0..n} T(n,k) x^k generate the columns of A287698.

			0: [1]
1: [0,         1]
2: [0,        -3,        4]
3: [0,        46,      -81,        36]
4: [0,     -1899,     3916,     -2592,      576]
5: [0,    163476,  -375375,    305500,  -108000,    14400]
6: [0, -25333590, 63002191, -58725000, 26370000, -5832000, 518400]

T(n,n) = A001044(n).

Cf. A212856, A212855, A287314, A287698.

A287696_row := proc(n) local k; hypergeom([],[1,1],z); series(%^x, z=0, n+1):
n!^3*coeff(%, z, n); seq(coeff(%, x, k), k=0..n) end:
for n from 0 to 8 do A287696_row(n) od;
A287696_poly := proc(n) local k, x; hypergeom([],[1,1],z); series(%^x, z=0, n+1):
unapply(n!^3*coeff(%, z, n), x); end:
for n from 0 to 7 do A287696_poly(n) od;

T[n_, k_] := (n!)^3 SeriesCoefficient[HypergeometricPFQ[{}, {1, 1}, z]^x, {x, 0, k}, {z, 0, n}];
Table[T[n, k], {n, 0, 7}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 13 2017 *)

Sum_{k=0..n} T(n,k) = A000012(n).

Sum_{k=0..n} abs(T(n,k)) = A212856(n) = A212855_row(3).

A334394 Triangle read by rows: T(n,k) is the number of ordered triples of n-permutations with exactly k common descents, n>=0, 0<=k<=max(0,n-1).

Original entry on oeis.org

1, 1, 7, 1, 163, 52, 1, 8983, 4499, 341, 1, 966751, 660746, 98256, 2246, 1, 179781181, 155729277, 35677082, 2045282, 15177, 1, 53090086057, 55690144728, 17446464519, 1754605504, 42658239, 104952, 1, 23402291822743, 28825420903351, 11518335730323, 1717307782339, 84058424389, 905365701, 739153, 1

Offset: 0

Geoffrey Critzer, Apr 26 2020

An ordered triple of n-permutations ( (a_1,a_2,...,a_n),(b_1,b_2,...,b_n),(c_1,c_2,...,c_n) ) has a common descent at position i, 1<=i<=n-1, if a_i > a_i+1, b_i > b_i+1 and c_i > c_i+1.

			Triangle begins:
       1;
       1;
       7,      1;
     163,     52,     1;
    8983,   4499,   341,   1;
  966751, 660746, 98256, 2246, 1;
  ...

R. P. Stanley, Enumerative Combinatorics, Volume I, Second Edition, example 3.18.3e, page 366.

Alois P. Heinz, Rows n = 0..30, flattened
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; page 209.

Cf. A192721, A008292, A212856 (column k=0), A000442 (row sums).

T:= (n, k)-> n!^3*coeff(series(coeff(series((y-1)/(y-add((x*
    (y-1))^j/j!^3, j=0..n)), y, k+1), y, k), x, n+1), x, n):
seq(seq(T(n,k), k=0..max(0, n-1)), n=0..10);  # Alois P. Heinz, Apr 28 2020

nn = 6; e3[x_] := Sum[x^n/n!^3, {n, 0, nn}];Drop[Map[Select[#, # > 0 &] &,
   Table[n!^3, {n, 0, nn}] CoefficientList[Series[(y - 1)/(y - e3[x (y - 1)]), {x, 0, nn}], {x, y}]], 1] // Grid

Sum_{n>=0} Sum_{k>=0} T(n,k)*y^k*x^n/n!^3 = (y-1)/(y-f(x*(y-1))) where f(z) = Sum_{n>=0} z^n/n!^3.

A337676 a(0) = 1; a(n) = -(n!)^3 * Sum_{k=0..n-1} a(k) / (k! * (n-k))^3.

Original entry on oeis.org

1, -1, 7, -170, 9664, -1080824, 207876968, -63709383408, 29068641741312, -18924533538121728, 16870738405288439808, -20048074289311310521344, 30889296893650981899202560, -60580966918820974514054369280, 148238116513927185591120536580096

Offset: 0

Ilya Gutkovskiy, Sep 15 2020

sign

Cf. A006252, A074706, A212856, A336259, A337677, A337678.

a[0] = 1; a[n_] := a[n] = -(n!)^3 Sum[a[k]/(k! (n - k))^3, {k, 0, n - 1}]; Table[a[n], {n, 0, 14}]
nmax = 14; CoefficientList[Series[1/(1 + PolyLog[3, x]), {x, 0, nmax}], x] Range[0, nmax]!^3

a(n)={n!^3*polcoef(1/(1 + polylog(3,x + O(x*x^n))), n)} \\ Andrew Howroyd, Sep 15 2020

Sum_{n>=0} a(n) * x^n / (n!)^3 = 1 / (1 + polylog(3,x)).

A287697 Triangle read by rows, (Sum_{k=0..n} T[n,k]*x^k) / (1-x)^(n+1) are generating functions of the columns of A287698.

Original entry on oeis.org

1, 0, 1, 0, 1, 7, 0, 1, 52, 163, 0, 1, 341, 4499, 8983, 0, 1, 2246, 98256, 660746, 966751, 0, 1, 15177, 2045282, 35677082, 155729277, 179781181, 0, 1, 104952, 42658239, 1754605504, 17446464519, 55690144728, 53090086057

Offset: 0

Peter Luschny, May 30 2017

			Triangle starts:
0: [1]
1: [0, 1]
2: [0, 1,      7]
3: [0, 1,     52,      163]
4: [0, 1,    341,     4499,       8983]
5: [0, 1,   2246,    98256,     660746,      966751]
6: [0, 1,  15177,  2045282,   35677082,   155729277,   179781181]
7: [0, 1, 104952, 42658239, 1754605504, 17446464519, 55690144728, 53090086057]
...
Let q4(x) = (x + 341*x^2 + 4499*x^3 + 8983*x^4) / (1-x)^5 then the coefficients of the series expansion of q4 are column 4 of A287698.

Cf. A000442, A212856, A287696, A287698.

A287697_row := n -> Delta(A287696_poly(n), n): # Delta defined in A287315.
for n from 0 to 9 do A287697_row(n) od;
A287697_eulerian := (n,x) -> add(A287697_row(n)[k+1]*x^k,k=0..n)/(1-x)^(n+1):
for n from 0 to 4 do A287697_eulerian(n,x) od;

T(n,n) = A212856(n).

Sum_{k=0..n} T(n,k) = A000442(n).

A216207 Matrix inverse of A181543 (cubes of entries of Pascal's triangle).

Original entry on oeis.org

1, -1, 1, 7, -8, 1, -163, 189, -27, 1, 8983, -10432, 1512, -64, 1, -966751, 1122875, -163000, 7000, -125, 1, 179781181, -208818216, 30317625, -1304000, 23625, -216, 1, -53090086057, 61664945083, -8953081011, 385146125, -6988625, 64827, -343, 1, 23402291822743, -27182124061184, 3946556485312, -169776943616, 3081169000, -28625408, 153664, -512, 1

Offset: 0

R. J. Mathar, Mar 12 2013

Is the leftmost column derived from A212856?

			1;
-1,1;
7,-8,1;
-163,189,-27,1;
8983,-10432,1512,-64,1;
-966751,1122875,-163000,7000,-125,1;
179781181,-208818216,30317625,-1304000,23625,-216,1;

Cf. A055133.

Sum_{j=k..n} A181543(n,j)*T(j,k) = delta(n,k).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A325305 Irregular triangular array, read by rows: T(n,k) is the sum of the products of distinct multinomial coefficients (n_1 + n_2 + n_3 + ...)!/(n_1! * n_2! * n_3! * ...) taken k at a time, where (n_1, n_2, n_3, ...) runs over all integer partitions of n (n >= 0, 0 <= k <= A070289(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212806 Number of n X n matrices in which each row is a permutation of [1..n] and which contain no column rises.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A287696 Triangle read by rows, T(n,k) = (n!)^3 * [x^k] [z^n] hypergeom([], [1, 1], z)^x for n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A334394 Triangle read by rows: T(n,k) is the number of ordered triples of n-permutations with exactly k common descents, n>=0, 0<=k<=max(0,n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A337676 a(0) = 1; a(n) = -(n!)^3 * Sum_{k=0..n-1} a(k) / (k! * (n-k))^3.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

A287697 Triangle read by rows, (Sum_{k=0..n} T[n,k]*x^k) / (1-x)^(n+1) are generating functions of the columns of A287698.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple