A129167 -id:A129167 - cp's OEIS frontend

A129165 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k base pyramids.

1, 0, 1, 1, 1, 1, 5, 2, 2, 1, 19, 9, 4, 3, 1, 73, 37, 15, 7, 4, 1, 292, 147, 63, 24, 11, 5, 1, 1203, 598, 258, 100, 37, 16, 6, 1, 5065, 2497, 1067, 419, 152, 55, 22, 7, 1, 21697, 10633, 4507, 1762, 647, 224, 79, 29, 8, 1, 94274, 45980, 19379, 7528, 2765, 964, 322

Offset: 0

Emeric Deutsch, Apr 04 2007

A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps. A pyramid in a skew Dyck word (path) is a factor of the form u^h d^h, h being the height of the pyramid. A base pyramid is a pyramid starting on the x-axis.

Row sums yield A002212.

			T(3,1)=2 because we have (UD)UUDL and (UUUDDD) (the base pyramids are shown between parentheses).
Triangle starts:
   1;
   0, 1;
   1, 1, 1;
   5, 2, 2, 1;
  19, 9, 4, 3, 1;

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203

Cf. A002212, A129166, A129167.

g:=(1-z-sqrt(1-6*z+5*z^2))/2/z: G:=(1-z)*(1-z+z*g)/(1-z*(1-z)*g-t*z): Gser:=simplify(series(G,z=0,15)): for n from 0 to 11 do P[n]:=sort(expand(coeff(Gser,z,n))) od: for n from 0 to 11 do seq(coeff(P[n],t,j),j=0..n) od; # yields sequence in triangular form

T(n,0) = A129166(n).
Sum_{k=0..n} k*T(n,k) = A129167(n).
G.f.: G(t,z) = (1-z)(1 - z + zg)/(1 - z(1-z)g - tz), where g = 1 + zg^2 + z(g-1) = (1 - z - sqrt(1 - 6z + 5z^2))(2z).

A246472 Number of order-preserving (monotone) functions from the power set of 1 = {0} to the power set of n = {0, ..., n-1}.

Original entry on oeis.org

1, 3, 9, 30, 109, 418, 1650, 6604, 26589, 107274, 432934, 1746484, 7040626, 28362324, 114175812, 459344920, 1847008989, 7423262554, 29822432862, 119766845860, 480833598054, 1929896415484, 7744047734652, 31067665113640, 124613703290994, 499744683756868

Offset: 0

Jesse Han, Aug 27 2014

nonn

This is the number of ways to choose a pair of elements (x,y) of P(n) so that x is a subset of y. This also gives the number of covariant functors from P(1) to P(n) viewed as categories.

Matches A129167 with offset 2 for the first four terms.

Sum[Binomial[#,i](1+ Sum[Binomial[#,j],{j,i+1,#}]),{i,0,#}]& /@ Range[0,20]

a(n) = sum(i=0, n, binomial(n,i)*(1+ sum(j = i+1, n, binomial(n,j)))); \\ Michel Marcus, Aug 27 2014

a(n) = Sum_{i=0..n} (binomial(n,i)*(1 + Sum_{j=i+1..n} binomial(n,j))).
a(n) = 2^(2*n-1) + 2^n - binomial(2*n, n)/2. - Vaclav Kotesovec, Aug 28 2014
n*(n-4)*a(n) +2*(-5*n^2+23*n-15)*a(n-1) +4*(8*n^2-41*n+45)*a(n-2) -16*(2*n-5)*(n-3)*a(n-3)=0. - R. J. Mathar, Jul 15 2017

cp's OEIS Frontend

A129165 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k base pyramids.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula