A108626 -id:A108626 - cp's OEIS frontend

A108625 Square array, read by antidiagonals, where row n equals the crystal ball sequence for the A_n lattice.

1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 13, 19, 7, 1, 1, 21, 55, 37, 9, 1, 1, 31, 131, 147, 61, 11, 1, 1, 43, 271, 471, 309, 91, 13, 1, 1, 57, 505, 1281, 1251, 561, 127, 15, 1, 1, 73, 869, 3067, 4251, 2751, 923, 169, 17, 1, 1, 91, 1405, 6637, 12559, 11253, 5321, 1415, 217, 19, 1

Offset: 0

Paul D. Hanna, Jun 12 2005

Compare to the corresponding array A108553 of crystal ball sequences for D_n lattice.
From Peter Bala, Jul 18 2008: (Start)
Row reverse of A099608.
This array has a remarkable relationship with the constant zeta(2). The row, column and diagonal entries of the array occur in series acceleration formulas for zeta(2).
For the entries in row n we have zeta(2) = 2*(1 - 1/2^2 + 1/3^2 - ... + (-1)^(n+1)/n^2) + (-1)^n*Sum_{k >= 1} 1/(k^2*T(n,k-1)*T(n,k)). For example, n = 4 gives zeta(2) = 2*(1 - 1/4 + 1/9 - 1/16) + 1/(1*21) + 1/(4*21*131) + 1/(9*131*471) + ... . See A142995 for further details.
For the entries in column k we have zeta(2) = (1 + 1/4 + 1/9 + ... + 1/k^2) + 2*Sum_{n >= 1} (-1)^(n+1)/(n^2*T(n-1,k)*T(n,k)). For example, k = 4 gives zeta(2) = (1 + 1/4 + 1/9 + 1/16) + 2*(1/(1*9) - 1/(4*9*61) + 1/(9*61*309) - ... ). See A142999 for further details.
Also, as consequence of Apery's proof of the irrationality of zeta(2), we have a series acceleration formula along the main diagonal of the table: zeta(2) = 5 * Sum_{n >= 1} (-1)^(n+1)/(n^2*T(n,n)*T(n-1,n-1)) = 5*(1/3 - 1/(2^2*3*19) + 1/(3^2*19*147) - ...).
There also appear to be series acceleration results along other diagonals. For example, for the main subdiagonal, calculation supports the result zeta(2) = 2 - Sum_{n >= 1} (-1)^(n+1)*(n^2+(2*n+1)^2)/(n^2*(n+1)^2*T(n,n-1)*T(n+1,n)) = 2 - 10/(2^2*7) + 29/(6^2*7*55) - 58/(12^2*55*471) + ..., while for the main superdiagonal we appear to have zeta(2) = 1 + Sum_{n >= 1} (-1)^(n+1)*((n+1)^2 + (2*n+1)^2)/(n^2*(n+1)^2*T(n-1,n)*T(n,n+1)) = 1 + 13/(2^2*5) - 34/(6^2*5*37) + 65/(12^2*37*309) - ... .
Similar series acceleration results hold for Apery's constant zeta(3) involving the crystal ball sequences for the product lattices A_n x A_n; see A143007 for further details. Similar results also hold between the constant log(2) and the crystal ball sequences of the hypercubic lattices A_1 x...x A_1 and between log(2) and the crystal ball sequences for lattices of type C_n ; see A008288 and A142992 respectively for further details. (End)
This array is the Hilbert transform of triangle A008459 (see A145905 for the definition of the Hilbert transform). - Peter Bala, Oct 28 2008

			Square array begins:
  1,   1,    1,     1,      1,       1,       1, ... A000012;
  1,   3,    5,     7,      9,      11,      13, ... A005408;
  1,   7,   19,    37,     61,      91,     127, ... A003215;
  1,  13,   55,   147,    309,     561,     923, ... A005902;
  1,  21,  131,   471,   1251,    2751,    5321, ... A008384;
  1,  31,  271,  1281,   4251,   11253,   25493, ... A008386;
  1,  43,  505,  3067,  12559,   39733,  104959, ... A008388;
  1,  57,  869,  6637,  33111,  124223,  380731, ... A008390;
  1,  73, 1405, 13237,  79459,  350683, 1240399, ... A008392;
  1,  91, 2161, 24691, 176251,  907753, 3685123, ... A008394;
  1, 111, 3191, 43561, 365751, 2181257, ...      ... A008396;
  ...
As a triangle:
  [0]  1
  [1]  1,  1
  [2]  1,  3,   1
  [3]  1,  7,   5,    1
  [4]  1, 13,  19,    7,    1
  [5]  1, 21,  55,   37,    9,    1
  [6]  1, 31, 131,  147,   61,   11,   1
  [7]  1, 43, 271,  471,  309,   91,  13,   1
  [8]  1, 57, 505, 1281, 1251,  561, 127,  15,  1
  [9]  1, 73, 869, 3067, 4251, 2751, 923, 169, 17, 1
       ...
Inverse binomial transform of rows yield rows of triangle A063007:
  1;
  1,  2;
  1,  6,   6;
  1, 12,  30,  20;
  1, 20,  90, 140,  70;
  1, 30, 210, 560, 630, 252; ...
Product of the g.f. of row n and (1-x)^(n+1) generates the symmetric triangle A008459:
  1;
  1,  1;
  1,  4,   1;
  1,  9,   9,   1;
  1, 16,  36,  16,  1;
  1, 25, 100, 100, 25, 1;
  ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
R. Bacher, P. de la Harpe, and B. Venkov, Séries de croissance et séries d'Ehrhart associées aux réseaux de racines, C. R. Acad. Sci. Paris, 325 (Series 1) (1997), 1137-1142.
Joseph T. Iosue, T. C. Mooney, Adam Ehrenberg, and Alexey V. Gorshkov, Projective toric designs, difference sets, and quantum state designs, arXiv:2311.13479 [quant-ph], 2023. See page 6.
Armin Straub, Multivariate Apéry numbers and supercongruences of rational functions, Algebra & Number Theory, Vol. 8, No. 8 (2014), pp. 1985-2008; arXiv preprint, arXiv:1401.0854 [math.NT], 2014.
A. van der Poorten, A proof that Euler missed ... Apery's proof of the irrationality of zeta(3). An informal report. Math. Intelligencer 1 (1978/79), no 4, 195-203.
Eric Weisstein's World of Mathematics, Apéry number.

Rows include: A003215 (row 2), A005902 (row 3), A008384 (row 4), A008386 (row 5), A008388 (row 6), A008390 (row 7), A008392 (row 8), A008394 (row 9), A008396 (row 10).
Cf. A063007, A099601 (n-th term of A_{2n} lattice), A108553.
Cf. A008459 (h-vectors type B associahedra), A145904, A145905.
Cf. A005258 (main diagonal), A108626 (antidiagonal sums).
Cf. A108628, A208675, A363867, A363868, A363869, A363870, A363871.

T:= func< n,k | (&+[Binomial(n,j)^2*Binomial(n+k-j,k-j): j in [0..k]]) >; // array
A108625:= func< n,k | T(n-k,k) >; // antidiagonals
[A108625(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 05 2023

T := (n,k) -> binomial(n, k)*hypergeom([-k, k - n, k - n], [1, -n], 1):
seq(seq(simplify(T(n,k)),k=0..n),n=0..10); # Peter Luschny, Feb 10 2018

T[n_, k_]:= HypergeometricPFQ[{-n, -k, n+1}, {1, 1}, 1] (* Michael Somos, Jun 03 2012 *)

T(n,k)=sum(i=0,k,binomial(n,i)^2*binomial(n+k-i,k-i))

def T(n,k): return sum(binomial(n,j)^2*binomial(n+k-j, k-j) for j in range(k+1)) # array
def A108625(n,k): return T(n-k, k) # antidiagonals
flatten([[A108625(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Oct 05 2023

T(n, k) = Sum_{i=0..k} C(n, i)^2 * C(n+k-i, k-i).
G.f. for row n: (Sum_{i=0..n} C(n, i)^2 * x^i)/(1-x)^(n+1).
Sum_{k=0..n} T(n-k, k) = A108626(n) (antidiagonal sums).
From Peter Bala, Jul 23 2008 (Start):
O.g.f. row n: 1/(1 - x)*Legendre_P(n,(1 + x)/(1 - x)).
G.f. for square array: 1/sqrt((1 - x)*((1 - t)^2 - x*(1 + t)^2)) = (1 + x + x^2 + x^3 + ...) + (1 + 3*x + 5*x^2 + 7*x^3 + ...)*t + (1 + 7*x + 19*x^2 + 37*x^3 + ...)*t^2 + ... . Cf. A142977.
Main diagonal is A005258.
Recurrence relations:
Row n entries: (k+1)^2*T(n,k+1) = (2*k^2+2*k+n^2+n+1)*T(n,k) - k^2*T(n,k-1), k = 1,2,3,... ;
Column k entries: (n+1)^2*T(n+1,k) = (2*k+1)*(2*n+1)*T(n,k) + n^2*T(n-1,k), n = 1,2,3,... ;
Main diagonal entries: (n+1)^2*T(n+1,n+1) = (11*n^2+11*n+3)*T(n,n) + n^2*T(n-1,n-1), n = 1,2,3,... .
Series acceleration formulas for zeta(2):
Row n: zeta(2) = 2*(1 - 1/2^2 + 1/3^2 - ... + (-1)^(n+1)/n^2) + (-1)^n*Sum_{k >= 1} 1/(k^2*T(n,k-1)*T(n,k));
Column k: zeta(2) = 1 + 1/2^2 + 1/3^2 + ... + 1/k^2 + 2*Sum_{n >= 1} (-1)^(n+1)/(n^2*T(n-1,k)*T(n,k));
Main diagonal: zeta(2) = 5 * Sum_{n >= 1} (-1)^(n+1)/(n^2*T(n-1,n-1)*T(n,n)).
Conjectural result for superdiagonals: zeta(2) = 1 + 1/2^2 + ... + 1/k^2 + Sum_{n >= 1} (-1)^(n+1) * (5*n^2 + 6*k*n + 2*k^2)/(n^2*(n+k)^2*T(n-1,n+k-1)*T(n,n+k)), k = 0,1,2... .
Conjectural result for subdiagonals: zeta(2) = 2*(1 - 1/2^2 + ... + (-1)^(k+1)/k^2) + (-1)^k*Sum_{n >= 1} (-1)^(n+1)*(5*n^2 + 4*k*n + k^2)/(n^2*(n+k)^2*T(n+k-1,n-1)*T(n+k,n)), k = 0,1,2... .
Conjectural congruences: the main superdiagonal numbers S(n) := T(n,n+1) appear to satisfy the supercongruences S(m*p^r - 1) = S(m*p^(r-1) - 1) (mod p^(3*r)) for all primes p >= 5 and all positive integers m and r. If p is prime of the form 4*n + 1 we can write p = a^2 + b^2 with a an odd number. Then calculation suggests the congruence S((p-1)/2) == 2*a^2 (mod p). (End)
From Michael Somos, Jun 03 2012: (Start)
T(n, k) = hypergeom([-n, -k, n + 1], [1, 1], 1).
T(n, n-1) = A208675(n).
T(n+1, n) = A108628(n). (End)
T(n, k) = binomial(n, k)*hypergeom([-k, k - n, k - n], [1, -n], 1). - Peter Luschny, Feb 10 2018
From Peter Bala, Jun 23 2023: (Start)
T(n, k) = Sum_{i = 0..k} (-1)^i * binomial(n, i)*binomial(n+k-i, k-i)^2.
T(n, k) = binomial(n+k, k)^2 * hypergeom([-n, -k, -k], [-n - k, -n - k], 1). (End)
From Peter Bala, Jun 28 2023; (Start)
T(n,k) = the coefficient of (x^n)*(y^k)*(z^n) in the expansion of 1/( (1 - x - y)*(1 - z ) - x*y*z ).
T(n,k) = B(n, k, n) in the notation of Straub, equation 24.
The supercongruences T(n*p^r, k*p^r) == T(n*p^(r-1), k*p^(r-1)) (mod p^(3*r)) hold for all primes p >= 5 and positive integers n and k.
The formula T(n,k) = hypergeom([n+1, -n, -k], [1, 1], 1) allows the table indexing to be extended to negative values of n and k; clearly, we find that T(-n,k) = T(n-1,k) for all n and k. It appears that T(n,-k) = (-1)^n*T(n,k-1) for n >= 0, while T(n,-k) = (-1)^(n+1)*T(n,k-1) for n <= -1 [added Sep 10 2023: these follow from the identities immediately below]. (End)
T(n,k) = Sum_{i = 0..n} (-1)^(n+i) * binomial(n, i)*binomial(n+i, i)*binomial(k+i, i) = (-1)^n * hypergeom([n + 1, -n, k + 1], [1, 1], 1). - Peter Bala, Sep 10 2023
From G. C. Greubel, Oct 05 2023: (Start)
Let t(n,k) = T(n-k, k) (antidiagonals).
t(n, k) = Hypergeometric3F2([k-n, -k, n-k+1], [1,1], 1).
T(n, 2*n) = A363867(n).
T(3*n, n) = A363868(n).
T(2*n, 2*n) = A363869(n).
T(n, 3*n) = A363870(n).
T(2*n, 3*n) = A363871(n). (End)
T(n, k) = Sum_{i = 0..n} binomial(n, i)*binomial(n+i, i)*binomial(k, i). - Peter Bala, Feb 26 2024
Sum_{k = 0..n} (-1)^(n+k)*binomial(n, k)*binomial(n+k, k)*T(n, k) = A005259(n), the Apéry numbers associated with zeta(3). - Peter Bala, Jul 18 2024
From Peter Bala, Sep 21 2024: (Start)
Sum_{k = 0..n} (-1)^(n+k)*binomial(n, k)*T(n, k) = binomial(2*n, n) = A000984(n).
Sum_{k = 0..n} (-1)^(n+k)*binomial(n, k)*binomial(n+k, k)*T(n-1, n-k) = A376458(n).
Sum_{k = 0..n} (-1)^(n+k)*binomial(n, k)*binomial(n+k, k)*T(i, k) = A143007(n, i). (End)
From Peter Bala, Oct 12 2024: (Start)
The square array = A063007 * transpose(A007318).
Conjecture: for positive integer m, Sum_{k = 0..n} (-1)^(n+k) * binomial(n, k) * T(m*n, k) = ((m+1)*n)!/( ((m-1)*n)!*n!^2) (verified up to m = 10 using the MulZeil procedure in Doron Zeilberger's MultiZeilberger package). (End)

A086581 Number of Dyck paths of semilength n with no DDUU.

Original entry on oeis.org

1, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, 20705, 62642, 190987, 586219, 1810011, 5617914, 17518463, 54857506, 172431935, 543861219, 1720737981, 5459867166, 17369553427, 55391735455, 177040109419, 567019562429, 1819536774089

Offset: 0

Michael Somos, Jul 22 2003

nonn

See A025242 for a bijection between paths avoiding UUDD versus DDUU.
Number of lattice paths, never going below the x-axis, from (0,0) to (n,0) consisting of up steps U(k) = (k,1) for every positive integer k, down steps D = (1,-1) and horizontal steps H. - José Luis Ramírez Ramírez, Apr 19 2015
Given a sequence variant with 0 inserted between the two 1's, the INVERT transform of the modified sequence is this sequence. - Gary W. Adamson, Jun 28 2015

			a(4) = 13 because of the 14 Dyck 4-paths only UUDDUUDD contains DDUU.

Robert Israel, Table of n, a(n) for n = 0..1709
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
Lu, Qing Lin Skew Motzkin paths Acta Math. Sin., Engl. Ser. 33, No. 5, 657-667 (2017) sequence s_n
T. Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math/0110039 [math.CO], 2001.
T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013
A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Cf. A025242, A082582.

Column k=0 of A114492.

F:= gfun:-rectoproc({(n+2)*a(n) +(n+3)*a(n-1) +2*(-9*n+4)*a(n-2) +10*(n-2)*a(n-3) +(n-4)*a(n-4) +5*(n-5)*a(n-5)=0, seq(a(n)=[1,1,2,5,13][n+1],n=0..4)},a(n),remember):
map(F, [$0..30]); # Robert Israel, Jun 29 2015

CoefficientList[ Series[(1 - 2 x + x^2 - Sqrt[1 - 4 x + 2 x^2 + x^4])/(2 x^2), {x, 0, 27}], x] (* Robert G. Wilson v, Mar 25 2011 *)

{a(n) = polcoeff((1 - 2*x + x^2 - sqrt(1 - 4*x + 2*x^2 + x^4 + x^3 * O(x^n))) / 2, n+2)}

a(n)=1+sum(k=0,n,sum(i=0,k,binomial(n-1,k)*binomial(2*i+2,i)*binomial(i+2,k-2*i-1)/(i+1))) \\ Thomas Baruchel, Jan 19 2015

G.f. A(x) satisfies the equation 0 = 1 - x - (1 - x)^2 * A(x) + (x * A(x))^2.
a(n) = A025242(n+1) = A082582(n+1).
G.f.: (1 - 2*x + x^2 - sqrt(1 - 4*x + 2*x^2 + x^4))  /(2 * x^2).
a(n+2) - 2*a(n+1) + a(n) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0).
G.f.: (1/(1-x))*c(x^2/(1-x)^3), c(x) the g.f. of A000108; a(n)=sum{k=0..floor(n/2), C(n+k,3k)*A000108(k)}. - Paul Barry, May 31 2006
Conjecture: (n+2)*a(n) +(n+3)*a(n-1) +2*(-9*n+4)*a(n-2) +10*(n-2)*a(n-3) +(n-4)*a(n-4) +5*(n-5)*a(n-5)=0. - R. J. Mathar, Nov 26 2012
G.f. satisfies (10*x^3-28*x^2+4*x+2)*A(x) + (5*x^6+x^5+10*x^4-18*x^3+x^2+x)*A'(x) = 5*x^4+x^3-15*x^2+7*x+2. This confirms R. J. Mathar's recurrence equation. - Robert Israel, Jun 29 2015
G.f.: 1 - G(0), where G(k)= 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013
G.f.: 1/G(0) where G(k) = 1 - q/(1 - q - q^2 / G(k+1) ); (continued fraction). - Joerg Arndt, Feb 27 2014
From Thomas Baruchel, Jan 19 2015: (Start)
a(n) = 1+Sum_{k=0..n} Sum_{i=0..k} C(n-1,k)*C(2i+2,i)*C(i+2,k-2i-1)/(i+1).
a(n) = Sum_{k=0..n} C(2k,k)*C(n+k,3k)/(k+1).
Sum_{k=0..n} a(k+1)*A108626(n-k) = Sum_{k=0..n} Sum_{i=0..k} binomial(n-k+1,i-1)*binomial(n-k+1,i)*binomial(n-i+1,k-i). (End)

Name corrected by David Scambler, Mar 28 2011

A171155 For two strings of length n, this is the number of pairwise alignments that do not have an insertion adjacent to a deletion.

Original entry on oeis.org

1, 1, 3, 9, 27, 83, 259, 817, 2599, 8323, 26797, 86659, 281287, 915907, 2990383, 9786369, 32092959, 105435607, 346950321, 1143342603, 3772698725, 12463525229, 41218894577, 136451431723, 452116980643, 1499282161375, 4975631425581, 16524213199923, 54913514061867

Offset: 0

Lee A. Newberg, Dec 04 2009

This is the number of walks from (0,0) to (n,n) where unit horizontal (+1,0), vertical (0,+1), and diagonal (+1,+1) steps are permitted but a horizontal step cannot be followed by a vertical step, nor vice versa.
a(n) is also the number of walks from (0,0) to (n,n) with steps that increment one or two coordinates and having the property that no two consecutive steps are orthogonal. - Lee A. Newberg, Dec 04 2009
a(n) is also the number of standard sequence alignments of two strings of length n, counting only those alignments with the property that, for every pair of consecutive alignment columns, there is at least one sequence that contributes a non-gap to both columns. That is, a(n) counts only those standard alignments with a column order that can be unambiguously reconstructed from the knowledge of all pairings, where a pairing is, e.g., that some i-th position of the first string is in the same column as some j-th position of the second string. - Lee A. Newberg, Dec 11 2009
First differences of A108626: a(n) = A108626(n) - A108626(n-1) for n>=1. - Thomas Baruchel, Nov 08 2014
The number of walls of height one in all bargraphs of semiperimeter n>=2. A wall is a maximal sequence of adjacent up steps. - Arnold Knopfmacher, Nov 04 2016
Main diagonal of Table 2 in Covington. - Peter Bala, Jan 27 2018
From Thierry Marchant, Oct 30 2024: (Start)
a(n) is also the number of maximal antichains in the product of two chains of length n.
a(n) is also the number of strict chains in the product of two chains of length n (a strict chain P in a product of two chains is a chain such that x,y in P implies x_1 different from y_1 and x_2 different from y_2). (End)

			For n = 3, the 9 alignments are:
ABC A-BC ABC- -ABC -ABC --ABC ABC- AB-C ABC--
DEF DEF- D-EF DEF- DE-F DEF-- -DEF -DEF --DEF

Alois P. Heinz, Table of n, a(n) for n = 0..1000
A. Blecher, C. Brennan and A. Knopfmacher, Walls in bargraphs, preprint.
Denis Bouyssou, Thierry Marchant, and Marc Pirlot, About maximal antichains in a product of two chains:A catch-all note, arXiv:2410.16243 [math.CO], 2024. See pp. 1, 3, 16-18.
Denis Bouyssou, Thierry Marchant, and Marc Pirlot, ELECTRE TRI-nB, pseudo-disjunctive: axiomatic and combinatorial results, arXiv:2410.18443 [cs.DM], 2024. See p. 14.
M. A. Covington, The Number of Distinct Alignments of Two Strings, Journal of Quantitative Linguistics, Vol.11 (2004), Issue3, pp. 173-182

See A171158 for the number of such walks in three dimensions. - Lee A. Newberg, Dec 04 2009
See A171563 for the number of such walks in four dimensions. - Lee A. Newberg, Dec 11 2009
Cf. A108626.
Main diagonal of A180091.

a:= proc(n) option remember; `if`(n<4, [1, 1, 3, 9][n+1],
      ((4*n-3)*a(n-1) -(2*n-5)*a(n-2) +a(n-3) -(n-3)*a(n-4))/n)
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 22 2013

CoefficientList[Series[Sqrt[(1 - x) / (1 - 3 x - x^2 - x^3)], {x, 0, 40}], x] (* Vincenzo Librandi, Nov 09 2014 *)

my(x='x+O('x^66)); Vec(sqrt((1-x)/(1-3*x-x^2-x^3))) \\ Joerg Arndt, May 11 2013

{a(n)=polcoeff(sum(m=0, n, (2*m)!/m!^2 * x^(2*m) / (1-x+x*O(x^n))^(3*m+1)), n)} \\ Paul D. Hanna, Sep 21 2013

{a(n)=polcoeff( sum(m=0,n, x^m * sum(k=0,m, binomial(m,k)^2 * x^k) / (1-x +x*O(x^n))^m) ,n)}
for(n=0,30,print1(a(n),", ")) \\ Paul D. Hanna, Nov 08 2014

a(n)=sum(k=0, n, sum(i=0, k, binomial(n-k, i)^2*binomial(n-i, k-i)))-sum(k=0, n-1, sum(i=0, k, binomial(n-k-1, i)^2*binomial(n-i-1, k-i))) \\ Thomas Baruchel, Nov 09 2014

a(n) = ((4*n-3)*a(n-1)-(2*n-5)*a(n-2)+a(n-3)-(n-3)*a(n-4))/n. - Alois P. Heinz, Jan 22 2013
G.f.: sqrt((1-x)/(1-3*x-x^2-x^3)). - Mark van Hoeij, May 10 2013
G.f.: Sum_{n>=0} (2*n)!/n!^2 * x^(2*n) / (1-2*x)^(3*n+1). - Paul D. Hanna, Sep 21 2013
G.f.: Sum_{n>=0} x^n/(1-x)^n * Sum_{k=0..n} C(n,k)^2 * x^k. - Paul D. Hanna, Nov 08 2014

Extended beyond a(19) by Alois P. Heinz, Jan 22 2013

A180091 a(m,n) is the number of ways to split two strings of length m and n, respectively, into the same number of nonempty parts such that at least one of the corresponding parts has length 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 5, 9, 1, 4, 8, 15, 27, 1, 5, 12, 24, 46, 83, 1, 6, 17, 37, 75, 143, 259, 1, 7, 23, 55, 118, 237, 450, 817, 1, 8, 30, 79, 180, 380, 755, 1429, 2599, 1, 9, 38, 110, 267, 592, 1229, 2421, 4570, 8323

Offset: 1

Steffen Eger, Jan 14 2011

a(m,n) is also the number alignments (between two strings) that satisfy weak monotonicity, completeness, and disjointness.
a(m,n) is also the number of monotone lattice paths from (0,0) to (m,n) with steps in {(1,1),(1,2),(1,3),(1,4),...,(2,1),(3,1),(4,1),...}. - Steffen Eger, Sep 25 2012
From Julien Rouyer, Jun 02 2023: (Start)
a(m-1,n-1) is also the number of strictly increasing functions defined on a part of the m-set {1,...,m} that take values in the n-set {1,...,n} and that can't be extended to a greater part of the m-set to give another strictly increasing function (values for m < n can be obtained by symmetry).
a(m-1,n-1) is also the number of solutions to the problem consisting of connecting, with noncrossing edges, some of m points aligned on a straight line to some of n other points aligned on a parallel straight line (each point is connected at most with one other point), in such a way that no additional noncrossing connection can be added.
A direct combinatorial calculation is possible, but time-consuming if m and n are large. (End)
From Thierry Marchant, Oct 30 2024: (Start)
a(m,n) is also the number of maximal antichains in the product of two chains of length m and n.
a(m,n) is also the number of strict chains in the product of two chains of length m and n (a strict chain P in a product of two chains is a chain such that x,y in P implies x_1 different from y_1 and x_2 different from y_2).
a(m,n) is also the number of walks from (0,0) to (m,n) where unit horizontal (+1,0), vertical (0,+1), and diagonal (+1,+1) steps are permitted but a horizontal step cannot be followed by a vertical step, nor vice versa. (End)

			For m=4, n=3, the 5 possibilities are:
a) X XXX   b) XXX X  c) X XX X  d) XX X X   e) X X XX
   YY Y        Y YY     Y  Y Y     Y  Y Y      Y Y Y
The triangle a(m,n) starts in row m=1 with columns 1 <= n <= m as:
  1;
  1,  1;
  1,  2,  3;
  1,  3,  5,   9;
  1,  4,  8,  15,  27;
  1,  5, 12,  24,  46,   83;
  1,  6, 17,  37,  75,  143,  259;
  1,  7, 23,  55, 118,  237,  450,  817;
  1,  8, 30,  79, 180,  380,  755, 1429,  2599;
  1,  9, 38, 110, 267,  592, 1229, 2421,  4570,  8323;
  1, 10, 47, 149, 386,  899, 1948, 3989,  7804, 14698, 26797;
  1, 11, 57, 197, 545, 1334, 3015, 6412, 12987, 25264, 47491, 86659;
From _Julien Rouyer_, Jun 02 2023: (Start)
There are a(5)=T(3,2)=5 strictly increasing functions defined on a part of {1,2,3} that take values in {1,2} and can't be extended keeping the same properties. The 5 functions are defined by
    f(1)=1, f(2)=2;
    g(1)=1, g(2)=3;
    h(1)=2, h(2)=3;
    i(1)=3;
    j(2)=1. (End)

D. Bouyssou, T. Marchant, and M. Pirlot, About maximal antichains in a product of two chains:A catch-all note, arXiv:2410.16243 [math.CO], 2024. See pp. 1, 3, 16-18.
M. A. Covington, The Number of Distinct Alignments of Two Strings, Journal of Quantitative Linguistics, Vol. 11 (2004), Issue 3, pp. 173-182.
S. Eger, Derivation of sequence [broken link]

Cf. A089071 (third column), A108626 (sums of diagonals).
Main diagonal gives A171155.
Cf. A047080.

A180091 := proc(m,n) a := binomial(m-1,n-1); for k from 2 to n-1 do for l from 1 to k-1 do if k-l-1 >= 0 and k-l-1 <= n-k-1 and l-1 >=0 and l-1 <= m+l-k-1 then a := a+ binomial(k,l)*binomial(n-k-1,k-l-1)*binomial(m+l-k-1,l-1); end if; end do: end do: a; end proc: # R. J. Mathar, Feb 01 2011

# The following program gives T(m,n)=a(m+1,n+1) for any m >= 0 and n >= 0:
def T(m,n):
    if n == 0:
        res = 1
    elif n == 1:
        res = max(m,n)
    elif m < n:
        res = T(n,m)
    else:
        res = 0
        for i in range(1,m+1):
            res += T(m-i,n-1)
        for j in range(2,n+1):
            res += T(m-1,n-j)
    return res # Julien Rouyer, Jun 02 2023

For m >= n: a(m,n) = C(m-1,n-1) + Sum_{k=2..n-1} Sum_{i=1..k-1} C(k,i)*C(n-k-1,k-i-1)*C(m+i-k-1,i-1).
Symmetrically extended to m <= n by a(m,n) = a(n,m).
a(n,n) = A171155(n-1).
a(m,n) = Sum_{i=1..m} a(m-i,n-1) + Sum_{j=2..n} a(m-1,n-j). - Julien Rouyer, Jun 02 2023

A299500 Triangle read by rows, T(n,k) = [x^k] Sum_{k=0..n} p_{n,k}(x) where p_{n,k}(x) = x^(n-k)binomial(n,k)hypergeom([-k, k-n, k-n], [1, -n], 1/x), for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 3, 7, 3, 1, 5, 16, 15, 4, 1, 8, 38, 46, 26, 5, 1, 13, 82, 141, 100, 40, 6, 1, 21, 173, 381, 375, 185, 57, 7, 1, 34, 352, 983, 1216, 820, 308, 77, 8, 1, 55, 701, 2400, 3704, 3101, 1575, 476, 100, 9, 1, 89, 1368, 5646, 10536, 10885, 6804, 2758, 696, 126, 10, 1

Offset: 0

Peter Luschny, Feb 11 2018

			The partial polynomials p_{n,k}(x) start:
[0] 1
[1] x,   1
[2] x^2, 2*x+1,        1
[3] x^3, 3*x^2+4*x,    3*x+2,             1
[4] x^4, 4*x^3+9*x^2,  6*x^2+12*x+1,      4*x+3,         1
[5] x^5, 5*x^4+16*x^3, 10*x^3+36*x^2+9*x, 10*x^2+24*x+3, 5*x+4, 1
.
The polynomials P_{n}(x) start:
[0]  1
[1]  1 +    x
[2]  2 +  2*x +    x^2
[3]  3 +  7*x +  3*x^2 +    x^3
[4]  5 + 16*x + 15*x^2 +  4*x^3 +   x^4
[5]  8 + 38*x + 46*x^2 + 26*x^3 + 5*x^4 + x^5
.
The triangle starts:
[0]  1
[1]  1,   1
[2]  2,   2,    1
[3]  3,   7,    3,    1
[4]  5,  16,   15,    4,    1
[5]  8,  38,   46,   26,    5,    1
[6] 13,  82,  141,  100,   40,    6,   1
[7] 21, 173,  381,  375,  185,   57,   7,   1
[8] 34, 352,  983, 1216,  820,  308,  77,   8, 1
[9] 55, 701, 2400, 3704, 3101, 1575, 476, 100, 9, 1'
.
The square array P_{n}(k) near k=0:
......  [k=-2] 1, -1,  2, -7,  17,  -44,  125,  -345,    958,   -2707, ...
A182883 [k=-1] 1,  0,  1, -2,   1,   -6,    7,   -12,     31,     -40, ...
A000045 [k=0]  1,  1,  2,  3,   5,    8,   13,    21,     34,      55, ...
A108626 [k=1]  1,  2,  5, 14,  41,  124,  383,  1200,   3799,   12122, ...
A299501 [k=2]  1,  3, 10, 37, 145,  588, 2437, 10251,  43582,  186785, ...
......  [k=3]  1,  4, 17, 78, 377, 1886, 9655, 50220, 264223, 1402108, ...

Cf. A000045, A108625, A108626, A182883, A299499, A299501, A299502.

CoeffList := p -> op(PolynomialTools:-CoefficientList(p,x)):
PrintPoly := p -> print(sort(expand(p),x,ascending)):
T := (n,k) -> x^(n-k)*binomial(n, k)*hypergeom([-k,k-n,k-n], [1,-n], 1/x):
P := [seq(add(simplify(T(n,k)),k=0..n), n=0..10)]:
seq(CoeffList(p), p in P); # seq(PrintPoly(p), p in P);
R := proc(n,k) option remember; # Recurrence
if n < 4 then return [1,k+1,(k+1)^2+1,(k+1)^3+4*k+2][n+1] fi; ((2-n)*R(n-4,k)-
(3-2*n)*(k-1)*R(n-3,k)+(k^2+2*k-1)*(1-n)*R(n-2,k)+(2*n-1)*(k+1)*R(n-1,k))/n end:
for k from -2 to 3 do lprint(seq(R(n,k), n=0..9)) od;

Let P_{n}(x) = Sum_{k=0..n} p_{n,k}(x) then
2^n*P_{n}(1/2) = A299502(n).
P_{n}(-1) = A182883(n). P_{n}(0) = A000045(n+1).
P_{n}(1) = A108626(n).  P_{n}(2) = A299501(n).
The general case: for fixed k the sequence P_{n}(k) with n >= 0 has the generating function ogf(k, x) = (1-2*(k+1)*x + (k^2+2*k-1)*x^2 - 2*(k-1)*x^3 + x^4)^(-1/2).  The example section shows the start of this square array of sequences.
These sequences can be computed by the recurrence P(n,k) = ((2-n)*P(n-4,k)-(3-2*n)*(k-1)*P(n-3,k)+(k^2+2*k-1)*(1-n)*P(n-2,k)+(2*n-1)*(k+1)*P(n-1,k))/n with initial values 1, k+1, (k+1)^2+1 and (k+1)^3+4*k+2.
The partial polynomials p_{n,k}(x) reduce for x = 1 to A108625 (seen as a triangle).

A299499 Triangle read by rows, T(n,k) = [x^k] Sum_{k=0..n} p_{n,k}(x) where p_{n,k}(x) = x^kbinomial(n, k)hypergeom([-k, k-n, k-n], [1, -n], 1/x), for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 5, 3, 1, 11, 16, 9, 4, 1, 26, 44, 34, 14, 5, 1, 63, 122, 111, 60, 20, 6, 1, 153, 341, 351, 225, 95, 27, 7, 1, 376, 940, 1103, 796, 400, 140, 35, 8, 1, 931, 2581, 3384, 2764, 1561, 651, 196, 44, 9, 1, 2317, 7064, 10224, 9304, 5915, 2772, 994, 264, 54, 10, 1

Offset: 0

Peter Luschny, Feb 11 2018

			The partial polynomials p_{n,k}(x) start:
[0] 1
[1] 1, x
[2] 1, 2*x+ 1,    x^2
[3] 1, 3*x+ 4,  3*x^2+ 2*x,      x^3
[4] 1, 4*x+ 9,  6*x^2+12*x+1,  4*x^3+ 3*x^2,       x^4
[5] 1, 5*x+16, 10*x^2+36*x+9, 10*x^3+24*x^2+3*x, 5*x^4+4*x^3, x^5
.
The polynomials P_{n}(x) start:
[0]   1
[1]   1 +    x
[2]   2 +  2*x +    x^2
[3]   5 +  5*x +  3*x^2 +    x^3
[4]  11 + 16*x +  9*x^2 +  4*x^3 +   x^4
[5]  26 + 44*x + 34*x^2 + 14*x^3 + 5*x^4 + x^5
.
The triangle starts:
[0]   1
[1]   1,    1
[2]   2,    2,    1
[3]   5,    5,    3,    1
[4]  11,   16,    9,    4,    1
[5]  26,   44,   34,   14,    5,   1
[6]  63,  122,  111,   60,   20,   6,   1
[7] 153,  341,  351,  225,   95,  27,   7,  1
[8] 376,  940, 1103,  796,  400, 140,  35,  8, 1
[9] 931, 2581, 3384, 2764, 1561, 651, 196, 44, 9, 1
.
The square array P_{n}(k) near k=0:
......  [k=-2] 1, -1,  2, -1,  -1,   10,  -25,    51,    -68,     41, ...
A182883 [k=-1] 1,  0,  1,  2,   1,    6,    7,    12,     31,     40, ...
A051286 [k=0]  1,  1,  2,  5,  11,   26,   63,   153,    376,    931, ...
A108626 [k=1]  1,  2,  5, 14,  41,  124,  383,  1200,   3799,  12122, ...
A299443 [k=2]  1,  3, 10, 35, 127,  474, 1807,  6999,  27436, 108541, ...
......  [k=3]  1,  4, 17, 74, 329, 1490, 6855, 31956, 150607, 716236, ...

Cf. A051286, A108625, A108626, A182883, A298611, A299443, A299500.

CoeffList := p -> op(PolynomialTools:-CoefficientList(p,x)):
PrintPoly := p -> print(sort(expand(p),x,ascending)):
T := (n,k) -> x^k*binomial(n, k)*hypergeom([-k,k-n,k-n], [1,-n], 1/x):
P := [seq(add(simplify(T(n,k)),k=0..n), n=0..10)]:
seq(CoeffList(p), p in P); seq(PrintPoly(p), p in P);
R := proc(n,k) option remember; # Recurrence
if n < 4 then return [1,k+1,(k+1)^2+1,(k+1)^3+2*k+4][n+1] fi; ((2-n)*R(n-4,k)+
(3-2*n)*(k-1)*R(n-3,k)+(k^2+2*k-1)*(1-n)*R(n-2,k)+(2*n-1)*(k+1)*R(n-1,k))/n end:
for k from -2 to 3 do lprint(seq(R(n,k), n=0..9)) od;

nmax = 10;
p[n_, k_, x_] := x^k*Binomial[n, k]*HypergeometricPFQ[{-k, k-n, k-n}, {1, -n}, 1/x];
p[n_, x_] := Sum[p[n, k, x], {k, 0, n}];
Table[CoefficientList[p[n, x], x], {n, 0, nmax}] // Flatten (* Jean-François Alcover, Feb 26 2018 *)

Let P_{n}(x) = Sum_{k=0..n} p_{n,k}(x) then
2^n*P_{n}(1/2) = A298611(n).
P_{n}(-1) = A182883(n), P_{n}(0) = A051286(n).
P_{n}( 1) = A108626(n), P_{n}(2) = A299443(n).
The general case: for fixed k the sequence P_{n}(k) with n >= 0 has the generating function ogf(k, x) = (1-2*(k+1)*x + (k^2+2*k-1)*x^2 + 2*(k-1)*x^3 + x^4)^(-1/2).  The example section shows the start of this square array of sequences.
These sequences can be computed by the recurrence P(n,k) = ((2-n)*P(n-4,k)+(3-2*n)*(k-1)*P(n-3,k)+(k^2+2*k-1)*(1-n)*P(n-2,k)+(2*n-1)*(k+1)*P(n-1,k))/n with initial values 1, k+1, (k+1)^2+1 and (k+1)^3+2*k+4.
The partial polynomials p_{n,k}(x) reduce for x = 1 to A108625 (seen as a triangle).

cp's OEIS Frontend

A108627 Logarithmic g.f.: Sum_{n>=1} a(n)/n*x^n = log(G108626(x)), where G108626(x) is g.f. for A108626.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI

Formula

A108625 Square array, read by antidiagonals, where row n equals the crystal ball sequence for the A_n lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A086581 Number of Dyck paths of semilength n with no DDUU.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A171155 For two strings of length n, this is the number of pairwise alignments that do not have an insertion adjacent to a deletion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

Extensions

A180091 a(m,n) is the number of ways to split two strings of length m and n, respectively, into the same number of nonempty parts such that at least one of the corresponding parts has length 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

A299500 Triangle read by rows, T(n,k) = [x^k] Sum_{k=0..n} p_{n,k}(x) where p_{n,k}(x) = x^(n-k)*binomial(n,k)*hypergeom([-k, k-n, k-n], [1, -n], 1/x), for 0 <= k <= n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

A299499 Triangle read by rows, T(n,k) = [x^k] Sum_{k=0..n} p_{n,k}(x) where p_{n,k}(x) = x^k*binomial(n, k)*hypergeom([-k, k-n, k-n], [1, -n], 1/x), for 0 <= k <= n.

A299500 Triangle read by rows, T(n,k) = [x^k] Sum_{k=0..n} p_{n,k}(x) where p_{n,k}(x) = x^(n-k)binomial(n,k)hypergeom([-k, k-n, k-n], [1, -n], 1/x), for 0 <= k <= n.

A299499 Triangle read by rows, T(n,k) = [x^k] Sum_{k=0..n} p_{n,k}(x) where p_{n,k}(x) = x^kbinomial(n, k)hypergeom([-k, k-n, k-n], [1, -n], 1/x), for 0 <= k <= n.