A227578 -id:A227578 - cp's OEIS frontend

A060854 Array T(m,n) read by antidiagonals: T(m,n) (m >= 1, n >= 1) = number of ways to arrange the numbers 1,2,...,m*n in an m X n matrix so that each row and each column is increasing.

1, 1, 1, 1, 2, 1, 1, 5, 5, 1, 1, 14, 42, 14, 1, 1, 42, 462, 462, 42, 1, 1, 132, 6006, 24024, 6006, 132, 1, 1, 429, 87516, 1662804, 1662804, 87516, 429, 1, 1, 1430, 1385670, 140229804, 701149020, 140229804, 1385670, 1430, 1, 1, 4862, 23371634, 13672405890, 396499770810, 396499770810, 13672405890, 23371634, 4862, 1

Offset: 1

R. H. Hardin, May 03 2001

Multidimensional Catalan numbers; a special case of the "hook-number formula".
Number of paths from (0,0,...,0) to (n,n,...,n) in m dimensions, all coordinates increasing: if (x_1,x_2,...,x_m) is on the path, then x_1 <= x_2 <= ... <= x_m. Number of ways to label an n by m array with all the values 1..n*m such that each row and column is strictly increasing. Number of rectangular Young Tableaux. Number of linear extensions of the n X m lattice (the divisor lattice of a number having exactly two prime divisors). - Mitch Harris, Dec 27 2005
Given m*n lines in a {(m + 1)(n - 1)}-dimensional space, T(m, n) is the number of {n*(m-1)-1}-dimensional spaces cutting these lines in points (see Fontanari and Castelnuovo). - Stefano Spezia, Jun 19 2022

			Array begins:
  1,   1,     1,         1,            1,                1, ...
  1,   2,     5,        14,           42,              132, ...
  1,   5,    42,       462,         6006,            87516, ...
  1,  14,   462,     24024,      1662804,        140229804, ...
  1,  42,  6006,   1662804,    701149020,     396499770810, ...
  1, 132, 87516, 140229804, 396499770810, 1671643033734960, ...

Guido Castelnuovo, Numero degli spazi che segano più rette in uno spazio ad n dimensioni, Rendiconti della R. Accademia dei Lincei, s. IV, vol. V, 4 agosto 1889. In Guido Castelnuovo, Memorie scelte, Zanichelli, Bologna 1937, pp. 55-64 (in Italian).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 7.23.19(b).

Alois P. Heinz, Antidiagonals n = 1..36
Albrecht Böttcher, Wiener-Hopf Determinants with Rational Symbols, Math. Nachr. 144 (1989), 39-64.
Freddy Cachazo and Nick Early, Minimal Kinematics: An all k and n peek into Trop^+G(k,n), arXiv:2003.07958 [hep-th], 2020.
Freddy Cachazo and Nick Early, Planar Kinematics: Cyclic Fixed Points, Mirror Superpotential, k-Dimensional Catalan Numbers, and Root Polytopes, arXiv:2010.09708 [math.CO], 2020.
Freddy Cachazo and Nick Early, Biadjoint Scalars and Associahedra from Residues of Generalized Amplitudes, arXiv:2204.01743 [hep-th], 2022.
Andrzej Dudek, Jarosław Grytczuk, Jakub Przybyło, and Andrzej Ruciński, Homogeneous substructures in random ordered hyper-matchings, arXiv:2507.20374 [math.CO], 2025. See p. 19.
Nick Early, Planarity in Generalized Scattering Amplitudes: PK Polytope, Generalized Root Systems and Worldsheet Associahedra, arXiv:2106.07142 [math.CO], 2021, see p. 14.
Ömer Eğecioğlu, On Böttcher's mysterious identity, Australasian Journal of Combinatorics, Volume 43 (2009), 307-316.
Paul Drube, Generating Functions for Inverted Semistandard Young Tableaux and Generalized Ballot Numbers, arXiv:1606.04869 [math.CO], 2016.
Claudio Fontanari, Guido Castelnuovo and his heritage: geometry, combinatorics, teaching, arXiv:2206.06709 [math.HO], 2022. See pp. 2-3.
J. S. Frame, G. de B. Robinson and R. M. Thrall, The hook graphs of a symmetric group, Canad. J. Math. 6 (1954), pp. 316-324.
Alexander Garver and Thomas McConville, Chapoton triangles for nonkissing complexes, Algebraic Combinatorics, 3 (2020), pp. 1331-1363.
Katarzyna Górska and Karol A. Penson, Multidimensional Catalan and related numbers as Hausdorff moments, arXiv preprint arXiv:1304.6008 [math.CO], 2013.
Owen John Levens, Joel Brewster Lewis, and Bridget Eileen Tenner, Global patterns in signed permutations, arXiv:2504.13108 [math.CO], 2025. See p. 18.
Dimana Miroslavova Pramatarova, Investigating the Periodicity of Weighted Catalan Numbers and Generalizing Them to Higher Dimensions, MIT Res. Sci. Instit. (2025). See p. 5.
Francisco Santos, Christian Stump, and Volkmar Welker, Noncrossing sets and a Graßmannian associahedron, in FPSAC 2014, Chicago, USA; Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, 2014, 609-620.
Wikipedia, Hook length formula

Rows give A000108 (Catalan numbers), A005789, A005790, A005791, A321975, A321976, A321977, A321978.
Diagonals give A039622, A060855, A060856.
Cf. A227578. - Alois P. Heinz, Jul 18 2013
Cf. A321716.

T:= (m, n)-> (m*n)! * mul(i!/(m+i)!, i=0..n-1):
seq(seq(T(n, 1+d-n), n=1..d), d=1..10);

maxm = 10; t[m_, n_] := Product[k!, {k, 0, n - 1}]*(m*n)! / Product[k!, {k, m, m + n - 1}]; Flatten[ Table[t[m + 1 - n, n], {m, 1, maxm}, {n, 1, m}]] (* Jean-François Alcover, Sep 21 2011 *)
Table[ BarnesG[n+1]*(n*(m-n+1))!*BarnesG[m-n+2] / BarnesG[m+2], {m, 1, 10}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jan 30 2016 *)

{A(i, j) = if( i<0 || j<0, 0, (i*j)! / prod(k=1, i+j-1, k^vecmin([k, i, j, i+j-k])))}; /* Michael Somos, Jan 28 2004 */

T(m, n) = 0!*1!*..*(n-1)! *(m*n)! / ( m!*(m+1)!*..*(m+n-1)! ).

T(m, n) = A000142(m*n)*A000178(m-1)*A000178(n-1)/A000178(m+n-1) = A000142(A004247(m, n)) * A007318(m+n, n)/A009963(m+n, n). - Henry Bottomley, May 22 2002

More terms from Frank Ellermann, May 21 2001

A262809 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 13, 13, 1, 1, 1, 75, 409, 63, 1, 1, 1, 541, 23917, 16081, 321, 1, 1, 1, 4683, 2244361, 10681263, 699121, 1683, 1, 1, 1, 47293, 308682013, 14638956721, 5552351121, 32193253, 8989, 1, 1, 1, 545835, 58514835289, 35941784497263, 117029959485121, 3147728203035, 1538743249, 48639, 1, 1

Offset: 0

Alois P. Heinz, Oct 02 2015

Also, A(n,k) is the number of alignments for k sequences of length n each (Slowinski 1998).
Row r > 0 is asymptotic to sqrt(r*Pi) * (r^(r-1)/(r-1)!)^n * n^(r*n+1/2) / (2^(r/2) * exp(r*n) * (log(2))^(r*n+1)), or equivalently to sqrt(r) * (r^(r-1)/(r-1)!)^n * (n!)^r / (2^r * (Pi*n)^((r-1)/2) * (log(2))^(r*n+1)). - Vaclav Kotesovec, Mar 23 2016
From Vaclav Kotesovec, Mar 23 2016: (Start)
Column k > 0 is asymptotic to sqrt(c(k)) * d(k)^n / (Pi*n)^((k-1)/2), where c(k) and d(k) are roots of polynomial equations of degree k, independent on n.
---------------------------------------------------
k               d(k)
---------------------------------------------------
2              5.8284271247461900976033774484193...
3             56.9476283720414911685286267804411...
4            780.2794068067951456595241495989622...
5          13755.2719024115081712083954421541320...
6         296476.9162644200814909862281498491264...
7        7553550.6198338218721069097516499501996...
8      222082591.6017202421029000117685530884167...
9     7400694480.0494436216324852038000444393262...
10  275651917450.6709238286995776605620357737005...
---------------------------------------------------
d(k) is a root of polynomial:
---------------------------------------------------
k=2, 1 - 6*d + d^2
k=3, -1 + 3*d - 57*d^2 + d^3
k=4, 1 - 12*d - 218*d^2 - 780*d^3 + d^4
k=5, -1 + 5*d - 1260*d^2 - 3740*d^3 - 13755*d^4 + d^5
k=6, 1 - 18*d - 5397*d^2 - 123696*d^3 + 321303*d^4 - 296478*d^5 + d^6
k=7, -1 + 7*d - 24031*d^2 - 374521*d^3 - 24850385*d^4 + 17978709*d^5 - 7553553*d^6 + d^7
k=8, 1 - 24*d - 102692*d^2 - 9298344*d^3 + 536208070*d^4 - 7106080680*d^5 - 1688209700*d^6 - 222082584*d^7 + d^8
(End)
d(k) = (2^(1/k) - 1)^(-k). - David Bevan, Apr 07 2022
d(k) is asymptotic to (k/log(2))^k/sqrt(2). - David Bevan, Apr 07 2022
A(n,k) is the number of binary matrices with k columns and any number of nonzero rows with n ones in every column. - Andrew Howroyd, Jan 23 2020

			A(2,2) = 13: [(2,2),(1,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,0)], [(2,2),(1,2),(1,1),(1,0),(0,0)], [(2,2),(2,1),(1,1),(0,1),(0,0)], [(2,2),(2,1),(1,1),(0,0)], [(2,2),(2,1),(1,1),(1,0),(0,0)], [(2,2),(2,1),(2,0),(0,1),(0,0)], [(2,2),(2,1),(1,0),(0,0)], [(2,2),(1,1),(0,1),(0,0)], [(2,2),(1,1),(0,0)], [(2,2),(1,1),(1,0),(0,0)].
Square array A(n,k) begins:
  1, 1,    1,        1,             1,                   1, ...
  1, 1,    3,       13,            75,                 541, ...
  1, 1,   13,      409,         23917,             2244361, ...
  1, 1,   63,    16081,      10681263,         14638956721, ...
  1, 1,  321,   699121,    5552351121,     117029959485121, ...
  1, 1, 1683, 32193253, 3147728203035, 1050740615666453461, ...

Alois P. Heinz, Antidiagonals n = 0..48, flattened
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Columns: A000012 (k=0 and k=1), A001850 (k=2), A126086 (k=3), A263064 (k=4), A263065 (k=5), A263066 (k=6), A263067 (k=7), A263068 (k=8), A263069 (k=9), A263070 (k=10).
Rows: A000012 (n=0), A000670 (n=1), A055203 (n=2), A062208 (n=3), A062205 (n=4), A263061 (n=5), A263062 (n=6), A062204 (n=7), A263063 (n=8), A263071 (n=9), A263072 (n=10).
Main diagonal: A262810.
Cf. A210472, A225094, A227578, A227655, A229142, A229345, A263159, A316674.
Cf. A188392, A330942, A331461, A331637.

A:= (n, k)-> add(add((-1)^i*binomial(j, i)*
     binomial(j-i, n)^k, i=0..j), j=0..k*n):
seq(seq(A(n, d-n), n=0..d), d=0..10);

A[, 0] =  1; A[n, k_] := Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, n]^k, {i, 0, j}], {j, 0, k*n}];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jul 22 2016, after Alois P. Heinz *)

T(n,k) = {my(m=n*k); sum(j=0, m, binomial(j,n)^k*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))} \\ Andrew Howroyd, Jan 23 2020

A(n,k) = Sum_{j=0..k*n} Sum_{i=0..j} (-1)^i*C(j,i)*C(j-i,n)^k.
A(n,k) = Sum_{i >= 0} binomial(i,n)^k/2^(i+1). - Peter Bala, Jan 30 2018
A(n,k) = Sum_{j=0..n*k} binomial(j,n)^k * Sum_{i=j..n*k} (-1)^(i-j) * binomial(i,j). - Andrew Howroyd, Jan 23 2020

A181197 Number of 3 X n matrices containing a permutation of 1..3*n in increasing order rowwise, columnwise and (downwards) antidiagonally.

Original entry on oeis.org

1, 1, 4, 29, 290, 3532, 49100, 750325, 12310294, 213446666, 3868253164, 72686739116, 1407643591804, 27964937748724, 567853691242796, 11751537336221989, 247263499985110046, 5279409371079693454, 114199628255736623996, 2499214354674134770354

Offset: 1

R. H. Hardin, Oct 10 2010

nonn

Row 3 of A181196.
Equivalently, the number of "truncated shifted standard Young tableaux" of shape ; in other words, if we shift the middle row to the right by one unit and the bottom row to the right by two units, we require that the resulting diagram be increasing as we read down or to the right.
To count these tableaux, observe that if we put the entry 2n + 2 + k in the last position of the second row, the bottom row must end with the entries 2n + 3 + k, ..., 3n. The remaining figure can be filled in arbitrarily; it is a shifted Young diagram of shape . Now apply the hook-length formula for shifted Young tableaux. (This argument is due to Greta Panova.)
a(n) is also the number of maximum packings of pattern
[5 6]
[3 4]
[1 2] in column-strict arrays of size 3 X n+1. - Ran Pan, Apr 13 2015
a(n) is also the number of standard Young tableaux of shape (n,n,n) (French notation) such that for any element T(i,j) in the tableau T, its upper element T(i+1,j) is larger than its right element T(i,j+1). - Ran Pan, Apr 13 2015

			All four 3 X 3 examples:
1..2..3....1..2..3....1..2..4....1..2..4
4..5..6....4..5..7....3..5..6....3..5..7
7..8..9....6..8..9....7..8..9....6..8..9

Alois P. Heinz, Table of n, a(n) for n = 1..220
Joerg Arndt, The a(4)=29 truncated shifted standard Young tableaux of shape [4,4,4].
J. B. Lewis, Pattern Avoidance for Alternating Permutations and Reading Words of Tableaux, Ph. D. Dissertation, Department of Mathematics, MIT, 2012. - From _N. J. A. Sloane_, Oct 12 2012
Ran Pan, Problem 0, Project P.
Ping Sun, Enumeration of standard Young tableaux of shifted strips with constant width, arXiv:1506.07256 [math.CO], 24 Jun 2015.

Row n=3 of A227578. - Alois P. Heinz, Jul 17 2013

a:= n-> `if`(n<2, 1, add(((2*n+k-1)!*(n-k)*(n-k-1)) /
         (n!*(n-1)!*k!*(2*n-1)*(n+k)*(n+k-1)), k=0..n-2)):
seq(a(n), n=1..30);  # Alois P. Heinz, Jul 01 2012

Flatten[{1,Table[Sum[((2*n+k-1)!*(n-k)*(n-k-1))/(n!*(n-1)!*k!*(2*n-1)*(n+k)*(n+k-1)),{k,0,n-2}],{n,2,20}]}] (* Vaclav Kotesovec, Jul 21 2013 *)

a(n) = Sum_{k=0..n-2} ((2n+k-1)!*(n-k)*(n-k-1)) / (n!*(n-1)!*k!*(2n-1) * (n+k)*(n+k-1)) for n>=2, a(1) = 1.
Recurrence: (2*n-1)*(7*n-13)*n^2*a(n) = 2*(182*n^4 - 1185*n^3 + 2722*n^2 - 2625*n + 900)*a(n-1) + 3*(2*n-5)*(3*n-5)*(3*n-4)*(7*n-6)*a(n-2). - Vaclav Kotesovec, Jul 21 2013
a(n) ~ 3^(3*n+1/2)/(64*Pi*n^4). - Vaclav Kotesovec, Jul 21 2013

Formula and comments from Joel B. Lewis, Jul 25 2011

A059231 Number of different lattice paths running from (0,0) to (n,0) using steps from S = {(k,k) or (k,-k): k positive integer} that never go below the x-axis.

Original entry on oeis.org

1, 1, 5, 29, 185, 1257, 8925, 65445, 491825, 3768209, 29324405, 231153133, 1841801065, 14810069497, 120029657805, 979470140661, 8040831465825, 66361595715105, 550284185213925, 4582462506008253, 38306388126997785, 321327658068506121, 2703925940081270205

Offset: 0

Wenjin Woan, Jan 20 2001

If y = x*A(x) then 4*y^2 - (1 + 3*x)*y + x = 0 and x = y*(1 - 4*y) / (1 - 3*y). - Michael Somos, Sep 28 2003
a(n) = A059450(n, n). - Michael Somos, Mar 06 2004
The Hankel transform of this sequence is 4^binomial(n+1,2). - Philippe Deléham, Oct 29 2007
a(n) is the number of Schroder paths of semilength n in which there are no (2,0)-steps at level 0 and at a higher level they come in 3 colors. Example: a(2)=5 because we have UDUD, UUDD, UBD, UGD, and URD, where U=(1,1), D=(1,-1), while B, G, and R are, respectively, blue, green, and red (2,0)-steps. - Emeric Deutsch, May 02 2011
Shifts left when INVERT transform applied four times. - Benedict W. J. Irwin, Feb 02 2016

			a(3) = 29 since the top row of Q^2 = (5, 8, 16, 0, 0, 0, ...), and 5 + 8 + 16 = 29.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry and Aoife Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.8.
Zhi Chen and Hao Pan, Identities involving weighted Catalan, Schroder and Motzkin paths, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=1, b=4.
Curtis Coker, Enumerating a class of lattice paths, Discrete Math., 271 (2003), 13-28 (the sequence d_n).
Curtis Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Joseph P. S. Kung and Anna de Mier, Catalan lattice paths with rook, bishop and spider steps, J. Comb. Theor., Series A (2013) Vol. 120, Issue 2, 379-389.
Gregory J. Morrow, Laws relating runs and steps in gambler’s ruin, Stochastic Proc. Appl. (2024) Vol. 125, Issue 5, 2010-2025.
Gregory Morrow, Some probability distributions and integer sequences related to rook paths, Univ. Colorado Springs (2024). See pp. 1, 4, 15, 22. DOI
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seqs. Vol. 9 (2006), #06.1.1.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.
Wen-jin Woan, Diagonal lattice paths, Congr. Numer. 151 (2001) 173-178.

Cf. A000108, A001003, A007564, A127846.
Row sums of A086873.
Column k=2 of A227578. - Alois P. Heinz, Jul 17 2013

gf := (1+3*x-sqrt(9*x^2-10*x+1))/(8*x): s := series(gf, x, 100): for i from 0 to 50 do printf(`%d,`,coeff(s, x, i)) od:
A059231_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := a[w-1]+4*add(a[j]*a[w-j-1],j=1..w-1) od;
convert(a, list) end: A059231_list(20); # Peter Luschny, May 19 2011

Join[{1},Table[-I 3^n/2LegendreP[n,-1,5/3],{n,40}]] (* Harvey P. Dale, Jun 09 2011 *)
Table[Hypergeometric2F1[-n, 1 - n, 2, 4], {n, 0, 22}] (* Arkadiusz Wesolowski, Aug 13 2012 *)

{a(n) = if( n<0, 0, polcoeff( (1 + 3*x - sqrt(1 - 10*x + 9*x^2 + x^2 * O(x^n))) / (8*x), n))}; /* Michael Somos, Sep 28 2003 */

{a(n) = if( n<0, 0, n++; polcoeff( serreverse( x * (1 - 4*x) / (1 - 3*x) + x * O(x^n)), n))}; /* Michael Somos, Sep 28 2003 */

# Algorithm of L. Seidel (1877)
def A059231_list(n) :
    D = [0]*(n+2); D[1] = 1
    R = []; b = False; h = 1
    for i in range(2*n) :
        if b :
            for k in range(1, h, 1) : D[k] += 2*D[k+1]
        else :
            for k in range(h, 0, -1) : D[k] += 2*D[k-1]
            h += 1
        b = not b
        if b : R.append(D[1])
    return R
A059231_list(23)  # Peter Luschny, Oct 19 2012

a(n) = Sum_{k=0..n} 4^k*N(n, k) where N(n, k) = (1/n)*binomial(n, k)*binomial(n, k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 10 2003
a(n) = 3^n/2*LegendreP(n, -1, 5/3). - Vladeta Jovovic, Sep 17 2003
G.f.: (1 + 3*x - sqrt(1 - 10*x + 9*x^2)) / (8*x) = 2 / (1 + 3*x + sqrt(1 - 10*x + 9*x^2)). - Michael Somos, Sep 28 2003
a(n) = Sum_{k=0..n} A088617(n, k)*4^k*(-3)^(n-k). - Philippe Deléham, Jan 21 2004
With offset 1: a(1)=1, a(n) = -3*a(n-1) + 4*Sum_{i=1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004
D-finite with recurrence a(n) = (5(2n-1)a(n-1) - 9(n-2)a(n-2))/(n+1) for n>=2; a(0)=a(1)=1. - Emeric Deutsch, Mar 20 2004
Moment representation: a(n)=(1/(8*Pi))*Int(x^n*sqrt(-x^2+10x-9)/x,x,1,9)+(3/4)*0^n. - Paul Barry, Sep 30 2009
a(n) = upper left term in M^n, M = the production matrix:
  1, 1
  4, 4, 4
  1, 1, 1, 1
  4, 4, 4, 4, 4
  1, 1, 1, 1, 1, 1
  ... - Gary W. Adamson, Jul 08 2011
a(n) is the sum of top row terms of Q^(n-1), where Q = the following infinite square production matrix:
  1, 4, 0, 0, 0, ...
  1, 1, 4, 0, 0, ...
  1, 1, 1, 4, 0, ...
  1, 1, 1, 1, 4, ...
  ... - Gary W. Adamson, Aug 23 2011
G.f.: (1+3*x-sqrt(9*x^2-10*x+1))/(8*x)=(1+3*x -G(0))/(4*x) ; G(k)= 1+x*3-x*4/G(k+1); (continued fraction, 1-step ). - Sergei N. Gladkovskii, Jan 05 2012
a(n) ~ sqrt(2)*3^(2*n+1)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 11 2012
a(n) = A127846(n) for n>0. - Philippe Deléham, Apr 03 2013
0 = a(n)*(+81*a(n+1) - 225*a(n+2) + 36*a(n+3)) + a(n+1)*(+45*a(n+1) + 82*a(n+2) - 25*a(n+3)) + a(n+2)*(+5*a(n+2) + a(n+3)) for all n>=0. - Michael Somos, Aug 25 2014
G.f.: 1/(1 - x/(1 - 4*x/(1 - x/(1 - 4*x/(1 - x/(1 - ...)))))), a continued fraction. - Ilya Gutkovskiy, Aug 10 2017

A263159 Number A(n,k) of lattice paths starting at {n}^k and ending when k or any component equals 0, using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 13, 1, 1, 1, 15, 157, 63, 1, 1, 1, 31, 2101, 5419, 321, 1, 1, 1, 63, 32461, 717795, 220561, 1683, 1, 1, 1, 127, 580693, 142090291, 328504401, 9763807, 8989, 1, 1, 1, 255, 11917837, 39991899123, 944362553521, 172924236255, 454635973, 48639, 1, 1

Offset: 0

Alois P. Heinz, Oct 11 2015

			Square array A(n,k) begins:
  1, 1,    1,       1,            1,                1, ...
  1, 1,    3,       7,           15,               31, ...
  1, 1,   13,     157,         2101,            32461, ...
  1, 1,   63,    5419,       717795,        142090291, ...
  1, 1,  321,  220561,    328504401,     944362553521, ...
  1, 1, 1683, 9763807, 172924236255, 7622403922836151, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened

Columns k=0+1, 2-10 give: A000012, A001850, A115866, A263162, A263163, A263164, A263165, A263166, A263167, A263168.
Rows n=0-1 give: A000012, A255047.
Main diagonal gives A263160.
Cf. A210472, A225094, A227578, A227655, A229142, A229345, A262809.

s:= proc(n) option remember; `if`(n=0, {[]},
      map(x-> [[x[], 0], [x[], 1]][], s(n-1)))
    end:
b:= proc(l) option remember; `if`(l=[] or l[1]=0, 1,
       add((p-> `if`(p[1]<0, 0, `if`(p[1]=0, 1, b(p)))
       )(sort(l-x)), x=s(nops(l)) minus {[0$nops(l)]}))
    end:
A:= (n, k)-> b([n$k]):
seq(seq(A(n,d-n), n=0..d), d=0..10);

g[k_] := Table[Reverse[IntegerDigits[n, 2]][[;;k]], {n, 2^k+1, 2^(k+1)-1}];
b[l_] := b[l] = If[l[[1]] == 0, 1, Sum[b[Sort[l - h]], {h, g[k]}]];
a[n_, k_] := If[n == 0 || k == 0 || k == 1, 1, b[Table[n, {k}]]];
Table[a[n-k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Apr 25 2020, after Alois P. Heinz in A115866 *)

A229142 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one component or all components by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 13, 1, 1, 1, 25, 115, 63, 1, 1, 1, 121, 2641, 2371, 321, 1, 1, 1, 721, 114121, 392641, 54091, 1683, 1, 1, 1, 5041, 7489441, 169417921, 67982041, 1307377, 8989, 1, 1, 1, 40321, 681120721, 137322405361, 308238414121, 12838867105, 32803219, 48639, 1, 1

Offset: 0

Alois P. Heinz, Sep 23 2013

Column k is the diagonal of the rational function 1 / (1 - Sum_{j=1..k} x_j - Product_{j=1..k} x_j) for k>1. - Seiichi Manyama, Jul 10 2020

			A(1,3) = 3*2+1 = 7:
          (0,1,1)-(0,0,1)
         /       X       \
  (1,1,1)-(1,0,1) (0,1,0)-(0,0,0)
       \ \       X       / /
        \ (1,1,0)-(1,0,0) /
         `---------------´
Square array A(n,k) begins:
  1, 1,    1,       1,           1,               1, ...
  1, 1,    3,       7,          25,             121, ...
  1, 1,   13,     115,        2641,          114121, ...
  1, 1,   63,    2371,      392641,       169417921, ...
  1, 1,  321,   54091,    67982041,    308238414121, ...
  1, 1, 1683, 1307377, 12838867105, 629799991355641, ...

Alois P. Heinz, Antidiagonals n = 0..44, flattened

Columns k=0+1, 2-10 give: A000012, A001850, A081798, A082488, A082489, A229049, A229674, A229675, A229676, A229677.
Rows n=0-1 give: A000012, A038507 (for k>1).
Main diagonal gives: A229267.
Cf. A060854, A227578, A227655, A225094, A210472, A262809, A263159.

with(combinat):
A:= (n,k)-> `if`(k<2, 1, add(multinomial(n+(k-1)*j, n-j, j$k), j=0..n)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

a[, 0] = a[, 1] = 1; a[n_, k_] := Sum[Product[Binomial[n+j*m, m], {j, 0, k-1}], {m, 0, n}]; Table[a[n-k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Dec 11 2013 *)

A(n,k) = Sum_{j=0..n} multinomial(n+(k-1)*j; n-j, {j}^k) for k>1, A(n,0) = A(n,1) = 1.

G.f. of column k: Sum_{j>=0} (k*j)!/j!^k * x^j / (1-x)^(k*j+1). for k>1. - Seiichi Manyama, Jul 10 2020

A181196 T(n,k) = number of n X k matrices containing a permutation of 1..n*k in increasing order rowwise, columnwise, diagonally and (downwards) antidiagonally.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 4, 1, 1, 1, 14, 29, 8, 1, 1, 1, 42, 290, 169, 16, 1, 1, 1, 132, 3532, 6392, 985, 32, 1, 1, 1, 429, 49100, 352184, 141696, 5741, 64, 1, 1, 1, 1430, 750325, 25097600, 36372976, 3142704, 33461, 128, 1, 1, 1, 4862, 12310294

Offset: 1

R. H. Hardin, Oct 10 2010

Table starts:
.1.1...1......1..........1..............1...................1
.1.1...2......5.........14.............42.................132
.1.1...4.....29........290...........3532...............49100
.1.1...8....169.......6392.........352184............25097600
.1.1..16....985.....141696.......36372976.........14083834704
.1.1..32...5741....3142704.....3777546912.......8092149471168
.1.1..64..33461...69705920...392658046912....4673805856338368
.1.1.128.195025.1546100352.40820345224064.2702482348019033600

			All solutions for 3 X 4:
..1..2..3..4....1..2..3..4....1..2..3..4....1..2..3..4....1..2..3..4
..5..6..7..8....5..6..7..9....5..6..7.10....5..6..8..9....5..6..8.10
..9.10.11.12....8.10.11.12....8..9.11.12....7.10.11.12....7..9.11.12
...
..1..2..3..6....1..2..3..6....1..2..3..6....1..2..3..6....1..2..3..6
..4..5..7..8....4..5..7..9....4..5..7.10....4..5..8..9....4..5..8.10
..9.10.11.12....8.10.11.12....8..9.11.12....7.10.11.12....7..9.11.12
...
..1..2..4..6....1..2..4..6....1..2..4..6....1..2..4..6....1..2..4..6
..3..5..7..8....3..5..7..9....3..5..7.10....3..5..8..9....3..5..8.10
..9.10.11.12....8.10.11.12....8..9.11.12....7.10.11.12....7..9.11.12
...
..1..2..3..5....1..2..3..5....1..2..3..5....1..2..3..5....1..2..3..5
..4..6..7..8....4..6..7..9....4..6..7.10....4..6..8..9....4..6..8.10
..9.10.11.12....8.10.11.12....8..9.11.12....7.10.11.12....7..9.11.12
...
..1..2..4..5....1..2..4..5....1..2..4..5....1..2..4..5....1..2..4..5
..3..6..7..8....3..6..7..9....3..6..7.10....3..6..8..9....3..6..8.10
..9.10.11.12....8.10.11.12....8..9.11.12....7.10.11.12....7..9.11.12
...
..1..2..3..7....1..2..3..7....1..2..4..7....1..2..4..7
..4..5..8..9....4..5..8.10....3..5..8..9....3..5..8.10
..6.10.11.12....6..9.11.12....6.10.11.12....6..9.11.12

R. H. Hardin and Alois P. Heinz, Antidiagonals n = 1..30, flattened
Brian T. Chan, Periodic P-Partitions, arXiv:1803.05594 [math.CO], 2018-2020.
Ping Sun, Enumeration of standard Young tableaux of shifted strips with constant width, El. J. Comb., 24 (2017), #P2.41; arXiv:1506.07256 [math.CO], 2015.
Antonio Vera López, Luis Martínez, Antonio Vera Pérez, Beatriz Vera Pérez and Olga Basova, Combinatorics related to Higman's conjecture I: Parallelogramic digraphs and dispositions, Linear Algebra and its Applications, Volume 530, 1 October 2017, p. 414-444. See Table 1.

Rows n=1-5 give: A000012, A000108, A181197, A181198, A181199.
Columns 1+2, 3-8 give: A000012, A011782, A001653, A181192, A181193, A181194, A181195.
A227578 is a similar but different array.

b:= proc(l) option remember; local n; n:= nops(l);
      `if`({l[]}={0}, 1, add(`if`((i=1 or l[i-1]<=l[i]) and l[i]>
      `if`(i=n, 0, l[i+1]), b(subsop(i=l[i]-1, l)), 0), i=1..n))
    end:
T:= (n,k)-> b([n$k]):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);  # Alois P. Heinz, Jul 24 2012

b[l_List] := b[l] = With[{n = Length[l]}, If[Union[l] == {0}, 1, Sum[If[(i == 1 || l[[i-1]] <= l[[i]]) && l[[i]] > If[i == n, 0, l[[i+1]]], b[ReplacePart[l, i -> l[[i]]-1]], 0], {i, 1, n}]]]; T[n_, k_] := b[Array[n&, k]]; Table[Table[T[n, 1+d-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Mar 06 2015, after Alois P. Heinz *)

Empirical column 1: a(n) = a(n-1).
Empirical column 2: a(n) = a(n-1).
Empirical column 3: a(n) = 2*a(n-1).
Empirical column 4: a(n) = 6*a(n-1)-a(n-2).
Empirical column 5: a(n) = 24*a(n-1)-40*a(n-2)-8*a(n-3).
Empirical column 6: a(n) = 120*a(n-1)-1672*a(n-2)+544*a(n-3)-6672*a(n-4) +256*a(n-5).
Empirical column 7: a(n) = 720*a(n-1) -84448*a(n-2) +1503360*a(n-3) -17912224*a(n-4) -318223104*a(n-5) +564996096*a(n-6) +270471168*a(n-7) -11373824*a(n-8) +65536*a(n-9).

A229345 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one component or all components by the same positive integer; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 7, 22, 4, 1, 1, 25, 248, 188, 8, 1, 1, 121, 6506, 11380, 1712, 16, 1, 1, 721, 292442, 2359348, 577124, 16098, 32, 1, 1, 5041, 19450082, 1088626684, 991365512, 30970588, 154352, 64, 1

Offset: 0

Alois P. Heinz, Sep 24 2013

			A(2,2) = 22: [(2,2),(1,1),(0,0)], [(2,2),(1,1),(0,1),(0,0)], [(2,2),(1,1),(1,0),(0,0)], [(2,2),(0,0)], [(2,2),(1,2),(0,1),(0,0)], [(2,2),(1,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(0,2),(0,0)], [(2,2),(1,2),(1,1),(0,0)], [(2,2),(1,2),(1,1),(0,1),(0,0)], [(2,2),(1,2),(1,1),(1,0),(0,0)], [(2,2),(1,2),(1,0),(0,0)], [(2,2),(0,2),(0,1),(0,0)], [(2,2),(0,2),(0,0)], [(2,2),(2,1),(1,0),(0,0)], [(2,2),(2,1),(1,1),(0,0)], [(2,2),(2,1),(1,1),(0,1),(0,0)], [(2,2),(2,1),(1,1),(1,0),(0,0)], [(2,2),(2,1),(0,1),(0,0)], [(2,2),(2,1),(2,0),(1,0),(0,0)], [(2,2),(2,1),(2,0),(0,0)], [(2,2),(2,0),(1,0),(0,0)], [(2,2),(2,0),(0,0)].
Square array A(n,k) begins:
  1,  1,     1,        1,            1,                 1, ...
  1,  1,     3,        7,           25,               121, ...
  1,  2,    22,      248,         6506,            292442, ...
  1,  4,   188,    11380,      2359348,        1088626684, ...
  1,  8,  1712,   577124,    991365512,     4943064622568, ...
  1, 16, 16098, 30970588, 453530591824, 25162900228200976, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened

Columns k=0-3 give: A000012, A011782, A132595(n+1), A229482.
Rows n=0-2 give: A000012, A038507 (for k>1), A229465.
Main diagonal gives: A229346.
Cf. A060854, A227578, A227655, A225094, A210472, A229142, A262809, A263159.

b:= proc(l) option remember; local m; m:= nops(l);
      `if`(m=0 or l[m]=0, 1,
      `if`(m>1, add(b(l-[j$m]), j=1..l[1]), 0)+
      add(add(b(sort(subsop(i=l[i]-j, l))), j=1..l[i]), i=1..m))
    end:
A:= (n, k)-> b([n$k]):
seq(seq(A(n, d-n), n=0..d), d=0..10);  # Alois P. Heinz, Sep 24 2013

b[l_] := b[l] = With[{m = Length[l]}, If[m == 0 || l[[m]] == 0, 1, If[m > 1, Sum[b[l - Array[j&, m]], {j, 1, l[[1]]}],  0] + Sum[Sum[b[Sort[ReplacePart[l, i -> l[[i]] - j]]], {j, 1, l[[i]]}], {i, 1, m}]]]; a[n_, k_] := b[Array[n&, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

A227579 Number of lattice paths from {n}^n to {0}^n using steps that decrement one component such that for each point (p_1,p_2,...,p_n) we have p_1<=p_2<=...<=p_n.

Original entry on oeis.org

1, 1, 5, 290, 456033, 36470203156, 237791136700913751, 184570140930218389159747070, 23408169635197679203800470649923362577, 637028433009539403532335279417025047587902906655768, 4725612998324981086891784010767387049970117446517002416810380479702

Offset: 0

Alois P. Heinz, Jul 16 2013

			a(2) = 5: [(2,2),(0,2),(0,0)], [(2,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(0,2),(0,0)], [(2,2),(1,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,1),(0,0)].

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..14 (terms 0..12 from Alois P. Heinz)

Main diagonal of A227578.

b:= proc(l) option remember; `if`(l[-1]=0, 1, add(add(b(subsop(
      i=j, l)), j=`if`(i=1, 0, l[i-1])..l[i]-1), i=1..nops(l)))
    end:
a:= n-> `if`(n=0, 1, b([n$n])):
seq(a(n), n=0..9);

b[l_] := b[l] = If[l[[-1]] == 0, 1, Sum[Sum[b[ReplacePart[l, i -> j]], {j, If[i == 1, 0, l[[i - 1]]], l[[i]] - 1}], {i, 1, Length[l]}]];
a[n_] := If[n == 0, 1, b[Table[n, {n}]]];
a /@ Range[0, 9] (* Jean-François Alcover, Jan 03 2021, after Alois P. Heinz *)

A227580 Number of lattice paths from {n}^3 to {0}^3 using steps that decrement one component such that for each point (p_1,p_2,p_3) we have p_1<=p_2<=p_3.

Original entry on oeis.org

1, 1, 14, 290, 7680, 238636, 8285506, 312077474, 12509563082, 526701471002, 23076216957520, 1044813920439200, 48630132961189400, 2317337976558074760, 112689430179458971738, 5577655817793682738378, 280392321290875174774106, 14290804691034216155457274

Offset: 0

Alois P. Heinz, Jul 16 2013

nonn

			a(2) = 14: [(2,2,2),(0,2,2),(0,0,2),(0,0,0)], [(2,2,2),(0,2,2),(0,0,2),(0,0,1),(0,0,0)], [(2,2,2),(0,2,2),(0,1,2),(0,0,2),(0,0,0)], [(2,2,2),(0,2,2),(0,1,2),(0,0,2),(0,0,1),(0,0,0)], [(2,2,2),(0,2,2),(0,1,2),(0,1,1),(0,0,1),(0,0,0)], [(2,2,2),(1,2,2),(0,2,2),(0,0,2),(0,0,0)], [(2,2,2),(1,2,2),(0,2,2),(0,0,2),(0,0,1),(0,0,0)], [(2,2,2),(1,2,2),(0,2,2),(0,1,2),(0,0,2),(0,0,0)], [(2,2,2),(1,2,2),(0,2,2),(0,1,2),(0,0,2),(0,0,1),(0,0,0)], [(2,2,2),(1,2,2),(0,2,2),(0,1,2),(0,1,1),(0,0,1),(0,0,0)], [(2,2,2),(1,2,2),(1,1,2),(0,1,2),(0,0,2),(0,0,0)], [(2,2,2),(1,2,2),(1,1,2),(0,1,2),(0,0,2),(0,0,1),(0,0,0)], [(2,2,2),(1,2,2),(1,1,2),(0,1,2),(0,1,1),(0,0,1),(0,0,0)], [(2,2,2),(1,2,2),(1,1,2),(1,1,1),(0,1,1),(0,0,1),(0,0,0)].

Alois P. Heinz, Table of n, a(n) for n = 0..200

Column k=3 of A227578.

a:= proc(n) option remember; `if`(n<3, [1, 1, 14][n+1],
      ((n+1)*(665*n^3-1433*n^2+980*n-204) *a(n-1)
       -(n-2)*(1615*n^3-3218*n^2+1521*n-342) *a(n-2)
       +192*(5*n-1)*(n-3)*(n-2)^2 *a(n-3)) /
       (2*(n+2)*(5*n-6)*(n+1)^2))
    end:
seq(a(n), n=0..30);

b[l_] := b[l] = If[l[[-1]] == 0, 1, Sum[Sum[b[ReplacePart[l, i -> j]], {j, If[i == 1, 0, l[[i-1]]], l[[i]] - 1}], {i, 1, Length[l]}]];
a[n_] := b[Array[n&, 3]];
a /@ Range[0, 30] (* Jean-François Alcover, Dec 20 2020, after Alois P. Heinz in A227578 *)

a(n) ~ 2^(6*n+10)/(sqrt(3)*Pi*(5*n)^4). - Vaclav Kotesovec, Jul 18 2013

cp's OEIS Frontend

A060854 Array T(m,n) read by antidiagonals: T(m,n) (m >= 1, n >= 1) = number of ways to arrange the numbers 1,2,...,m*n in an m X n matrix so that each row and each column is increasing.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A262809 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A181197 Number of 3 X n matrices containing a permutation of 1..3*n in increasing order rowwise, columnwise and (downwards) antidiagonally.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A059231 Number of different lattice paths running from (0,0) to (n,0) using steps from S = {(k,k) or (k,-k): k positive integer} that never go below the x-axis.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

A263159 Number A(n,k) of lattice paths starting at {n}^k and ending when k or any component equals 0, using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A229142 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one component or all components by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A181196 T(n,k) = number of n X k matrices containing a permutation of 1..n*k in increasing order rowwise, columnwise, diagonally and (downwards) antidiagonally.