A088789 -id:A088789 - cp's OEIS frontend

A072034 a(n) = Sum_{k=0..n} binomial(n,k)*k^n.

1, 1, 6, 54, 680, 11000, 217392, 5076400, 136761984, 4175432064, 142469423360, 5372711277824, 221903307604992, 9961821300640768, 482982946946734080, 25150966159083264000, 1400031335107317628928, 82960293298087664648192

Offset: 0

Karol A. Penson, Jun 07 2002

nonn

The number of functions from {1,2,...,n} into a subset of {1,2,...,n} summed over all subsets. - Geoffrey Critzer, Sep 16 2012

Vincenzo Librandi, Table of n, a(n) for n = 0..200
V. Kotesovec, Interesting asymptotic formulas for binomial sums, Jun 09 2013

Cf. A088789, A242446, A256016, A336828, A341815.

seq(add(binomial(n,k)*k^n,k=0..n),n=0..17); # Peter Luschny, Jun 09 2015

Table[Sum[Binomial[n,k]k^n,{k,0,n}],{n,1,20}] (* Geoffrey Critzer, Sep 16 2012 *)

x='x+O('x^50); Vec(serlaplace(1/(1 + lambertw(-x*exp(x))))) \\ G. C. Greubel, Nov 10 2017

a(n) = sum(k=0, n, binomial(n,k)*k^n); \\ Michel Marcus, Nov 10 2017

E.g.f.: 1/(1+LambertW(-x*exp(x))). - Vladeta Jovovic, Mar 29 2008
a(n) ~ (n/(e*LambertW(1/e)))^n/sqrt(1+LambertW(1/e)). - Vaclav Kotesovec, Nov 26 2012
O.g.f.: Sum_{n>=0} n^n * x^n / (1 - n*x)^(n+1). - Paul D. Hanna, May 22 2018

Offset set to 0 and a(0) = 1 prepended by Peter Luschny, Jun 09 2015

E.g.f. edited to include a(0)=1 by Robert Israel, Jun 09 2015

A007889 Number of intransitive (or alternating, or Stanley) trees: vertices are [0,n] and for no i

Original entry on oeis.org

1, 1, 2, 7, 36, 246, 2104, 21652, 260720, 3598120, 56010096, 971055240, 18558391936, 387665694976, 8787898861568, 214868401724416, 5636819806209792, 157935254554567296, 4707152127520549120, 148704074888134683520, 4963548160096887021056, 174553183413968718996736

Offset: 0

Alexander Postnikov [ apost(AT)math.mit.edu ]

Number of local binary search trees (i.e. labeled binary trees such that every left child has a smaller label than its parent and every right child has a larger label than its parent) on n vertices. Example: a(3)=7 because we have 3L2L1, 2L1R3, 3L1R2, 1R2R3, 1R3L2, 2R3L1 (Li means left child labeled i, RI means right child labeled i) and root 2 with left child 1 and right child 3. - Emeric Deutsch, Nov 24 2004

Number of regions of the Linial arrangement. - Ira M. Gessel, Nov 01 2023

I. M. Gelfand, M. I. Graev and A. Postnikov, Combinatorics of hypergeometric functions associated with positive roots, in Arnold-Gelfand Mathematical Seminars: Geometry and Singularity Theory, Birkhäuser, 1997.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.41(a).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
C. Chauve, S. Dulucq and A. Rechnitzer, Enumerating alternating trees, J. Combin. Theory Ser. A 94 (2001), 142-151.
Sergey Fomin and Grigory Mikhalkin, Labeled floor diagrams for plane curves, arXiv:0906.3828, 2009-2010. [_N. J. A. Sloane_, Sep 27 2010]
G. Hetyei, Efron's coins and the Linial arrangement, arXiv preprint arXiv:1511.04482 [math.CO], 2015.
D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997 [Annotated scanned copy, with permission]
A. Postnikov, Intransitive Trees, J. Combin. Theory Ser. A 79 (1997), 360-366.
Richard P. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Natl. Acad. Sci. USA 93 (1996), 2620-2625.
Index entries for sequences related to trees

Cf. A038049, A138860, A283828, A323841.

Row sums of A029847.

f:= n->1/(2^n*(n+1))*add(binomial(n+1, k)*k^n, k=1..(n+1)): seq(f(n), n=0..19);

With[{nn=20},CoefficientList[Series[-2/x LambertW[-1/2x Exp[x/2]], {x,0,nn}], x]Range[0,nn]!] (* Harvey P. Dale, Aug 12 2011 *)
Table[1/((n+1)2^n) Sum[Binomial[n+1,k]k^n,{k,n+1}],{n,0,20}] (* Harvey P. Dale, Apr 21 2012 *)

{a(n)=local(A=1+x);for(i=0,n,A=exp(x*(1+A)/2 +x*O(x^n)));n!*polcoeff(A,n)} \\ Paul D. Hanna, Mar 29 2008

/* Coefficients of A(x)^p are given by: */ {a(n,p=1)=(1/2^n)*sum(k=0,n,binomial(n,k)*p*(k+p)^(n-1))} \\ Vladeta Jovovic and Paul D. Hanna, Apr 03 2008

def A007889(n) : return add(binomial(n,k)*(k+1)^(n-1) for k in (0..n))/2^n
for n in (0..19) : print(A007889(n)) # Peter Luschny, Feb 29 2012

a(n) = (1/((n+1)*2^n))*Sum_{k=1..n+1} C(n+1,k)*k^n.
E.g.f. A(x) satisfies: A(x) = exp( x*(1 + A(x))/2 ). E.g.f. A(x) equals the inverse function of 2*log(x)/(1+x). - Paul D. Hanna, Mar 29 2008
E.g.f.: -2/x*LambertW(-1/2*x*exp(1/2*x)). - Vladeta Jovovic, Mar 29 2008
From Vladeta Jovovic and Paul D. Hanna, Apr 03 2008: (Start)
Powers of e.g.f.: If A(x)^p = Sum_{n>=0} a(n,p)*x^n/n! then a(n,p) = (1/2^n)* Sum_{k=0..n} binomial(n,k)*p*(k+p)^(n-1).
Let A(x) = e.g.f. of A007889, B(x) = e.g.f. of A138860 where B(x) = exp( x*[B(x) + B(x)^2]/2 ); then B(x) = A(x*B(x)) = (1/x)*Series_Reversion(x/A(x)) and A(x) = B(x/A(x)) = x/Series_Reversion(x*B(x)). (End)
For n>=2, a(n)=Sum_{1,...,floor(n/2)}binomial(n-1, 2k-1)*k^(n-2). [Vladimir Shevelev, Mar 21 2010]
For n>0, a(n) = A088789(n+1)*2/(n+1). [Vaclav Kotesovec, Dec 26 2011]

A038049 Number of labeled rooted trees with 2-colored leaves.

Original entry on oeis.org

2, 4, 24, 224, 2880, 47232, 942592, 22171648, 600698880, 18422374400, 630897721344, 23864653578240, 988197253808128, 44460603225407488, 2159714024218951680, 112652924603290615808, 6280048587936003784704, 372616014329572403183616, 23445082059018189741752320

Offset: 1

Christian G. Bower, Jan 04 1999

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 185 (3.1.83)

Alois P. Heinz, Table of n, a(n) for n = 1..150
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A000169, A029856, A038050, A038054, A088789.

a:= n-> add(binomial(n, k)*(n-k)^(n-1), k=0..n):
seq(a(n), n=1..20);  # Alois P. Heinz, Nov 30 2012

Table[n!*Sum[2^j/j!*StirlingS2[n-1,n-j],{j,1,n}],{n,1,20}] (* Vaclav Kotesovec, Nov 30 2012 *)

Divides by n and shifts left under exponential transform.
E.g.f.: A(x) = x-LambertW(-x*exp(x)). - Vladeta Jovovic, Mar 08 2003
a(n) = Sum_{k=0..n} (binomial(n, k)*(n-k)^(n-1)).
A(x) = 2*compositional inverse of 2*x/(1+exp(2*x)). - Peter Bala, Oct 14 2011
a(n) ~ n^(n-1) * sqrt((1+LambertW(1/e))) / (e*LambertW(1/e))^n. - Vaclav Kotesovec, Nov 30 2012

A138860 E.g.f. satisfies: A(x) = exp( x*(A(x) + A(x)^2)/2 ).

Original entry on oeis.org

1, 1, 4, 31, 364, 5766, 115300, 2788724, 79197040, 2583928360, 95256535936, 3916137470664, 177651980724160, 8815348234689920, 474993826614917632, 27619367979975064576, 1723821221240101984000, 114948301218300412117632

Offset: 0

Paul D. Hanna, Apr 01 2008, Apr 02 2008, Apr 03 2008

nonn

The related sequence A007889 enumerates the number of intransitive (or alternating) trees.

a(n+1) is the number of incomplete ternary trees on n labeled vertices in which each left child has a larger label than its parent and each middle child has a smaller label than its parent. - Brian Drake, Jul 28 2008

			E.g.f.: A(x) = 1 + x + 4*x^2/2! + 31*x^3/3! + 364*x^4/4! + 5766*x^5/5! + ...

Seiichi Manyama, Table of n, a(n) for n = 0..363

Cf. A007889, A088789, A058014, A036778, A138903.

Cf. A138764.

Table[1/2^n * Sum[Binomial[n,k]*(n+k+1)^(n-1),{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, Jun 15 2013 *)

a(n)=(1/2^n)*sum(k=0,n,binomial(n,k)*(n+k+1)^(n-1))

/* Series Reversion: */
a(n)=local(X=x+x*O(x^n));n!*polcoeff(exp(serreverse(2*x/(exp(X)+exp(2*X)) )),n)

/* Coefficients of A(x)^p are given by: */
{a(n,p=1)=(1/2^n)*sum(k=0,n,binomial(n,k)*p*(n+k+p)^(n-1))}

a(n) = (1/2^n)* Sum_{k=0..n} binomial(n,k)*(n+k+1)^(n-1) - Vladeta Jovovic, Mar 31 2008.
E.g.f. satisfies: A( 2*x/( exp(x) + exp(2*x) ) ) = exp(x).
E.g.f.: A(x) = inverse function of 2*log(x)/(x + x^2).
E.g.f.: A(x) = exp( Series_Reversion[ 2*x/(exp(x) + exp(2*x)) ] ).
E.g.f.: A(x) = G(x/2) where G(x) = e.g.f. of A138764.
More generally, if A(x) = Sum_{n>=0} a(n)*x^n/n! = exp( x*[A(x) + A(x)^m]/2 ) then a(n) = (1/2^n)* Sum_{k=0..n} binomial(n,k)*(n+(m-1)*k+1)^(n-1) and if B(x) = Sum_{n>=0} b(n)*x^n/n! = log(A(x)) then b(n) = (1/2^n)* Sum_{k=0..n} binomial(n,k)*(n+(m-1)*k)^(n-1). - Paul D. Hanna and Vladeta Jovovic, Apr 02 2008
Powers of e.g.f.: If A(x)^p = Sum_{n>=0} a(n,p)*x^n/n! then
. a(n,p) = (1/2^n)* Sum_{k=0..n} binomial(n,k)*p*(n+k+p)^(n-1).
Given e.g.f. A(x), let B(x) = e.g.f. of A007889, then
. A(x) = B(x*A(x)) = (1/x)*Series_Reversion(x/B(x)) and
. B(x) = A(x/B(x)) = x/Series_Reversion(x*A(x)).
a(n) ~ n^(n-1)*(1+r)^n*r^(n+1)/(sqrt(1+3*r)*(1-r)^(2*n+1)*exp(n)*2^n), where r = 0.6472709258412625... is the root of the equation (r/(1-r))^(1+r) = e. - Vaclav Kotesovec, Jun 15 2013

A378561 Number of ways to place k nonattacking anassas on an n X n chess board. Triangle T(n,k) read by rows.

Original entry on oeis.org

1, 1, 1, 1, 4, 3, 1, 9, 22, 14, 1, 16, 82, 156, 90, 1, 25, 220, 840, 1366, 738, 1, 36, 485, 3100, 9796, 14288, 7364, 1, 49, 938, 9030, 46816, 129360, 174112, 86608, 1, 64, 1652, 22344, 172116, 767424, 1916776, 2424880, 1173240, 1, 81, 2712, 49056, 525756, 3442740, 13682320, 31572720, 38019496, 17990600

Offset: 0

Eder G. Santos, Nov 30 2024

Anassas (also called semi-rook+semi-bishop) are chess pieces with 2 moves: one horizontal or vertical and one diagonal.

			Triangle begins:
  1;
  1  1;
  1  4   3;
  1  9  22   14;
  1 16  82  156   90;
  1 25 220  840 1366   738;
  1 36 485 3100 9796 14288 7364;
  ...

S. Chaiken, C. R. H. Hanusa, and T. Zaslavsky, A q-Queens Problem. V. Some of Our Favorite Pieces: Queens, Bishops, Rooks, and Nightriders, J. Korean Math. Soc., 57(6): 1407-1433, 2020; see also arXiv preprint, arXiv:1609.00853 [math.CO], 2016-2020.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 716-722.
Eder G. Santos, Counting non-attacking chess pieces placements: Bishops and Anassas, arXiv:2411.16492 [math.CO], 2024.

Columns k=0-1 give: A000012, A000290.

Main diagonal gives A088789(n+1).

print([sum([factorial(j)*binomial(n-k+j,j)*stirling_number2(n,n-k+j)*2^(k-2*j)*(binomial(k-j,j-1)+binomial(k-j+1,j)) for j in [0..ceil(k/2)]]) for n in [0..10] for k in [0..n]])

T(n,k) = Sum_{j=0..ceiling(k/2)} j! * binomial(n-k+j,j) * Stirling2(n,n-k+j) * 2^(k-2*j) * (binomial(k-j,j-1) + binomial(k-j+1,j)).

cp's OEIS Frontend

A072034 a(n) = Sum_{k=0..n} binomial(n,k)*k^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A007889 Number of intransitive (or alternating, or Stanley) trees: vertices are [0,n] and for no i

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

A038049 Number of labeled rooted trees with 2-colored leaves.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A138860 E.g.f. satisfies: A(x) = exp( x*(A(x) + A(x)^2)/2 ).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A378561 Number of ways to place k nonattacking anassas on an n X n chess board. Triangle T(n,k) read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

Formula

A185056 Number of ways to place n nonattacking composite pieces bishop + semi-rook on an n X n board.

Views

Author

Keywords

Comments

Links

Crossrefs