A144079 -id:A144079 - cp's OEIS frontend

A144097 The 4-Schroeder numbers: a(n) = number of lattice paths (Schroeder paths) from (0,0) to (3n,n) with unit steps N=(0,1), E=(1,0) and D=(1,1) staying weakly above the line y = 3x.

1, 2, 14, 134, 1482, 17818, 226214, 2984206, 40503890, 561957362, 7934063678, 113622696470, 1646501710362, 24098174350986, 355715715691350, 5289547733908510, 79163575684710818, 1191491384838325474

Offset: 0

Joachim Schroeder (schroderjd(AT)qwa.uovs.ac.za), Sep 10 2008

a(n) is also the number of lattice path from (0,0) to (4n,0) with unit steps (1,3), (2,2) and (1,-1) staying weakly above the x-axis.
Also, the number of planar rooted trees with n non-leaf vertices such that each non-leaf vertex has either 3 or 4 children. - Cameron Marcott, Sep 18 2013
a(n) equals the number of ordered complete 4-ary trees with 3*n + 1 leaves, where the internal vertices come in two colors and such that each vertex and its rightmost child have different colors. See Drake, Example 1.6.9. - Peter Bala, Apr 30 2023

			a(2)=14, because
  01: NNNENNNE,
  02: NNDNNNE,
  03: NNNENND,
  04: NNDNND,
  05: NNNDNNE,
  06: NNNDND,
  07: NNNNENNE,
  08: NNNNEND,
  09: NNNNDNE,
  10: NNNNDD,
  11: NNNNNENE,
  12: NNNNNED,
  13: NNNNNDE,
  14: NNNNNNEE
are all the paths from (0,0) to (2,6) with steps N,E and D weakly above y=3x.

Sheng-Liang Yang and Mei-yang Jiang, The m-Schröder paths and m-Schröder numbers, Disc. Math. (2021) Vol. 344, Issue 2, 112209. doi:10.1016/j.disc.2020.112209. See Table 1.

Alois P. Heinz, Table of n, a(n) for n = 0..800
D. Bevan, D. Levin, P. Nugent, J. Pantone, and L. Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510.08036 [math.CO], 2015.
B. Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.6.9), A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
Gi-Sang Cheon, S.-T. Jin, and L. W. Shapiro, A combinatorial equivalence relation for formal power series, Linear Algebra and its Applications, Available online 30 March 2015.
J. Schroeder, Generalized Schroeder numbers and the rotation principle, Journal of Integer Sequences 10(7).
R. A. Sulanke, A recurrence restricted by a diagonal condition: generalized Catalan arrays, Fibonacci Q., 27 (1989), 33-46.
Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See p. 11.
Lin Yang, Yu-Yuan Zhang, and Sheng-Liang Yang, The halves of Delannoy matrix and Chung-Feller properties of the m-Schröder paths, Linear Alg. Appl. (2024).
Sheng-liang Yang and Mei-yang Jiang, Pattern avoiding problems on the hybrid d-trees, J. Lanzhou Univ. Tech., (China, 2023) Vol. 49, No. 2, 144-150. (in Mandarin; improperly cited as A144079)

Cf. A027307 (the case y=2x), A008288 (Delannoy numbers), A008412 (4-dimensional coordination numbers).
This appears to equal 2*A243675. - N. J. A. Sloane, Mar 28 2021
The sequences listed in Yang-Jiang's Table 1 appear to be A006318, A001003, A027307, A034015, A144097, A243675, A260332, A243676. - N. J. A. Sloane, Mar 28 2021

Schr:=proc(n,m,l)(n-l*m+1)/m*sum(2^v*binomial(m,v)*binomial(n,v-1),v=1..m) end proc; where n=3m and l=3, also
Schr:=proc(n,m,l)(n-l*m+1)/(n+1)*sum(2^v*binomial(m-1,v-1)*binomial(n+1,v),v=0..m) end proc; where n=3m and l=3, also
Schr:=proc(n,m,l)(n-l*m+1)/m*sum(binomial(m,v)*binomial(n+v,m-1),v=0..m) end proc; where n=3m and l=3, also
Schr:=proc(n,m,l)(n-l*m+1)/(n+1)*sum(binomial(n+1,v)*binomial(m-1+v,n),v=0..n+1) end proc; where n=3m and l=3.
# alternative Maple program:
a:= proc(n) option remember; `if`(n<2, n+1,
      ((15610*n^5 -67123*n^4 +106824*n^3 -77633*n^2
       +25514*n-3000)*a(n-1) -(3*(n-2))*(3*n-4)*
       (3*n-5)*(35*n^2-28*n+5)*a(n-2)) / ((3*(3*n-1))
       *(3*n+1)*n*(35*n^2-98*n+68)))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, May 26 2015

d[n_, k_] := Binomial[n+k, k] Hypergeometric2F1[-k, -n, -n-k, -1]; a[0] = 1; a[n_] = d[3n, n] - 3d[3n+1, n-1] - 2d[3n, n-1]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 25 2017 *)

{a(n) = sum(k=0, n, binomial(n, k) * binomial(3*n+k+1, n)/(3*n+k+1))} \\ Seiichi Manyama, Jul 25 2020

{a(n) = if(n==0, 1, sum(k=1, n, 2^k*binomial(n, k) * binomial(3*n, k-1)/n))} \\ Seiichi Manyama, Jul 25 2020

G.f. A(z) satisfies A(z) = 1 + z(A(z)^3 + A(z)^4) a(n)= S_{3n+1}(n) - 3S_n(3n + 1), where S_a(b) are coordination numbers, i.e., the number of points in the a-dimensional cubic lattice Z^a having distance b in the L_1 norm.
Also a(n) = D(3n,n) - 3D(3n + 1,n-1) - 2D(3n,n-1), where D(a,b) are the Delannoy numbers, i.e., the number of paths with N, E and D steps from (0,0) to (a,b).
D-finite with recurrence 3*n*(3*n-1)*(3*n+1)*(35*n^2-98*n+68) *a(n) +(-15610*n^5+67123*n^4-106824*n^3+77633*n^2-25514*n+3000)*a(n-1) +3*(n-2) *(3*n-4) *(3*n-5) *(35*n^2-28*n+5) *a(n-2)=0. - R. J. Mathar, Sep 06 2016
From Seiichi Manyama, Jul 25 2020: (Start)
a(n) = Sum_{k=0..n} binomial(n,k) * binomial(3*n+k+1, n)/(3*n+k+1).
a(n) = (1/n) * Sum_{k=1..n} 2^k * binomial(n,k) * binomial(3*n,k-1) for n > 0. (End)
a(n) ~ sqrt(12160 + 3853*sqrt(10)) * 3^(3*n - 9/2) / (2*sqrt(5*Pi) * n^(3/2) * (223 - 70*sqrt(10))^(n - 1/2)). - Vaclav Kotesovec, Jul 31 2021
Series reversion of x*(1 - x^3)/(1 + x^3) = x + 2*x^4 + 14*x^7 + 134*x^10 + ... = Sum_{n >= 0} a(n)*x^(3*n+1). - Peter Bala, Apr 30 2023
From Peter Bala, Jun 16 2023: (Start)
The g.f. A(x) = 1 + 2*x + 14*x^2 + 134*x^3 + ... satisfies A(x)^3 = (1/x) * the series reversion of ((1 - x)/(1 + x))^3.
Define b(n) = [x^(3*n)] ( (1 + x)/(1 - x) )^n = (1/3) * [x^n] ((1 + x)/(1 - x))^(3*n) = A333715(n). Then A(x) = exp( Sum_{n >= 1} b(n)*x^n/n ).
a(n) = 2*hypergeom([1 - n, -3*n], [2], 2) for n >= 1. (End)
a(n) = (1/n) * Sum_{k=0..n-1} (-1)^k * 2^(n-k) * binomial(n,k) * binomial(4*n-k,n-1-k) for n > 0. - Seiichi Manyama, Aug 09 2023

A144078 a(n) = the number of digits in the binary representation of n that differ from the corresponding digit in the binary reversal of n. (I.e., a(n) = number of 1's in n XOR A030101(n).)

Original entry on oeis.org

0, 2, 0, 2, 0, 2, 0, 2, 0, 4, 2, 4, 2, 2, 0, 2, 0, 4, 2, 2, 0, 4, 2, 4, 2, 2, 0, 4, 2, 2, 0, 2, 0, 4, 2, 4, 2, 6, 4, 4, 2, 6, 4, 2, 0, 4, 2, 4, 2, 2, 0, 6, 4, 4, 2, 6, 4, 4, 2, 4, 2, 2, 0, 2, 0, 4, 2, 4, 2, 6, 4, 2, 0, 4, 2, 4, 2, 6, 4, 4, 2, 6, 4, 2, 0, 4, 2, 4, 2, 6, 4, 2, 0, 4, 2, 4, 2, 2, 0, 6, 4, 4, 2, 4, 2

Offset: 1

Leroy Quet, Sep 09 2008

a(n) + A144079(n) = A070939(n), the number of binary digits in n.

			20 in binary is 10100. Compare this with its digit reversal, 00101. XOR each pair of corresponding digits: 1 XOR 0 = 1, 0 XOR 0 = 0, 1 XOR 1 = 0, 0 XOR 0 = 0, 0 XOR 1 = 1. There are two bit pairs that differ, so a(20) = 2.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A006995, A030101, A143960, A144079.

A144078 := proc(n) local a,dgs,i; a := 0 ; dgs := convert(n,base,2) ; for i from 1 to nops(dgs) do if op(i,dgs)+op(-i,dgs) = 1 then a := a+1 ; fi; od; RETURN(a) ; end: for n from 1 to 240 do printf("%d,",A144078(n)) ; od: # R. J. Mathar, Sep 14 2008

brd[n_]:=Module[{idn2=IntegerDigits[n,2]},Count[Transpose[{idn2, Reverse[ idn2]}], ?(#[[1]]!=#[[2]]&)]]; Array[brd,110] (* _Harvey P. Dale, May 09 2016 *)

a(n) = hammingweight(bitxor(n, fromdigits(Vecrev(binary(n)),2))) \\ Rémy Sigrist, Oct 07 2018

From Rémy Sigrist, Oct 07 2018: (Start)
a(n) = 0 iff n is a binary palindrome (A006995).
a(A143960(n)) = 2*n (in fact A143960(n) is the least k such that a(k) = 2*n).
(End)

More terms from R. J. Mathar, Sep 14 2008

cp's OEIS Frontend

A144097 The 4-Schroeder numbers: a(n) = number of lattice paths (Schroeder paths) from (0,0) to (3n,n) with unit steps N=(0,1), E=(1,0) and D=(1,1) staying weakly above the line y = 3x.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A144078 a(n) = the number of digits in the binary representation of n that differ from the corresponding digit in the binary reversal of n. (I.e., a(n) = number of 1's in n XOR A030101(n).)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions