A082161 -id:A082161 - cp's OEIS frontend

A288954 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except before the first and after the last branch node on level 0.

1, 1, 3, 13, 79, 555, 4605, 42315, 436275, 4894155, 60125625, 794437875, 11325612375, 172141044075, 2793834368325, 48009995908875, 874143494098875, 16757439016192875, 338309837281040625, 7157757510792763875, 158706419654857449375, 3673441093896736036875

Offset: 2

Michael Wallner, Jun 20 2017

nonn

A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. A branch node is a node with a left and right edge (no pointer). See the Genitrini et al. link. - Michael Wallner, Apr 20 2017

a(n) is the number of plane increasing trees with n+1 nodes where in the growth process induced by the labels a maximal young leaves and non-maximal young leaves alternate except for a sequence of maximal young leaves at the begininning and at the end. A young leaf is a leaf with no left sibling. A maximal young leaf is a young leaf with maximal label. See the Wallner link. - Michael Wallner, Apr 20 2017

			See A288950 and A288953.

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017.
Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017.

Cf. A288953 (variation without initial sequence).
Cf. A177145 (variation without initial and final sequence).
Cf. A001147 (relaxed compacted binary trees of right height at most one).
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
Cf. A000032, A000246, A001879, A051577, A213527, A288950, A288952 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
Cf. A000166, A000255, A000262, A052852, A123023, A130905, A176408, A201203 (variants of relaxed compacted binary trees of right height at most one, see the Wallner link).

terms = 22; egf = 1/(3(1-z))(1/Sqrt[1-z^2] + (3z^3 - z^2 - 2z + 2)/((1-z)(1-z^2))) + O[z]^terms;
CoefficientList[egf, z] Range[0, terms-1]! (* Jean-François Alcover, Dec 13 2018 *)

E.g.f.: 1/(3*(1-z))*( 1/sqrt(1-z^2) + (3*z^3-z^2-2*z+2)/((1-z)*(1-z^2)) ).

A103239 Column 0 of triangular matrix T = A103238, which satisfies: T^2 + T = SHIFTUP(T) where diagonal(T)={1,2,3,...}.

Original entry on oeis.org

1, 2, 8, 52, 480, 5816, 87936, 1601728, 34251520, 843099616, 23520367488, 734404134336, 25402332040704, 964965390917120, 39964015456707584, 1793140743838290432, 86691698782589288448, 4494521175128812273152

Offset: 0

Paul D. Hanna, Jan 31 2005

nonn

a(n-1) = number of initially connected acyclic unlabeled n-state automata on a 2-letter input alphabet for which only one state is affected identically by both input letters. This state is necessarily one that is carried to the sink (absorbing state). For example, with n=2, a(1)=2 counts 2333, 3233, but not 2233. Here 1 is the source and 3 is the sink and 2333 is short for {{1, 2}, {1, 3}, {2, 3}, {2, 3}} giving the action of the input letters. The unlabeled condition is captured by requiring that the first appearances of 2,3,...,n occur in that order. A082161 counts these automata without the affected-identically restriction. - David Callan, Jun 07 2006

			1 = (1-2x) + 2*x/(1-x)*(1-2x)(1-3x) + 8*x^2/(1-x)^2*(1-2x)(1-3x)(1-4x) +
52*x^3/(1-x)^3*(1-2x)(1-3x)(1-4x)(1-5x) + ...
+ a(n)*x^n/(1-x)^n*(1-2x)(1-3x)*..*(1-(n+2)x) + ...

Vaclav Kotesovec, Table of n, a(n) for n = 0..32

Cf. A103238.

{a(n)=if(n<0,0,if(n==0,1,polcoeff( 1-sum(k=0,n-1,a(k)*x^k/(1-x)^k*prod(j=0,k,1-(j+2)*x+x*O(x^n))),n)))}

G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1-x)^n*Product_{j=0..n} (1-(j+2)*x).

A102102 Column 0 of triangular matrix A102101, which shifts upward to exclude the main diagonal under matrix fourth power.

Original entry on oeis.org

1, 1, 15, 1000, 189035, 79278446, 63263422646, 86493299281972, 187766975052827491, 611024291011881918991, 2849262494779035461688236, 18362167739517547774072439880, 158759599858376078627687256207242

Offset: 0

Paul D. Hanna, Dec 29 2004

nonn

Analogous to A082161 and A082162, this describes the deterministic completely defined initially connected acyclic automata with 4 inputs and n transient unlabeled states (and a unique absorbing state) with a(0)=1.

Manosij Ghosh Dastidar and Michael Wallner, Asymptotics of relaxed k-ary trees, arXiv:2404.08415 [math.CO], 2024. See p. 1.4.

Cf. A102101, A082161, A082162.

{a(n)=local(A=matrix(1,1),B);A[1,1]=1; for(m=2,n+1,B=matrix(m,m);for(i=1,m, for(j=1,i, if(j==i,B[i,j]=j,if(j==1,B[i,j]=(A^4)[i-1,1], B[i,j]=(A^4)[i-1,j]));));A=B);return(A[n+1,1])}

A104416 Triangle, read by rows, where T(n,k) = A008275(k+1,n-k+1) are Stirling numbers of the first kind.

Original entry on oeis.org

1, -1, 1, 0, -3, 1, 0, 2, -6, 1, 0, 0, 11, -10, 1, 0, 0, -6, 35, -15, 1, 0, 0, 0, -50, 85, -21, 1, 0, 0, 0, 24, -225, 175, -28, 1, 0, 0, 0, 0, 274, -735, 322, -36, 1, 0, 0, 0, 0, -120, 1624, -1960, 546, -45, 1, 0, 0, 0, 0, 0, -1764, 6769, -4536, 870, -55, 1, 0, 0, 0, 0, 0, 720, -13132, 22449, -9450, 1320, -66, 1

Offset: 0

Paul D. Hanna, Mar 06 2005

The matrix inverse forms A104417, in which column 0 equals A082161.

			A(x,y) = (1-x) + x*y*(1-x)*(1-2*x) + x^2*y^2*(1-x)*(1-2*x)*(1-3*x) + x^3*y^3*(1-x)*(1-2*x)*(1-3*x)*(1-4*x) + ...
Rows begin:
  1;
  -1,1;
  0,-3,1;
  0,2,-6,1;
  0,0,11,-10,1;
  0,0,-6,35,-15,1;
  0,0,0,-50,85,-21,1;
  0,0,0,24,-225,175,-28,1;
  0,0,0,0,274,-735,322,-36,1;
  0,0,0,0,-120,1624,-1960,546,-45,1;
  ...

Cf. A104417, A082161, A008275.

{T(n,k)=local(X=x+x*O(x^n),Y=y+y*O(y^k)); polcoeff(polcoeff(sum(i=0,n,X^i*Y^i*prod(j=1,i+1,1-j*X)),n,x),k,y)}

G.f.: A(x, y) = Sum_{n>=0} x^n*y^n*Product_{k=1..n+1} (1-k*x).

A104417 Triangle, read by rows, equal to the matrix inverse of A104416, where A104416(n,k) = A008275(k+1,n-k+1) (Stirling numbers of the first kind).

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 16, 16, 6, 1, 127, 127, 49, 10, 1, 1363, 1363, 531, 115, 15, 1, 18628, 18628, 7286, 1615, 230, 21, 1, 311250, 311250, 121964, 27321, 4040, 413, 28, 1, 6173791, 6173791, 2421471, 545311, 82131, 8841, 686, 36, 1, 142190703, 142190703

Offset: 0

Paul D. Hanna, Mar 06 2005

Column 0 and column 1 contain A082161.

			Column 0 forms A082161 that satisfies:
1 = (1-x) + 1*x*(1-x)(1-2x) + 3*x^2*(1-x)(1-2x)(1-3x) +
+ 16*x^3*(1-x)(1-2x)(1-3x)(1-4x) + ...
+ A082161(n+1)*x^n*(1-x)(1-2x)(1-3x)*..*(1-(n+1)*x) + ...
this g.f. can be derived from the matrix inverse, A104416.
Rows begin:
1;
1,1;
3,3,1;
16,16,6,1;
127,127,49,10,1;
1363,1363,531,115,15,1;
18628,18628,7286,1615,230,21,1;
311250,311250,121964,27321,4040,413,28,1; ...

Cf. A104416, A082161.

PARI

A106208 Triangular matrix T, read by rows, that satisfies: [T^-1](n,k) = -(k+1)*T(n-1,k) when (n-1)>=k>=0, with T(n,n) = 1 and T(n+1,n) = (n+1) for n>=0.

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 16, 10, 3, 1, 127, 78, 21, 4, 1, 1363, 832, 216, 36, 5, 1, 18628, 11342, 2901, 460, 55, 6, 1, 311250, 189286, 48081, 7456, 840, 78, 7, 1, 6173791, 3752320, 949800, 145660, 15955, 1386, 105, 8, 1, 142190703, 86392756, 21826470, 3327340

Offset: 0

Paul D. Hanna, May 01 2005

Column 0 is A082161 (offset 1). Column 1 is (1/2)*A102087. Row sums form A106209.

			Triangle T begins:
1;
1,1;
3,2,1;
16,10,3,1;
127,78,21,4,1;
1363,832,216,36,5,1;
18628,11342,2901,460,55,6,1;
311250,189286,48081,7456,840,78,7,1;
6173791,3752320,949800,145660,15955,1386,105,8,1; ...
Matrix inverse T^-1 begins:
1;
-1,1;
-1,-2,1;
-3,-4,-3,1;
-16,-20,-9,-4,1;
-127,-156,-63,-16,-5,1;
-1363,-1664,-648,-144,-25,-6,1;
-18628,-22684,-8703,-1840,-275,-36,-7,1; ...
where [T^-1](n,k) = -(k+1)*T(n-1,k) when (n-1)>=k>=0.
G.f. for column 0: 1 = 1(1-x) + 1*x*(1-x)(1-2x) +
3*x^2*(1-x)(1-2x)(1-3x) + ... +
T(n,0)*x^n*(1-x)(1-2x)(1-3x)*..*(1-(n+1)*x) + ...
G.f. for column 1: 1 = 1(1-2x) + 2*x*(1-2x)(1-3x) +
10*x^2*(1-2x)(1-3x)(1-4x) + ... +
T(n+1,1)*x^n*(1-2x)(1-3x)(1-4x)*..*(1-(n+2)*x) + ...
G.f. for column 2: 1 = 1(1-3x) + 3*x*(1-3x)(1-4x) +
21*x^2*(1-3x)(1-4x)(1-5x) + ... +
T(n+2,2)*x^n*(1-3x)(1-4x)(1-5x)*..*(1-(n+3)*x) + ...

Cf. A102086, A082161, A106209.

PARI
```
T(n,k)=if(n
				
```

T(n,k)=local(A=matrix(1,1),B);A[1,1]=1; for(m=2,n+1,B=matrix(m,m);for(i=1,m, for(j=1,i, if(j==i,B[i,j]=j,if(j==1,B[i,j]=(A^2)[i-1,1], B[i,j]=(A^2)[i-1,j]));));A=B);return(A[n+1,k+1]/(k+1))

T(n, k) = A102086(n, k)/(k+1) for n>=0, k>=0. T(n, 0) = A082161(n) for n>0, with T(0, 0) = 1. G.f. for column k: 1 = Sum_{n>=0} T(n+k, k)*x^n*prod_{j=1, n+1} (1-(j+k)*x).

A106210 Triangular matrix T, read by rows, that satisfies: [T^-1](n,k) = -k^2T(n-2,k) when (n-2)>=k>=0, with T(n,n) = 1 and T(n+1,n) = (2n+1) for n>=0.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 16, 16, 5, 1, 127, 127, 39, 7, 1, 1363, 1363, 416, 72, 9, 1, 18628, 18628, 5671, 967, 115, 11, 1, 311250, 311250, 94643, 16027, 1864, 168, 13, 1, 6173791, 6173791, 1876160, 316600, 36415, 3191, 231, 15, 1, 142190703, 142190703

Offset: 0

Paul D. Hanna, May 01 2005

Both column 0 and column 1 form A082161. Row sums form A106211.

			Triangle T begins:
1;
1,1;
3,3,1;
16,16,5,1;
127,127,39,7,1;
1363,1363,416,72,9,1;
18628,18628,5671,967,115,11,1;
311250,311250,94643,16027,1864,168,13,1;
6173791,6173791,1876160,316600,36415,3191,231,15,1; ...
Matrix inverse T^-1 begins:
1;
-1,1;
0,-3,1;
0,-1,-5,1;
0,-3,-4,-7,1;
0,-16,-20,-9,-9,1;
0,-127,-156,-63,-16,-11,1;
0,-1363,-1664,-648,-144,-25,-13,1;
0,-18628,-22684,-8703,-1840,-275,-36,-15,1; ...
where [T^-1](n,k) = -k^2*T(n-2,k) when (n-2)>=k>=0.
G.f. for column 0: 1/(1-0x) = 1*(1-1x) + 1*x*(1-1x)(1-2x) +
3*x^2*(1-1x)(1-2x)(1-3x) + 16*x^3*(1-1x)(1-2x)(1-3x)(1-4x) + ...
+ T(n,0)*x^n*(1-1x)(1-2x)*..*(1-(n+1)*x) + ...
G.f. for column 1: 1/(1-1x) = 1*(1-2x) + 3*x*(1-2x)(1-3x) +
16*x^2*(1-2x)(1-3x)(1-4x) + 127*x^3*(1-2x)(1-3x)(1-4x)(1-5x) + ...
+ T(n+1,1)*x^n*(1-2x)(1-3x)*..*(1-(n+2)*x) + ...
G.f. for column 2: 1/(1-2x) = 1*(1-3x) + 5*x*(1-3x)(1-4x) +
39*x^2*(1-3x)(1-4x)(1-5x) + 416*x^3*(1-3x)(1-4x)(1-5x)(1-6x) + ...
+ T(n+2,2)*x^n*(1-3x)(1-4x)*..*(1-(n+3)*x) + ...

Cf. A102086, A082161, A106211.

PARI
```
T(n,k)=if(n
				
```

T(n,k)=local(A=matrix(1,1),B);A[1,1]=1; for(m=2,n+2,B=matrix(m,m);for(i=1,m, for(j=1,i, if(j==i,B[i,j]=j,if(j==1,B[i,j]=(A^2)[i-1,1], B[i,j]=(A^2)[i-1,j]));));A=B); return(if(k==0,if(n==0,1,A[n+1,k+1]),A[n+1,k]/k^2))

T(n, k) = A102086(n, k)/(k+1) for n>=0, k>=0. T(n, 0) = A082161(n) for n>0, with T(0, 0) = 1. G.f. for column k: 1/(1-k*x) = Sum_{n>=0} T(n+k, k)*x^n*prod_{j=1, n+1} (1-(j+k)*x).

A128249 T(n,k) is the number of unlabeled acyclic single-source automata with n transient states on a (k+1)-letter input alphabet.

Original entry on oeis.org

1, 3, 1, 16, 7, 1, 127, 139, 15, 1, 1363, 5711, 1000, 31, 1, 18628, 408354, 189035, 6631, 63, 1, 311250, 45605881, 79278446, 5470431, 42196, 127, 1, 6173791, 7390305396, 63263422646, 12703473581, 147606627, 262459, 255, 1, 142190703, 1647470410551

Offset: 1

R. J. Mathar, May 09 2007

Table with rows n=1,2,... and columns k=1,2,3,... is read along antidiagonals.

David Callan, A determinant of Stirling Cycle Numbers Count Unlabeled Acyclic Single-Source Automata math.CO/0704.0004.
Manosij Ghosh Dastidar and Michael Wallner, Asymptotics of relaxed k-ary trees, arXiv:2404.08415 [math.CO], 2024. See p. 1.4.

Cf. A082162, A082161.

T := proc(n,k) local kn,A,i,j ; kn := k*n ; A := matrix(kn,kn) ; for i from 1 to kn do for j from 1 to kn do A[i,j] := abs(combinat[stirling1](floor((i-1)/k)+2,floor((i-1)/k)+1+i-j)) ; od ; od ; linalg[det](A) ; end: for d from 1 to 9 do for n from d to 1 by -1 do k := d+1-n ; printf("%d, ",T(n,k)) ; od ; od;

t[n_, k_] := Module[{kn, a, i, j}, kn = k*n; For[i = 1, i <= kn, i++, For[j = 1, j <= kn, j++, a[i, j] = Abs[StirlingS1[Floor[(i-1)/k]+2, Max[0, Floor[(i-1)/k]+1+i-j]]]]]; Det[Array[a, {kn, kn}]]]; Table[t[n-k, k], {n, 1, 10}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Jan 10 2014, translated from Maple *)

A187806 G.f.: 1/(1-x) = Sum_{n>=0} a(n)x^n Product_{k=1..n+1} (1-k*x).

Original entry on oeis.org

1, 2, 7, 39, 314, 3388, 46409, 776267, 15406059, 354928082, 9330754204, 276092552520, 9092298247070, 330151121828252, 13114259187006717, 566025800996830823, 26391137839213285415, 1322515573450223865750, 70912312814053387968103, 4052279260763983306587339

Offset: 0

Paul D. Hanna, Jan 06 2013

nonn

Compare to: 1 = Sum_{n>=0} A082161(n)*x^n * Product_{k=1..n+1} (1-k*x).

			1/(1-x) = (1-x) + 2*x*(1-x)*(1-2*x) + 7*x^2*(1-x)*(1-2*x)*(1-3*x) + 39*x^3*(1-x)*(1-2*x)*(1-3*x)*(1-4*x) + 314*x^4*(1-x)*(1-2*x)*(1-3*x)*(1-4*x)*(1-5*x) + 3388*x^5*(1-x)*(1-2*x)*(1-3*x)*(1-4*x)*(1-5*x)*(1-6*x) +...

Fedor Petrov, On a generating function and vector ν of length n, answer to question on MathOverflow (2024).

Cf. A082161, A118805.

{a(n)=if(n==0, 1, 1-polcoeff(sum(k=0, n-1, a(k)*x^k*prod(j=1, k+1, 1-j*x+x*O(x^n))), n))}
for(n=0,20,print1(a(n),", "))

upto(n) = my(v1); v1 = vector(n+1, i, 1); for(i=1, n, for(j=i+1, n+1, v1[j] += i*v1[j-1])); v1 \\ Mikhail Kurkov, Oct 25 2024

A209935 G.f.: 1 = Sum_{n>=0} a(n)x^nProduct_{k=1..n+1} (1-k^2*x) for n>0 with a(0)=1.

Original entry on oeis.org

1, 1, 5, 66, 1735, 77587, 5339632, 527780778, 71236904519, 12635518401687, 2857729962091681, 804340796768258860, 276170316701087964628, 113757566198465278521124, 55424247710747076665462268, 31554099393732823158673973698

Offset: 0

Paul D. Hanna, Mar 15 2012

nonn

			G.f.: 1 = 1*(1-x) + 1*x*(1-x)*(1-2^2*x) + 5*x^2*(1-x)*(1-2^2*x)*(1-3^2*x) + 66*x^3*(1-x)*(1-2^2*x)*(1-3^2*x)*(1-4^2*x) + 1735*x^4*(1-x)*(1-2^2*x)*(1-3^2*x)*(1-4^2*x)*(1-5^2*x) +...

Cf. A082161.

{a(n)=if(n==0, 1, polcoeff(1-sum(k=0, n-1, a(k)*x^k*prod(j=1, k+1, 1-j^2*x+x*O(x^n))), n))}
for(n=0,20,print1(a(n),", "))

cp's OEIS Frontend

A288954 Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except before the first and after the last branch node on level 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A103239 Column 0 of triangular matrix T = A103238, which satisfies: T^2 + T = SHIFTUP(T) where diagonal(T)={1,2,3,...}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A102102 Column 0 of triangular matrix A102101, which shifts upward to exclude the main diagonal under matrix fourth power.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A104416 Triangle, read by rows, where T(n,k) = A008275(k+1,n-k+1) are Stirling numbers of the first kind.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A104417 Triangle, read by rows, equal to the matrix inverse of A104416, where A104416(n,k) = A008275(k+1,n-k+1) (Stirling numbers of the first kind).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A106208 Triangular matrix T, read by rows, that satisfies: [T^-1](n,k) = -(k+1)*T(n-1,k) when (n-1)>=k>=0, with T(n,n) = 1 and T(n+1,n) = (n+1) for n>=0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

Formula

A106210 Triangular matrix T, read by rows, that satisfies: [T^-1](n,k) = -k^2*T(n-2,k) when (n-2)>=k>=0, with T(n,n) = 1 and T(n+1,n) = (2*n+1) for n>=0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

Formula

A128249 T(n,k) is the number of unlabeled acyclic single-source automata with n transient states on a (k+1)-letter input alphabet.

Views

Author

Keywords

Comments

Links

Crossrefs

A106210 Triangular matrix T, read by rows, that satisfies: [T^-1](n,k) = -k^2T(n-2,k) when (n-2)>=k>=0, with T(n,n) = 1 and T(n+1,n) = (2n+1) for n>=0.

A187806 G.f.: 1/(1-x) = Sum_{n>=0} a(n)x^n Product_{k=1..n+1} (1-k*x).

A209935 G.f.: 1 = Sum_{n>=0} a(n)x^nProduct_{k=1..n+1} (1-k^2*x) for n>0 with a(0)=1.