A171155 -id:A171155 - cp's OEIS frontend

A047080 Triangular array T read by rows: T(h,k)=number of paths from (0,0) to (k,h-k) using step-vectors (0,1), (1,0), (1,1) with no right angles between pairs of consecutive steps.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 3, 1, 1, 4, 5, 5, 4, 1, 1, 5, 8, 9, 8, 5, 1, 1, 6, 12, 15, 15, 12, 6, 1, 1, 7, 17, 24, 27, 24, 17, 7, 1, 1, 8, 23, 37, 46, 46, 37, 23, 8, 1, 1, 9, 30, 55, 75, 83, 75, 55, 30, 9, 1, 1, 10, 38, 79, 118, 143, 143, 118, 79, 38, 10, 1

Offset: 0

Clark Kimberling

T(n,k) equals the number of reduced alignments between a string of length n and a string of length k. See Andrade et. al. - Peter Bala, Feb 04 2018

			E.g., row 3 consists of T(3,0)=1; T(3,1)=2; T(3,2)=2; T(3,3)=1.
Triangle begins:
  1;
  1,  1;
  1,  1,  1;
  1,  2,  2,  1;
  1,  3,  3,  3,  1;
  1,  4,  5,  5,  4,  1;
  1,  5,  8,  9,  8,  5,  1;
  1,  6, 12, 15, 15, 12,  6,  1;

Muniru A Asiru, Table of n, a(n) for n = 0..1325
H. Andrade, I. Area, J. J. Nieto, and A. Torres, The number of reduced alignments between two DNA sequences, BMC Bioinformatics (2014) Vol. 15: 94.

Cf. A047081, A047082, A047083, A047084, A047085, A047086, A047087, A047088.

Cf. A001590, A022856, A028310, A078042, A089071, A091337, A171155.

F:=Factorial;
p:= func< n,k | (&+[ (-1)^j*F(n+k-3*j)/(F(j)*F(n-2*j)*F(k-2*j)): j in [0..Min(Floor(n/2), Floor(k/2))]]) >;
q:= func< n,k | n eq 0 or k eq 0 select 0 else (&+[ (-1)^j*F(n+k-3*j-2)/(F(j)*F(n-2*j-1)*F(k-2*j-1)) : j in [0..Min(Floor((n-1)/2), Floor((k-1)/2))]]) >;
A:= func< n,k | p(n,k) - q(n,k) >;
A047080:= func< n,k | n eq 0 select 1 else A(n-k, k) >;
[[A(n,k): k in [1..6]]: n in [1..6]];
[A047080(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 30 2022

T := proc(n, k) option remember; if n < 0 or k > n then return 0 fi;
if n < 3 then return 1 fi; if k < iquo(n,2) then return T(n, n-k) fi;
T(n-1, k-1) + T(n-1, k) - T(n-4, k-2)  end:
seq(seq(T(n,k), k=0..n), n=0..11); # Peter Luschny, Feb 11 2018

T[n_, k_] := T[n, k] = Which[n<0 || k>n, 0, n<3, 1, kJean-François Alcover, Jul 30 2018 *)

f=factorial
def p(n,k): return sum( (-1)^j*f(n+k-3*j)/(f(j)*f(n-2*j)*f(k-2*j)) for j in range(1+min((n//2), (k//2))) )
def q(n,k): return sum( (-1)^j*f(n+k-3*j-2)/(f(j)*f(n-2*j-1)*f(k-2*j-1)) for j in range(1+min(((n-1)//2), ((k-1)//2))) )
def A(n,k): return p(n,k) - q(n,k)
def A047080(n,k): return A(n-k, k)
flatten([[A047080(n,k) for k in range(n+1)] for n in range(14)]) # G. C. Greubel, Oct 30 2022

T(h, k) = T(h-1, k-1) + T(h-1, k) - T(h-4, k-2);
Writing T(h, k) = F(h-k, k), generating function for F is (1-xy)/(1-x-y+x^2y^2).
From Peter Bala, Feb 04 2018: (Start)
T(n, k) = (Sum_{i = 0..A} (-1)^i*(n+k-3*i)!/(i!*(n-2*i)!*(k-2*i)!)) - (Sum_{i = 0..B} (-1)^i*(n+k-3*i-2)!/(i!*(n-2*i-1)!*(k-2*i-1)!)), where A = min{floor(n/2), floor(k/2)} and B = min{floor((n-1)/2), floor((k-1)/2)}.
T(2*n, n) = A171155(n). (End)
From G. C. Greubel, Oct 30 2022: (Start) (formulas for triangle T(n,k))
T(n, n-k) = T(n, k).
T(n, n) = A000012(n).
T(n, n-1) = A028310(n-1).
T(n, n-2) = A089071(n-1) = A022856(n+1).
T(2*n, n-1) = A047087(n).
T(2*n+1, n-1) = A047088(n).
Sum_{k=0..n} T(n, k) = (-1)^n*A078042(n) = A001590(n+3).
Sum_{k=0..n} (-1)^k*T(n, k) = A091337(n+1).
Sum_{k=0..floor(n/2)} T(n, k) = A047084(n). (End)

Sequence recomputed to correct terms from 23rd onward, and recurrence and generating function added by Michael L. Catalano-Johnson (mcj(AT)pa.wagner.com), Jan 14 2000

A047085 a(n) = T(2*n, n), array T as in A047080.

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

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A047080, A047081, A047082, A047083, A047084, A047086, A047087, A047088.

Cf. A171155.

R:=PowerSeriesRing(Rationals(), 50); Coefficients(R!( Sqrt((1-x)/(1 -3*x-x^2-x^3)) )); // G. C. Greubel, Oct 30 2022

CoefficientList[Series[Sqrt[(1-x)/(1-3*x-x^2-x^3)], {x, 0, 50}], x] (* G. C. Greubel, Oct 30 2022 *)

def A047085_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( sqrt((1-x)/(1-3*x-x^2-x^3)) ).list()
A047085_list(50) # G. C. Greubel, Oct 30 2022

From G. C. Greubel, Oct 30 2022: (Start)
a(n) = A171155(n).
G.f.: sqrt((1 - x)/(1 - 3*x - x^2 - x^3)). (End)

Data corrected by Sean A. Irvine, May 11 2021

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

Original entry on oeis.org

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

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

A171158 The number of walks from (0,0,0) to (n,n,n) with steps that increment one to three coordinates and having the property that no two consecutive steps are orthogonal.

Original entry on oeis.org

1, 1, 19, 235, 3181, 44725, 648439, 9614329, 145020445, 2217212539, 34269961873, 534449721793, 8397498847645, 132785160326593, 2111135363144743, 33723822603109987, 540949658114010583, 8708952402795685879, 140665766088396528829, 2278642960112808284773

Offset: 0

Lee A. Newberg, Dec 04 2009

a(n) is also the number of standard sequence alignments of three 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 some string x is in the same column as some j-th position of some string y. - Lee A. Newberg, Dec 11 2009

			For n = 2, the 19 walks are:
000 -> 001 -> 012 -> 122 -> 222
000 -> 001 -> 102 -> 212 -> 222
000 -> 001 -> 112 -> 222
000 -> 010 -> 021 -> 122 -> 222
000 -> 010 -> 120 -> 221 -> 222
000 -> 010 -> 121 -> 222
000 -> 011 -> 112 -> 222
000 -> 011 -> 121 -> 222
000 -> 011 -> 122 -> 222
000 -> 100 -> 201 -> 212 -> 222
000 -> 100 -> 210 -> 221 -> 222
000 -> 100 -> 211 -> 222
000 -> 101 -> 112 -> 222
000 -> 101 -> 211 -> 222
000 -> 101 -> 212 -> 222
000 -> 110 -> 121 -> 222
000 -> 110 -> 211 -> 222
000 -> 110 -> 221 -> 222
000 -> 111 -> 222

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

See A171155 for the number of such walks in two dimensions.

See A171563 for the number of such walks in four dimensions. - Lee A. Newberg, Dec 11 2009

a(n) ~ c * d^n / n, where d = 17.073685937995..., c = 0.171212682922... . - Vaclav Kotesovec, Sep 10 2014

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

A171563 The number of walks from (0,0,0,0) to (n,n,n,n) with steps that increment one to four coordinates and having the property that no two consecutive steps are orthogonal.

Original entry on oeis.org

1, 1, 183, 12645, 985035, 81827267, 7118644591, 640769321689, 59196873690319, 5581678517756599, 535018115452292125, 51979823843828063203, 5107397983259866484167, 506660924932346216388835, 50675683529411401757497171, 5104747391125384906330663869

Offset: 0

Lee A. Newberg, Dec 11 2009

a(n) is also the number of standard sequence alignments of four 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 some string x is in the same column as some j-th position of some string y.

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

See A171155 and A171158 for the number of such walks in two dimensions and in three dimensions.

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

cp's OEIS Frontend

A047080 Triangular array T read by rows: T(h,k)=number of paths from (0,0) to (k,h-k) using step-vectors (0,1), (1,0), (1,1) with no right angles between pairs of consecutive steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A047085 a(n) = T(2*n, n), array T as in A047080.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

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

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

A171158 The number of walks from (0,0,0) to (n,n,n) with steps that increment one to three coordinates and having the property that no two consecutive steps are orthogonal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A171563 The number of walks from (0,0,0,0) to (n,n,n,n) with steps that increment one to four coordinates and having the property that no two consecutive steps are orthogonal.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions