A180091 -id:A180091 - cp's OEIS frontend

A108626 Antidiagonal sums of square array A108625, in which row n equals the crystal ball sequence for A_n lattice.

1, 2, 5, 14, 41, 124, 383, 1200, 3799, 12122, 38919, 125578, 406865, 1322772, 4313155, 14099524, 46192483, 151628090, 498578411, 1641921014, 5414619739, 17878144968, 59097039545, 195548471268, 647665451911, 2146947613286

Offset: 0

Paul D. Hanna, Jun 12 2005

nonn

Limit a(n+1)/a(n) = 3.3829757679... = 1/r = 3 + r + r^2, where r is radius of convergence of A(x), which diverges at x=r.

Infinitely many recurrence relations of even order 2d can be built for this sequence; first define the following polynomial: P(d) = (1/2^d) * Sum_{i=0..floor(d/2)} binomial(d, 2*i) * (x^4 + 2*x^2 - 4*x + 1)^i * (x^2 + 2*x - 1)^(d - 2*i) then call c(d,k) the coefficient of term with power k in the polynomial P(d); then we have the relation: Sum_{k=0..2*d} c(d, 2*d-k)*a(n+k) = (-1)^d * Sum_{k=0..n} Sum_{i=0..k} binomial(n-k, d+i)*binomial(n-k, i)*binomial(n-i, k-i). - Thomas Baruchel, Jan 26 2015

			Log(A(x)) = 2*x + 6*x^2/2 + 20*x^3/3 + ... + A108627(n)*x^n/n + ...

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Thomas Baruchel and C. Elsner, On error sums formed by rational approximations with split denominators, arXiv preprint arXiv:1602.06445 [math.NT], 2016.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020, p. 16.

Cf. A108625, A108627, A180091.

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( 1/Sqrt(1-4*x+2*x^2+x^4) )); // G. C. Greubel, Oct 06 2023

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

CoefficientList[Series[1/Sqrt[x^4+2*x^2-4*x+1], {x, 0, 50}], x] (* Vincenzo Librandi, Nov 08 2014 *)

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

{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+1)) , n)}
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Nov 08 2014

def A108626_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/sqrt(1-4*x+2*x^2+x^4) ).list()
A108626_list(40) # G. C. Greubel, Oct 06 2023

a(n) = Sum_{k=0..n} Sum_{i=0..k} C(n, i)^2 * C(n+k-i, k-i).
G.f.: 1 / sqrt(x^4 + 2*x^2 - 4*x + 1). - Thomas Baruchel, Nov 08 2014
G.f.: A(x) = exp( Sum_{n>=1} A108627(n)*x^n/n ), where A108627 has g.f.: 2*x*(1 - x - x^3)/((1-x)*(1 - 3*x - x^2 - x^3)).
a(n) = ( (5*n-3)*a(n-1) - (6*n-8)*a(n-2) + (2*n-4)*a(n-3) - (n-2)*a(n-4) + (n-3)*a(n-5) ) / n. - Thomas Baruchel, Nov 08 2014
a(n+2) - 2*a(n+1) - a(n) = 2*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) = Sum_{k=0..n} a(k)*A086581(n-k+1). - Thomas Baruchel, Nov 08 2014
G.f.: Sum_{n>=0} (2*n)!/n!^2 * x^(2*n) / ((1-x)*(1-2*x)^(3*n+1)). - Paul D. Hanna, Nov 08 2014
G.f.: Sum_{n>=0} x^n/(1-x)^(n+1) * Sum_{k=0..n} C(n,k)^2 * x^k. - Paul D. Hanna, Nov 08 2014
Partial sums of A171155: a(n) = Sum_{i=0..n} A171155(n). - Thomas Baruchel, Nov 08 2014
Recurrence: n*a(n) = 2*(2*n-1)*a(n-1) - 2*(n-1)*a(n-2) - (n-2)*a(n-4). - Vaclav Kotesovec, Dec 20 2015
a(n) = Sum_{k=0..n} binomial(n,k)*hypergeometric3F2([-k,k-n,k-n], [1,-n], 1). - Peter Luschny, Feb 13 2018

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

A185287 R(m,n) is the number of ways to split two strings x and y 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 and such that the parts of the y string have at most size 2.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 3, 0, 0, 1, 4, 5, 3, 0, 0, 1, 5, 8, 7, 3, 0, 0, 1, 6, 12, 13, 7, 0, 0, 0, 1, 7, 17, 22, 16, 6, 0, 0, 0, 1, 8, 23, 35, 32, 17, 4, 0, 0, 0, 1, 9, 30, 53, 58, 39, 14, 0, 0, 0, 0, 1, 10, 38, 77, 98, 80, 40, 10, 0, 0

Offset: 1

Steffen Eger, Feb 20 2011

			1    0    0    0    0    0    0    0    0    0    0    0
1    1    2    0    0    0    0    0    0    0    0    0
1    2    3    3    3    0    0    0    0    0    0    0
1    3    5    7    7    6    4    0    0    0    0    0
1    4    8   13   16   17   14   10    5    0    0    0
1    5   12   22   32   39   40   35   25   15    6    0
1    6   17   35   58   80   95   97   86   65   41   21
1    7   23   53   98  151  201  233  238  213  167  112
1    8   30   77  157  267  392  505  577  587  532  427
1    9   38  108  241  448  718 1013 1273 1436 1458 1333
1   10   47  147  357  720 1250 1912 2612 3217 3590 3640
1   11   57  195  513 1116 2086 3434 5056 6728 8146 9011

Cf. A180091.

r[m_, n_] := Binomial[m-1, n-1] + Sum[ Binomial[k, 2k-n]*Binomial[k+m-n-1, 2k-n-1], {k, 2, n-1}]; r[m_, n_] /; n > 2m-1 = 0; Flatten[ Table[ r[m-k+1, k], {m, 1, 12}, {k, 1, m}]] (* Jean-François Alcover, Nov 07 2011 *)

PARI
```
C(n,k)=if(nJoerg Arndt, Mar 11 2011 */
```

R(m,n) = C(m-1,n-1) + Sum_{k=2..n-1} C(m+k-n-1,2*k-n-1)*C(k,2*k-n).

A191588 T(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 and such that the parts have at most size 2.

Original entry on oeis.org

1, 1, 1, 0, 2, 3, 0, 1, 3, 7, 0, 0, 3, 7, 13, 0, 0, 1, 6, 17, 27, 0, 0, 0, 4, 14, 36, 61, 0, 0, 0, 1, 10, 35, 77, 133, 0, 0, 0, 0, 5, 25, 81, 173, 287, 0, 0, 0, 0, 1, 15, 65, 183, 387, 633, 0, 0, 0, 0, 0, 6, 41, 161, 421, 857, 1407, 0, 0, 0, 0, 0, 1, 21, 112, 385, 969, 1911, 3121, 0, 0, 0, 0, 0, 0, 7, 63, 294, 918, 2211, 4287, 6943, 0, 0, 0, 0, 0, 0, 1, 28, 182, 742, 2181, 5040, 9619, 15517, 0, 0

Offset: 1

Steffen Eger, Jun 09 2011

Diagonal appears to be A098479. - Joerg Arndt, Jun 09 2011

T(m,n) is the number of lattice paths from (0,0) to (m,n) with steps in {(1,1),(1,2),(2,1)}. - Steffen Eger, Sep 25 2012

			1
1 1
0 2 3
0 1 3 7
0 0 3 7 13
0 0 1 6 17 27
0 0 0 4 14 36 61
0 0 0 1 10 35 77 133
0 0 0 0  5 25 81 173 287
0 0 0 0  1 15 65 183 387 633
0 0 0 0  0  6 41 161 421 857 1407
0 0 0 0  0  1 21 112 385 969 1911 3121
0 0 0 0  0  0  7  63 294 918 2211 4287  6943
0 0 0 0  0  0  1  28 182 742 2181 5040  9619 15517
0 0 0 0  0  0  0   8  92 504 1842 5134 11508 21602 34755
Examples:
For m=3, n=2, we have
  x xx     xx x
  y  y      y y
For m=3, n=3, we have
  x xx     xx x   x x x
  yy y      y yy  y y y
For m=4, n=4, we have
  x xx x   x xx x   xx x x   xx x x   x x xx  x x xx   x x x x
  yy y y   y y yy   y yy y    y y yy  y yy y  yy y y   y y y y

Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.

Cf. A180091, A185287, A098479 (diagonal).

t[m_, n_] /; m >= n := t[m, n] = Binomial[n, 2n - m] + Sum[Binomial[k, 2k - n]*Binomial[2k - n, 3k - n - m], {k, 2, n-1}]; t[m_, n_] /; m < n := t[m, n]; Table[t[n, m], {n, 1, 14}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 07 2013, from formula *)

For m >= n: T(m,n) = C(n,2*n-m) + Sum_{k=2..n-1} C(k,2*k-n)*C(2*k-n,3*k-n-m) (note: C(2*k-n,3*k-n-m) = C(2*k-n,m-k)) where C(n,k) = binomial(n,k) for n >= k and 0 otherwise.

Symmetrically extended by T(n,m) = T(m,n).

cp's OEIS Frontend

A108626 Antidiagonal sums of square array A108625, in which row n equals the crystal ball sequence for A_n lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

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

A185287 R(m,n) is the number of ways to split two strings x and y 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 and such that the parts of the y string have at most size 2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A191588 T(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 and such that the parts have at most size 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula