A027261 -id:A027261 - cp's OEIS frontend

A334778 Triangle read by rows: T(n,k) is the number of permutations of 2 indistinguishable copies of 1..n arranged in a circle with exactly k local maxima.

1, 0, 1, 0, 4, 2, 0, 18, 66, 6, 0, 72, 1168, 1192, 88, 0, 270, 16220, 61830, 33600, 1480, 0, 972, 202416, 2150688, 3821760, 1268292, 40272, 0, 3402, 2395540, 62178928, 272509552, 279561086, 62954948, 1476944, 0, 11664, 27517568, 1629254640, 15313310208, 36381368048, 24342647424, 3963672720, 71865728

Offset: 0

Andrew Howroyd, May 13 2020

T(n,k) is divisible by n for n > 0.

			Triangle begins:
   1;
   0,    1;
   0,    4,       2;
   0,   18,      66,        6;
   0,   72,    1168,     1192,        88;
   0,  270,   16220,    61830,     33600,      1480;
   0,  972,  202416,  2150688,   3821760,   1268292,    40272;
   0, 3402, 2395540, 62178928, 272509552, 279561086, 62954948, 1476944;
  ...
The T(2,1) = 4 permutations of 1122 with 1 local maximum are 1122, 1221, 2112, 2211.
The T(2,2) = 2 permutations of 1122 with 2 local maxima are 1212, 2121.

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Columns k=0..6 are A000007, A027261(n-1), A159716, A159717, A159718, A159719, A159720.
Row sums are A000680.
Main diagonal is A334779.
The version for permutations of 1..n is A263789.
Cf. A334218, A334774, A334780.

CircPeaksBySig(sig, D)={
  my(F(lev,p,q) = my(key=[lev,p,q], z); if(!mapisdefined(FC, key, &z),
    my(m=sig[lev]); z = if(lev==1, if(p==0, binomial(m-1, q), 0), sum(i=0, p, sum(j=0, min(m-i, q), self()(lev-1, p-i, q-j+i) * binomial(m+2*(q-j)+1, 2*q+i-j+1) * binomial(q-j+i, i) * binomial(q+1, j) )));
    mapput(FC, key, z)); z);
  local(FC=Map());
  vector(#D, i, my(k=D[i], lev=#sig); if(lev==1, k==1, my(m=sig[lev]); lev*sum(j=1, min(m,k), m*binomial(m-1,j-1)*F(lev-1,k-j,j-1)/j)));
}
Row(n)={ if(n==0, [1], CircPeaksBySig(vector(n,i,2), [0..n])) }
{ for(n=0, 8, print(Row(n))) }

T(n,k) = n*(2*F(2,n-1,k-1,0) + F(2,n-1,k-2,1)) for n > 1 where F(m,n,p,q) = Sum_{i=0..p} Sum_{j=0..min(m-i, q)} F(m, n-1, p-i, q-j+i) * binomial(m+2*(q-j)+1, 2*q+i-j+1) * binomial(q-j+i, i) * binomial(q+1, j) for n > 1 with F(m,1,0,q) = binomial(m-1, q), F(m,1,p,q) = 0 for p > 0.

A334780(n) = Sum_{k=1..n} k*T(n,k).

A014915 a(1)=1, a(n) = n*3^(n-1) + a(n-1).

Original entry on oeis.org

1, 7, 34, 142, 547, 2005, 7108, 24604, 83653, 280483, 930022, 3055786, 9964519, 32285041, 104029576, 333612088, 1065406345, 3389929279, 10750918570, 33996147910, 107218620331, 337346390797, 1059110761804, 3318547053652, 10379285465677, 32408789311195, 101039166676078

Offset: 1

Olivier Gérard

Vincenzo Librandi, Table of n, a(n) for n = 1..600
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 14.
Alexander V. Kitaev, Meromorphic Solution of the Degenerate Third Painlevé Equation Vanishing at the Origin, arXiv:1809.00122 [math.CA], 2018.
Index entries for linear recurrences with constant coefficients, signature (7,-15,9).

Cf. A027261, A027471, A059045, A064017, A079272.

[((2*n - 1)*3^n + 1)/4: n in [1..30]]; // Vincenzo Librandi, Jun 09 2011

LinearRecurrence[{7, -15, 9}, {1, 7, 34}, 25] (* L. Edson Jeffery, May 08 2015 *)

From Henry Bottomley, Dec 18 2000: (Start)
a(n) = ((2*n-1)*3^n + 1)/4.
a(n) = 7*a(n-1) - 15*a(n-2) + 9*a(n-3) for n > 3.
a(n) = 1 + 2*3 + 3*3^2 + .. + n*3^(n-1).
a(n) = a(n-1) + A027471(n+1). (End)
G.f.: x/((1-x)*(1-3*x)^2). - Colin Barker, Jul 28 2012
a(n) = f^n(n)/2 with f(x) = 3*x-1. - Glen Gilchrist, Apr 10 2019
E.g.f.: exp(x)*(1 + exp(2*x)*(6*x - 1))/4. - Stefano Spezia, May 14 2024
a(n) = 6*a(n-1) - 9*a(n-2) + 1 for n > 2. - Elmo R. Oliveira, May 24 2025

A064017 Number of ternary trees (A001764) with n nodes and maximal diameter.

Original entry on oeis.org

1, 3, 12, 45, 162, 567, 1944, 6561, 21870, 72171, 236196, 767637, 2480058, 7971615, 25509168, 81310473, 258280326, 817887699, 2582803260, 8135830269, 25569752274, 80196041223, 251048476872, 784526490225, 2447722649502

Offset: 1

Danail Bonchev (bonchevd(AT)aol.com), Sep 07 2001

A problem important for polymer science because it counts the trees having unbranched branches; they are called "combs".
Equals (1, 3, 9, 27, 81, ...) convolved with (1, 0, 3, 9, 27, 81, ...). Example: a(5) = 162 = (81, 27, 9, 3, 1) dot (1, 0, 3, 9, 27) = 81 + 3*27. - Gary W. Adamson, Jul 31 2010
Floretion Algebra Multiplication Program, FAMP Code: lesforseq[ - 'i + 'j - 'kk' - 'ki' - 'kj' ], vesforseq(n) = 3^n, tesforseq = A006234

			a(5) = 162 because we can write (5+1)*3^(5-2) = 6*3^3 = 6*27.

Harry J. Smith, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (6,-9).

Cf. A001764, A006234, A014915, A025192, A027261, A079272, A196389.

a:=n->ceil(sum(3^(n-2),j=0..n)): seq(a(n), n=1..26); # Zerinvary Lajos, Jun 05 2008

Join[{1},Table[(n+1)3^(n-2),{n,2,30}]] (* or *) Join[{1}, LinearRecurrence[ {6,-9},{3,12},30]] (* Harvey P. Dale, Feb 07 2012 *)

{ for (n=1, 200, if (n>1, a=(n + 1)*p; p*=3, a=p=1); write("b064017.txt", n, " ", a) ) } \\ Harry J. Smith, Sep 06 2009

a(n)=if(n==1, 1, (n+1)*3^(n-2)); \\ Joerg Arndt, May 06 2013

@CachedFunction
def BB(n, k, x):  # modified cardinal B-splines
    if n == 1: return 0 if (x < 0) or (x >= k) else 1
    return x*BB(n-1, k, x) + (n*k-x)*BB(n-1, k, x-k)
def EulerianPolynomial(n, k, x):
    if n == 0: return 1
    return add(BB(n+1, k, k*m+1)*x^m for m in (0..n))
def A064017(n) : return 3^(n-1)*EulerianPolynomial(1,n-1,1/3) if n != 1 else 1
[A064017(n) for n in (1..25)]  # Peter Luschny, May 04 2013

a(n) = 3*a(n-1) + 3^(n-2).
a(n) = (n+1)*3^(n-2), for n > 1.
From Paul Barry, Sep 05 2003: (Start)
a(n) = (n+2)3^(n-1) + 0^n/3 (offset 0).
a(n) = A025192(n) + A027471(n). (End)
A006234(n+4) - a(n+2) = 3^n. - Creighton Dement, Mar 01 2005
a(n+1) = Sum_{k=0..n} A196389(n,k)*3^k. - Philippe Deléham, Oct 31 2011
G.f.: (1 - 3*x + 3*x^2)*x/(1 - 3*x)^2. - Philippe Deléham, Oct 31 2011
a(n) = 6*a(n-1) - 9*a(n-2), with a(1)=1, a(2)=3, a(3)=12. - Harvey P. Dale, Feb 07 2012
E.g.f.: (exp(3*x)*(1 + 3*x) - 1)/9. - Stefano Spezia, Mar 05 2020
From Amiram Eldar, Jan 18 2021: (Start)
Sum_{n>=1} 1/a(n) = 27*log(3/2) - 19/2.
Sum_{n>=1} (-1)^(n+1)/a(n) = 17/2 - 27*log(4/3). (End)

A159715 Number of permutations of 2 indistinguishable copies of 1..n arranged in a circle with exactly 1 local maximum.

Original entry on oeis.org

4, 18, 72, 270, 972, 3402, 11664, 39366, 131220, 433026, 1417176, 4605822, 14880348, 47829690, 153055008, 487862838, 1549681956, 4907326194, 15496819560, 48814981614, 153418513644, 481176247338, 1506290861232, 4707158941350

Offset: 2

R. H. Hardin, Apr 20 2009

nonn

R. H. Hardin, Table of n, a(n) for n = 2..100
Index entries for linear recurrences with constant coefficients, signature (6,-9).

Cf. A027261, A159721, A159727, A159733, A159736, A159738, A159739, A159740.

[2*n*3^(n-2): n in [2..30]]; // G. C. Greubel, Jun 01 2018

LinearRecurrence[{6,-9}, {}, 30] (* or *) Table[2*n*3^(n-2), {n, 2, 30}] (* G. C. Greubel, Jun 01 2018 *)

for(n=2, 30, print1(2*n*3^(n-2), ", ")) \\ G. C. Greubel, Jun 01 2018

a(n) = (copies*n)*(copies+1)^(n-2), here: copies = 2.
Apparently a(n) = A027261(n-1), n > 2. - R. J. Mathar, Apr 21 2009
Conjectures from Colin Barker, Mar 23 2018: (Start)
G.f.: 2*x^2*(2 - 3*x) / (1 - 3*x)^2.
a(n) = 2*3^(n-2)*n for n>1.
a(n) = 6*a(n-1) - 9*a(n-2) for n>3. (End)
E.g.f.: 2*x*exp(3*x)/3. - G. C. Greubel, Jun 01 2018
From Amiram Eldar, May 16 2022: (Start)
Sum_{n>=2} 1/a(n) = (9/2)*log(3/2) - 3/2.
Sum_{n>=2} (-1)^n/a(n) = 3/2 - (9/2)*log(4/3). (End)

A079272 a(n) = ((2n+1)*3^n - 1)/2.

Original entry on oeis.org

4, 22, 94, 364, 1336, 4738, 16402, 55768, 186988, 620014, 2037190, 6643012, 21523360, 69353050, 222408058, 710270896, 2259952852, 7167279046, 22664098606, 71479080220, 224897593864, 706073841202, 2212364702434, 6919523643784, 21605859540796, 67359444450718

Offset: 1

Lekraj Beedassy, Feb 06 2003

Sequence corresponds to the maximum chain length of a variant of the classical puzzle whereby, under agreed terms, a ringed golden chain asset of a(n) links, when judiciously fragmented into n opened links (through n cuts) and n pieces of lengths (2n+1), (2n+1)*3, (2n+1)*3^2, ..., (2n+1)*3^(n-1), may be used to sequentially settle for payment equivalent up to a(n)-link cost, a link-cost at a time, with swapping allowed with identical fragments owned by the creditor.

a(n) = the difference of the sum of the terms in row(n) and row(n-1) in a triangle with first column T(n-1,0) = n-1 and T(i,j) = T(i-1,j-1) + T(i,j-1) + T(i+1,j-1). - J. M. Bergot, Jul 05 2018

			For instance, the 4 fragmented chains of original length a(4) = 364 into
.
   1 +  9  + 1
   +         +
  243       27
   +         +
   1 +  81 + 1
.
when swapped with identical fragments owned by the creditor, enable the sequential payment, a link-cost at a time, for an expense up to 364 link-costs.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (7,-15,9).

Cf. A014915, A016777, A027261, A064017.

[((2*n+1)*3^n - 1)/2: n in [1..25]]; // Vincenzo Librandi, Jul 07 2018

a:=n->sum (3^j*n^binomial(j,n),j=0..n): seq(a(n),n=1..25); # Zerinvary Lajos, Apr 18 2009

Rest@ CoefficientList[Series[2x(2-3x)/((1-x)(1-3x)^2), {x, 0, 25}], x] (* Michael De Vlieger, Jul 06 2018 *)

vector(25, n, ((2*n+1)*3^n - 1)/2) \\ G. C. Greubel, Apr 14 2019

[((2*n+1)*3^n - 1)/2 for n in (1..25)] # G. C. Greubel, Apr 14 2019

From Colin Barker, Jul 28 2012: (Start)
a(n) = 7*a(n-1) - 15*a(n-2) + 9*a(n-3).
G.f.: 2*x*(2-3*x)/((1-x)*(1-3*x)^2). (End)
a(n) = f^n(n) with f(x) = 3*x+1 = A016777(x). - Glen Gilchrist, Apr 10 2019
E.g.f.: ((1+3*x)*sinh(x) + 3*x*cosh(x))*exp(2*x). - G. C. Greubel, Apr 14 2019

More terms from Michel ten Voorde, Jun 20 2003

cp's OEIS Frontend

A334778 Triangle read by rows: T(n,k) is the number of permutations of 2 indistinguishable copies of 1..n arranged in a circle with exactly k local maxima.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A014915 a(1)=1, a(n) = n*3^(n-1) + a(n-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A064017 Number of ternary trees (A001764) with n nodes and maximal diameter.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

SageMath

Formula

A159715 Number of permutations of 2 indistinguishable copies of 1..n arranged in a circle with exactly 1 local maximum.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A079272 a(n) = ((2n+1)*3^n - 1)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions