A298645 -id:A298645 - cp's OEIS frontend

A298646 a(n) is the sum of the degrees of asymmetry of all Dyck paths of semilength n.

0, 0, 4, 18, 88, 360, 1524, 6090, 24784, 98244, 393820, 1556324, 6196656, 24461424, 97079220, 383132250, 1518103840, 5992343940, 23726184372, 93686670220, 370840981680, 1464969055368, 5798679839524, 22917832613988, 90725318348448, 358737952183800

Offset: 1

Emeric Deutsch, Feb 21 2018

nonn

The degree of asymmetry of a Dyck path is defined in the following manner: we label the steps of a Dyck path of length 2n, from left to right, by 1,2,..., n-1, n, n, n-1, ..., 2,1. The degree of asymmetry is defined to be the number of pairs of identically labeled steps that are not at the same level. Example: the Dyck path uduudd has degree of asymmetry 2. Indeed, the labels are 123321 and the steps labeled 2 are at different levels and those labeled 3 are also at different levels.

All terms are even.

			a(3) = 4. Indeed, showing the step levels, the 5 = A000108(3) Dyck paths of semilength 3 are 111111, 122221, 123321, 111221, 122111. The first 3 are symmetric (degree of asymmetry 0) and each of the last 2 has degree of asymmetry 2.

Alois P. Heinz, Table of n, a(n) for n = 1..1664

Cf. A000108, A298645.

a:= proc(n) option remember; `if`(n<4, [0$3, 4][n+1], (
      2*(n-1)*(34328*n^3+1024539*n^2-2260739*n-3203910)*n*a(n-1)
      +24*(n-1)*(63276*n^4-396683*n^3+460919*n^2+544393*n-1067970)*
      a(n-2)-32*(34328*n^5+784243*n^4-7831140*n^3+24334466*n^2
      -31463717*n+15037140)*a(n-3)-128*(n-3)*(n-4)*(2*n-7)*(38875*n^2
      -225739*n+246552)*a(n-4))/((n+2)*(n+1)*n*(56039*n^2-121145*n-130144)))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Feb 21 2018

b[x_, y_, v_] := b[x, y, v] = Expand[If[Min[y, v, x - Max[y, v]] < 0, 0, If[x == 0, 1, Function[l, Sum[Sum[If[y == v + (j - i)/2, 1, z] b[x - 1, y + i, v + j], {i, l}], {j, l}]][{-1, 1}]]]];
g[n_] := g[n] = Sum[b[n, j, j], {j, 0, n}];
T[n_, k_] := Coefficient[g[n], z, k];
a[n_] := Sum[k T[n, k], {k, 0, n - 1}];
Array[a, 30] (* Jean-François Alcover, Dec 21 2020, after Alois P. Heinz in A298645 *)

a(n) = Sum_{k=0..n-1} k*A298645(n,k).
a(n) = (2*(n-1)*(34328*n^3 + 1024539*n^2 - 2260739*n - 3203910)*n*a(n-1) + 24*(n-1)*(63276*n^4 - 396683*n^3 + 460919*n^2 + 544393*n - 1067970)* a(n-2) - 32*(34328*n^5 + 784243*n^4 - 7831140*n^3 + 24334466*n^2 - 31463717*n + 15037140)*a(n-3) - 128*(n-3)*(n-4)*(2*n-7)*(38875*n^2 - 225739*n + 246552)*a(n-4))/((n+2)*(n+1)*n*(56039*n^2 - 121145*n - 130144)) for n>3, a(n) = 0 for n<3, a(3) = 4. - Alois P. Heinz, Feb 28 2018
a(n) ~ 4^n / sqrt(Pi*n) * (1 - 2/sqrt(Pi*n)). - Vaclav Kotesovec, Mar 06 2018

A298647 Number of Dyck paths of semilength n having maximal degree of asymmetry, namely n-1 for n>2 and 0 otherwise.

Original entry on oeis.org

1, 1, 2, 2, 2, 8, 16, 52, 134, 432, 1248, 4104, 12648, 42464, 136512, 466568, 1545566, 5361632, 18165184, 63804952, 219997832, 780895392, 2730730176, 9780049008, 34598622616, 124873507904, 446068180608, 1620786592416, 5837657948832, 21336295622016, 77395590570240

Offset: 0

Emeric Deutsch and Alois P. Heinz, Feb 21 2018

nonn

The degree of asymmetry of a Dyck path is defined in the following manner: we label the steps of a Dyck path of length 2n, from left to right, by 1,2,..., n-1, n, n, n-1, ..., 2,1. The degree of asymmetry is defined to be the number of pairs of identically labeled steps that are not at the same level. Example: the Dyck path UDUUDD has degree of asymmetry 2. Indeed, the labels are 123321 and the steps labeled 2 are at different levels and those labeled 3 are also at different levels.

			a(1) = 1, counting UD; a(2) = 2 since both UDUD and UUDD have maximal degree of asymmetry 0; a(5) = 8 counting UDUUUUDDDD, UDUDUUUDDD, UDUUDDUUDD, UDUDUUDUDD, and their reflections in a vertical axis.

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

Cf. A298645, A298646.

Column k=1 of A341445 (for n>2).

b:= proc(x, y, v) option remember; expand(
      `if`(min(y, v, x-max(y, v))<0, 0, `if`(x=0, 1, (l-> add(add(
      `if`(y=v+(j-i)/2, 1, z)*b(x-1, y+i, v+j), i=l), j=l))([-1, 1]))))
    end:
a:= n-> lcoeff(add(b(n, j$2), j=0..n)):
seq(a(n), n=0..40);
# second Maple program:
a:= proc(n) option remember; `if`(n<8, [1$2, 2$3, 8, 16, 52][n+1],
      (256*(n-4)*(n-5)*(n-8)*(147*n^5-1708*n^4+7165*n^3-12896*n^2+8882*n
      -1362)*a(n-6)-64*(294*n^7-6139*n^6+52088*n^5-227713*n^4+534530*n^3
      -630478*n^2+295718*n-24240)*a(n-5)-16*(3675*n^8-96943*n^7+1072857
      *n^6-6448749*n^5+22718880*n^4-46984656*n^3+53484228*n^2-28042052*n
      +3963360)*a(n-4)-24*(1470*n^7-30345*n^6+256611*n^5-1138707*n^4
      +2807363*n^3-3706740*n^2+2239444*n-369120)*a(n-3)+4*(n-2)*(1470
      *n^7-27958*n^6+211755*n^5-810763*n^4+1642737*n^3-1686751*n^2+790686
      *n-150480)*a(n-2)+2*(n-1)*(882*n^6-14357*n^5+89078*n^4-262023*n^3
      +370096*n^2-233344*n+64320)*a(n-1))/((147*n^5-2443*n^4+15467*n^3
      -46109*n^2+63736*n-32160)*(n-1)*n*(n+1)))
    end:
seq(a(n), n=0..40);

b[x_, y_, v_] := b[x, y, v] = Expand[
  If[Min[y, v, x - Max[y, v]]<0, 0, If[x==0, 1, Function[l, Sum[Sum[
  If[y == v+(j-i)/2, 1, z] b[x-1, y+i, v+j], {i, l}], {j, l}]][{-1, 1}]]]];
a[n_] := With[{p = Sum[b[n, j, j], {j, 0, n}]}, Coefficient[p, z, Exponent[p, z]]];
a /@ Range[0, 40] (* Jean-François Alcover, Dec 30 2020, after Alois P. Heinz *)

a(n) = A298645(n,n-1) for n > 2.

a(n) ~ 2^(2*n + 3) / (Pi * n^3). - Vaclav Kotesovec, Mar 06 2018

A300322 Number T(n,k) of Dyck paths of semilength n such that 2k is the difference between the area under the right half of the path and the area under the left half of the path; triangle T(n,k), n>=0, -floor(n(n-1)/6) <= k <= floor(n*(n-1)/6), read by rows.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 1, 3, 6, 3, 1, 2, 5, 8, 12, 8, 5, 2, 1, 4, 9, 16, 22, 28, 22, 16, 9, 4, 1, 1, 4, 11, 21, 34, 49, 60, 69, 60, 49, 34, 21, 11, 4, 1, 2, 7, 15, 31, 53, 82, 114, 147, 171, 186, 171, 147, 114, 82, 53, 31, 15, 7, 2, 1, 5, 13, 30, 56, 95, 150, 216, 293, 371, 445, 495, 522, 495, 445, 371, 293, 216, 150, 95, 56, 30, 13, 5, 1

Offset: 0

Alois P. Heinz, Mar 02 2018

			               /\
T(3,-1) = 1:  /  \/\
.
                /\
               /  \     /\/\
T(3,0) = 3:   /    \   /    \   /\/\/\
.
                 /\
T(3,1) = 1:   /\/  \
.
Triangle T(n,k) begins:
:                             1                            ;
:                             1                            ;
:                             2                            ;
:                         1,  3,  1                        ;
:                     1,  3,  6,  3,  1                    ;
:                 2,  5,  8, 12,  8,  5,  2                ;
:         1,  4,  9, 16, 22, 28, 22, 16,  9,  4,  1        ;
:  1, 4, 11, 21, 34, 49, 60, 69, 60, 49, 34, 21, 11, 4, 1  ;

Alois P. Heinz, Rows n = 0..60, flattened
Wikipedia, Counting lattice paths

Row sums give A000108.
Column k=0 gives A300323.
Cf. A130518, A129182, A177702, A239927, A298645, A300953.

b:= proc(x, y, v) option remember; expand(
     `if`(min(y, v, x-max(y, v))<0, 0, `if`(x=0, 1, (l-> add(add(
      b(x-1, y+i, v+j)*z^((y-v)/2+(i-j)/4), i=l), j=l))([-1, 1]))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=ldegree(p)..degree(p)))(
             add(b(n, (n-2*j)$2), j=0..n/2)):
seq(T(n), n=0..12);

b[x_, y_, v_] := b[x, y, v] = Expand[If[Min[y, v, x - Max[y, v]] < 0, 0, If[x == 0, 1, Function[l, Sum[Sum[b[x - 1, y + i, v + j] z^((y - v)/2 + (i - j)/4), {i, l}], {j, l}]][{-1, 1}]]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, Range[Exponent[p, z, Reverse @@ # &], Exponent[p, z]]}]][Sum[b[n, n-2j, n-2j], {j, 0, n/2}]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 31 2018, from Maple *)

T(n,k) = T(n,-k).

T(n,A130518(n)) = A177702(n).

A300323 Number of Dyck paths of semilength n such that the area under the right half of the path equals the area under the left half of the path.

Original entry on oeis.org

1, 1, 2, 3, 6, 12, 28, 69, 186, 522, 1536, 4638, 14408, 45568, 146884, 479871, 1589516, 5320854, 18000198, 61412376, 211282386, 731973720, 2553168136, 8957554412, 31604599044, 112060048354, 399227283950, 1428315878002, 5130964125124, 18499652813682

Offset: 0

Alois P. Heinz, Mar 02 2018

nonn

			              /\
             /  \      /\/\
a(3) = 3:   /    \    /    \    /\/\/\ .
.
a(5) = 12 counts A001405(5) = 10 symmetric plus 2 non-symmetric Dyck paths:
             /\  /\
          /\/  \/  \  and its reversal.

Alois P. Heinz, Table of n, a(n) for n = 0..300
Wikipedia, Counting lattice paths

Column k=0 of A300322.

Cf. A000108 (all Dyck paths), A000225, A001405 (symmetric Dyck paths), A129182, A239927, A298645.

b:= proc(x, y) option remember; expand(`if`(x=0, 1,
      `if`(y<1,   0, b(x-1, y-1)*z^(2*y-1))+
      `if`(x add(coeff(p, z, i)^2
      , i=0..degree(p)))(b(n, n-2*j)), j=0..n/2)
    end:
seq(a(n), n=0..32);

b[x_, y_] := b[x, y] = Expand[If[x == 0, 1, If[y < 1, 0, b[x - 1, y - 1] z^(2y - 1)] + If[x < y + 2, 0, b[x - 1, y + 1] z^(2y + 1)]]];
a[n_] := a[n] = Sum[Function[p, Sum[Coefficient[p, z, i]^2, {i, 0, Exponent[p, z]}]][b[n, n - 2j]], {j, 0, n/2}];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, May 31 2018, from Maple *)

a(n) >= A001405(n) with equality only for n <= 4.

a(n) is odd <=> n in { A000225 }.

A341445 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having degree of symmetry k (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 0, 2, 2, 0, 3, 2, 6, 0, 6, 8, 8, 16, 0, 10, 16, 32, 24, 40, 0, 20, 52, 84, 108, 60, 90, 0, 35, 134, 262, 294, 310, 150, 210, 0, 70, 432, 816, 1008, 880, 816, 336, 448, 0, 126, 1248, 2544, 3192, 3208, 2460, 2100, 784, 1008, 0, 252

Offset: 1

Sergi Elizalde, Feb 12 2021

The degree of symmetry of a Dyck path is defined as the number of steps in the first half that are mirror images of steps in the second half, with respect to the reflection along the vertical line through the midpoint of the path.

			For n=4 there are 6 Dyck paths with degree of symmetry equal to 2: uuuddudd, uuduuddd, uududdud, uuddudud, uduududd, ududuudd.
Triangle begins:
     1;
     0,    2;
     2,    0,    3;
     2,    6,    0,    6;
     8,    8,   16,    0,   10;
    16,   32,   24,   40,    0,   20;
    52,   84,  108,   60,   90,    0,  35;
   134,  262,  294,  310,  150,  210,   0,   70;
   432,  816, 1008,  880,  816,  336, 448,    0, 126;
  1248, 2544, 3192, 3208, 2460, 2100, 784, 1008,   0, 252;
  ...

Sergi Elizalde, The degree of symmetry of lattice paths, arXiv:2002.12874 [math.CO], 2020.
Sergi Elizalde, Measuring symmetry in lattice paths and partitions, Sem. Lothar. Combin. 84B.26, 12 pp (2020).

Equivalent to A298645 with rows reversed.
Row sums give A000108.
Main diagonal gives A001405.
Column k=1 gives A298647 (for n>2).
Second subdiagonal gives 2*A191522.

b:= proc(x, y, v) option remember; expand(
      `if`(min(y, v, x-max(y, v))<0, 0, `if`(x=0, 1, (l-> add(add(
      `if`(y=v+(j-i)/2, z, 1)*b(x-1, y+i, v+j), i=l), j=l))([-1, 1]))))
    end:
g:= proc(n) option remember; add(b(n, j$2), j=0..n) end:
T:= (n, k)-> coeff(g(n), z, k):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Feb 12 2021

b[x_, y_, v_] := b[x, y, v] = Expand[If[Min[y, v, x - Max[y, v]] < 0, 0, If[x == 0, 1, Function[l, Sum[Sum[If[y == v + (j - i)/2, z, 1]*b[x - 1, y + i, v + j], {i, l}], {j, l}]][{-1, 1}]]]];
g[n_] := g[n] = Sum[b[n, j, j], {j, 0, n}];
T[n_, k_] := Coefficient[g[n], z, k];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Feb 13 2021, after Alois P. Heinz *)

cp's OEIS Frontend

A298646 a(n) is the sum of the degrees of asymmetry of all Dyck paths of semilength n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A298647 Number of Dyck paths of semilength n having maximal degree of asymmetry, namely n-1 for n>2 and 0 otherwise.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A300322 Number T(n,k) of Dyck paths of semilength n such that 2*k is the difference between the area under the right half of the path and the area under the left half of the path; triangle T(n,k), n>=0, -floor(n*(n-1)/6) <= k <= floor(n*(n-1)/6), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A300323 Number of Dyck paths of semilength n such that the area under the right half of the path equals the area under the left half of the path.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A341445 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having degree of symmetry k (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A300322 Number T(n,k) of Dyck paths of semilength n such that 2k is the difference between the area under the right half of the path and the area under the left half of the path; triangle T(n,k), n>=0, -floor(n(n-1)/6) <= k <= floor(n*(n-1)/6), read by rows.