A198204 -id:A198204 - cp's OEIS frontend

A058877 Number of labeled acyclic digraphs with n nodes containing exactly n-1 points of in-degree zero.

0, 2, 9, 28, 75, 186, 441, 1016, 2295, 5110, 11253, 24564, 53235, 114674, 245745, 524272, 1114095, 2359278, 4980717, 10485740, 22020075, 46137322, 96468969, 201326568, 419430375, 872415206, 1811939301, 3758096356, 7784628195, 16106127330, 33285996513

Offset: 1

N. J. A. Sloane, Jan 07 2001

Convolution of 2^n+1 (A000051) and 2^n-1 (A000225). - Graeme McRae, Jun 07 2006
Let Q be a binary relation on the power set P(A) of a set A having n = |A| elements such that for all nonempty elements x,y of P(A), xRy if x is a proper subset of y and there are no z in P(A) such that x is a proper subset of z and z is a proper subset of y. Then a(n) = |Q|. - Ross La Haye, Feb 20 2008, Oct 21 2008
Also: convolution of A006589 with A000012 (i.e., partial sums of A006589). - R. J. Mathar, Jan 25 2009
The La Haye binary relation Q is more clearly stated as x is nonempty and y has one more element than x. If x is a k-set than the number of such pairs is binomial( n, k) * (n-k). - Michael Somos, Mar 29 2012
Select one of the n nodes of the digraph and select a nonempty subset of the rest to connect to the selected node. This can be done in n * (2^(n-1) - 1) ways. - Michael Somos, Mar 29 2012
Column 1 of A198204. - Peter Bala, Aug 01 2012
a(n) is the number of ternary sequences of length n that contain one 0 and at least one 1.  For example, a(3)=9 since the sequences are the 3 permutations of 011 and the 6 permutations of 012. - Enrique Navarrete, Apr 05 2021
a(n) is also the number of multiplications required to compute the permanent of general n X n matrices using canonical trellis method (see Theorem 5, p. 10 in Kiah et al.). - Stefano Spezia, Nov 02 2021

			G.f. = 2*x^2 + 9*x^3 + 28*x^4 + 75*x^5 + 186*x^6 + 441*x^7 + 1016*x^8 + ...

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
Gerta Rucker and Christoph Rucker, "Walk counts, Labyrinthicity and complexity of acyclic and cyclic graphs and molecules", J. Chem. Inf. Comput. Sci., 40 (2000), 99-106. See Table 1 on page 101. [From Parthasarathy Nambi, Sep 26 2008]

Vincenzo Librandi, Table of n, a(n) for n = 1..2001
Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 12.
Han Mao Kiah, Alexander Vardy and Hanwen Yao, Computing Permanents on a Trellis, arXiv:2107.07377 [cs.IT], 2021.
Tamás Szakács, Convolution of second order linear recursive sequences. II. Commun. Math. 25, No. 2, 137-148 (2017), remark 3.
Tamás Szakács, Linear recursive sequences and factorials, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See p. 36.
Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Second column of A058876. Cf. A003025, A003026.
Column k=1 of A133399.
Cf. A198204.

[(n+1)*2^n-n-1: n in [0..30]]; // Vincenzo Librandi, Sep 26 2011

[seq (stirling2(n,2)*n,n=1..29)]; # Zerinvary Lajos, Dec 06 2006
a:=n->sum(k*binomial(n,k), k=2..n): seq(a(n), n=1..29); # Zerinvary Lajos, May 08 2007

Table[(n+1)*2^n-n-1, {n, 0, 200}] (* Vladimir Joseph Stephan Orlovsky, Jun 30 2011 *)
a[ n_] := Sum[ Binomial[ n, k] (n - k), {k, n-1}]; (* Michael Somos, Mar 29 2012 *)

{a(n) = if( n<1, 0, n * (2^(n-1) - 1))} /* Michael Somos, Mar 29 2012 */

[stirling_number2(i,2)*i for i in range(1,26)] # Zerinvary Lajos, Jun 27 2008

[(n+1)*gaussian_binomial(n,1,2) for n in range(0,29)] # Zerinvary Lajos, May 31 2009

a(n+1) = (n+1)*2^n - n - 1 = Sum_{j=0..n} (n+j)*2^(n-j-1) = A048493(n)-1 = Column sum of A062111. - Henry Bottomley, May 30 2001
From R. J. Mathar, Jan 25 2009: (Start)
G.f.: x^2*(2-3*x)/((1-2*x)*(1-x))^2.
a(n) = 6*a(n-1) - 13*a(n-2) + 12*a(n-3) - 4*a(n-4). (End)
a(n) = Sum_{k=1..n-1} binomial(n, k) * (n-k). - Michael Somos, Mar 29 2012
E.g.f: x*exp(x)*(exp(x)-1). - Enrique Navarrete, Apr 05 2021

More terms from Vladeta Jovovic, Apr 10 2001

A141618 Triangle read by rows: number of nilpotent partial transformations (of an n-element set) of height r (height(alpha) = |Im(alpha)|), 0 <= r < n.

Original entry on oeis.org

1, 1, 2, 1, 9, 6, 1, 28, 72, 24, 1, 75, 500, 600, 120, 1, 186, 2700, 7800, 5400, 720, 1, 441, 12642, 73500, 117600, 52920, 5040, 1, 1016, 54096, 571536, 1764000, 1787520, 564480, 40320, 1, 2295, 217800, 3916080, 21019824, 40007520, 27941760, 6531840, 362880, 1, 5110, 839700, 24555600, 214326000

Offset: 1

Abdullahi Umar, Aug 23 2008

The sum of each row of the sequence (as a triangular array) is A000272. Second left-downward diagonal is A058877.
From Tom Copeland, Oct 26 2014: (Start)
With T(x,t) the e.g.f. for A055302 for the number of labeled rooted trees with n nodes and k leaves, the mirror of the row polynomials of this array are given by e^T(x,t) = exp[ t * x + (2t) * x^2/2! + (6t + 3t^2) * x^3/3! + ...] = 1 + t * x + (2t + t^2) * x^2/2! + (6t + 9t^2 + t^3) * x^3/3! + ... = 1 + Nr(x,t).
Equivalently, e^x-1 = Nr[Tinv(x,t),t] = t * N[t*Tinv(x,t),1/t], where N(x,t) is the e.g.f. of this array and Tinv(x,t) is the comp. inverse in x of T(x,t). Note that Nr(x,t) = t * N(x*t,1/t), and N(x,t) = t * Nr(x*t,1/t). Also, log[1 + Nr(x,t)]= x * [t + Nr(x,t)] = T(x,t).
E.g.f. is N(x,t)= t * {exp[T(x*t,1/t)] - 1}, and log[1 + N(x,t)/t] =  T(x*t,1/t) =  x + (2t) * x^2/2! +  (3t + 6t^2) * x^3/3! + (4t + 36t^2 + 24t^3) * x^4/4! + ... = x + (t) * x^2 + (t + 2t^2) * x^3/2! + (t + 9t^2 + 6t^3) * x^4/3! +  ... is the comp. inverse in x of x / [1 + t * (e^x - 1)].
The exp/log transforms (A036040/A127671) generally give associations between enumerations of sets of connected graphs/objects (in this case, trees) and sets of disconnected (or not necessarily connected) graphs/objects (in this case, bipartite graphs of the nilpotent transformations). The transforms also relate formal cumulants and moments so that Nr(x,t) is then the e.g.f. for the formal moments associated to the formal cumulants whose e.g.f. is T(x,t). (End)
T(n,k) is the number of parking functions of length n containing exactly k+1 distinct values in its image. - Alan Kappler, Jun 08 2024

			N(J(4,2)) = 6*6*2 = 72.
From _Peter Bala_, Oct 22 2008: (Start)
Triangle begins
n\k|..0.....1.....2.....3.....4....5
=====================================
.1.|..1
.2.|..1.....2
.3.|..1.....9.....6
.4.|..1....28....72....24
.5.|..1....75...500...600...120
.6.|..1...186..2700..7800..5400...720
...
(End)

A. Laradji and A. Umar, On the number of nilpotents in the partial symmetric semigroup, Comm. Algebra 32 (2004), 3017-3023.
A. Laradji and A. Umar, On the number of nilpotents in the partial symmetric semigroup, Tech. Report TR305, King Fahd Univ. of Petroleum and Minerals, (2003).
Wikipedia, Cumulant

Cf. A000272, A007318, A036040, A048993, A055302, A058877, A127671, A198204.

A048993 := proc(n,k)
    combinat[stirling2](n,k) ;
end proc:
A141618 := proc(n,k)
    binomial(n,k)*k!*A048993(n,k+1) ;
end proc:

Flatten[CoefficientList[CoefficientList[InverseSeries[Series[Log[1 + x]/(1 + t*x),{x,0,9}]],x]*Table[n!, {n,0,9}],t]] (* Peter Luschny, Oct 24 2015, after Peter Bala *)

A055302(n,k)=n!/k!*stirling(n-1, n-k,2);
T(n,k)=A055302(n+1,n+1-k) / (n+1);
for(n=1,10,for(k=1,n,print1(T(n,k),", "));print());
\\ Joerg Arndt, Oct 27 2014

N(J(n,r)) = C(n,r)*S(n,r+1)*r! where S(n, r + 1) is a Stirling number of the second kind (given by A048993 with zeros removed); generating function = (x+1)^(n-1).
From Peter Bala, Oct 22 2008: (Start)
Define a functional I on formal power series of the form f(x) = 1 + ax + bx^2 + ... by the following iterative process. Define inductively f^(1)(x) = f(x) and f^(n+1)(x) = f(x*f^(n)(x)) for n >= 1. Then set I(f(x)) = lim_{n -> infinity} f^(n)(x) in the x-adic topology on the ring of formal power series; the operator I may also be defined by I(f(x)) := 1/x*series reversion of x/f(x).
Let f(x) = 1 + a*x + a*x^2/2! + a*x^3/3! + ... . Then the e.g.f. for this table is I(f(x)) = 1 + a*x +(a + 2*a^2)*x^2/2! + (a + 9*a^2 + 6*a^3)*x^3/3! + (a + 28*a^2 + 72*a^3 + 24*a^4)*x^4/4! + ... . Note, if we take f(x) = 1 + a*x + a*x^2 + a*x^3 + ... then I(f(x)) is the o.g.f. of the Narayana triangle A001263. (End)
A generator for this array is given by the inverse, g(x,t), of f(x,t)= x/(1 + t * (e^x-1)). Then A248927 gives h(x,t)= x / f(x,t) = 1 + t*(e^x-1)= 1 + t * (x + x^2/2! + x^3/3! + ...) and g(x,t)= x * (1 + t * x + (t + 2 t^2) * x^2/2! + (t + 9 t^2 + 6 t^3) * x^3/3! + ...), so by Bala's arguments A248927 is a refinement of A141618 with row sums A000272. The connection to Narayana numbers is reflected in the relation between A248927 and A134264. See A145271 for more relations that g(x,t) and f(x,t) must satisfy. - Tom Copeland, Oct 17 2014
T(n,k) = C(n,k-1) * A028246(n,k) = C(n,k-1) * A019538(n,k)/k = A055302(n+1,n+1-k) / (n+1). - Tom Copeland, Oct 25 2014
E.g.f. is the series reversion of log(1 + x)/(1 + t*x) with respect to x. Cf. A198204. - Peter Bala, Oct 21 2015

More terms from Joerg Arndt, Oct 27 2014

A052892 E.g.f. is series reversion of log(1+x)*(1-x).

Original entry on oeis.org

0, 1, 3, 22, 269, 4606, 101407, 2728818, 86783769, 3184595686, 132443395091, 6156200036746, 316272966462565, 17795937622944846, 1088410048965734055, 71893314170319604066, 5100574859506418167601, 386824334429004242804086, 31229208329663841200670619

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

A simple grammar.

Sum_{k=1..n} a(k)*Sum_{j=k..n} C(k,n-j)*(-1)^(n-j)*Stirling1(j,k)/j! = delta(n,1) for n > 0. - Vladimir Kruchinin, Feb 08 2012

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 868.
Vladimir Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.

Row sums of A198204. - Peter Bala, Aug 01 2012

Cf. A052842.

spec := [S,{C=Prod(Z,B),S=Set(C,1 <= card),B=Sequence(S)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);
# second Maple program:
A052892 := proc (n) option remember; `if`(n = 0, 0, add(pochhammer(n, k)*Stirling2(n, k+1), k = 0..n-1)) end:
seq(A052892(n), n = 0..17); # Mélika Tebni, Jun 03 2023

a[n_] := ((-1)^(n-1)*(n-1)!*Sum[ (Sum[ j!*(Sum[ (StirlingS1[i, j]*(-1)^(i)*Binomial[j, n+j-i-1])/i!, {i, j, n+j-1}])*Binomial[k, j], {j, 0, k}])*Binomial[n+k-1, n-1], {k, 0, n-1}]); a[0] = 0; Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Feb 26 2013, after Vladimir Kruchinin *)
CoefficientList[InverseSeries[Series[Log[1+x]*(1-x), {x, 0, 20}], x],x] * Range[0, 20]! (* Vaclav Kotesovec, Jan 22 2014 *)

a(n):=((-1)^(n-1)*(n-1)!*sum((sum(j!*(sum((stirling1(i,j)*(-1)^(i)*binomial(j,n+j-i-1))/i!,i,j,n+j-1))*binomial(k,j), j,0,k)) *binomial(n+k-1,n-1),k,0,n-1)); /* Vladimir Kruchinin, Feb 06 2012 */

E.g.f.: exp(RootOf(-2*_Z+_Z*exp(x*_Z)+1)*x) - 1.
G.f.: x*Sum_{k>0} 1/(2-k*x)^k. - Vladeta Jovovic, Sep 23 2006
a(n) = (-1)^(n-1)*(n-1)!*Sum_{k=0..n-1} Sum_{j=0..k} j!*(Sum_{i=j..n+j-1} Stirling1(i,j)*(-1)^(i)*C(j,n+j-i-1)/i!)*C(k,j)*C(n+k-1,n-1), n > 0. - Vladimir Kruchinin, Feb 08 2012
a(n) = Sum_{i=0..n-1} binomial(n-1,i)*Sum_{k=0..i} Stirling2(i,k)*k!* binomial(n+k-1,k). - Vladimir Kruchinin, Jan 22 2014
a(n) ~ n^(n-1) * (c/2)^(n-1) / (sqrt(c+1) * exp(n) * (c-1)^(2*n-1)), where c = LambertW(2*exp(1)) = 1.3748225281836... - Vaclav Kotesovec, Jan 22 2014
For n >= 1, a(n) = Sum_{k=0..n-1} Pochhammer(n, k)*Stirling2(n, k+1). - Mélika Tebni, Jun 03 2023

A133399 Triangle T(n,k)=number of forests of labeled rooted trees with n nodes, containing exactly k trees of height one, all others having height zero (n>=0, 0<=k<=floor(n/2)).

Original entry on oeis.org

1, 1, 1, 2, 1, 9, 1, 28, 12, 1, 75, 120, 1, 186, 750, 120, 1, 441, 3780, 2100, 1, 1016, 16856, 21840, 1680, 1, 2295, 69552, 176400, 45360, 1, 5110, 272250, 1224720, 705600, 30240, 1, 11253, 1026300, 7692300, 8316000, 1164240, 1, 24564, 3762132, 45018600

Offset: 0

Alois P. Heinz, Nov 24 2007

			Triangle begins:
  1;
  1;
  1,     2;
  1,     9;
  1,    28,     12;
  1,    75,    120;
  1,   186,    750,     120;
  1,   441,   3780,    2100;
  1,  1016,  16856,   21840,   1680;
  1,  2295,  69552,  176400,  45360;
  1,  5110, 272250, 1224720, 705600, 30240;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
A. P. Heinz, Finding Two-Tree-Factor Elements of Tableau-Defined Monoids in Time O(n^3), Ed. S. G. Akl, F. Fiala, W. W. Koczkodaj: Advances in Computing and Information, ICCI90 Niagara Falls, LNCS 468, Springer-Verlag (1990), pp. 120-128.

Columns k=1,2 give: A058877, A133386.
Row sums give: A000248.
T(2n,n) = A001813(n), T(2n+1,n) = A002691(n).
Reading the table by diagonals gives triangle A198204. - Peter Bala, Jul 31 2012
Cf. A235596.

/* As triangle */ [[Binomial(n,k)*Factorial(k)*StirlingSecond(n-k+1,k+1): k in [0..Floor(n/2)]]: n in [0.. 15]]; // Vincenzo Librandi, Jun 06 2019

T:= (n,k)-> binomial(n,k)*k!*Stirling2(n-k+1,k+1): for n from 0 to 10 do lprint(seq(T(n, k), k=0..floor(n/2))) od;

nn=12;f[list_]:=Select[list,#>0&];Map[f,Range[0,nn]!CoefficientList[ Series[Exp[y x (Exp[x]-1)] Exp[x],{x,0,nn}],{x,y}]]//Grid (* Geoffrey Critzer, Feb 09 2013 *)
t[n_, k_] := Binomial[n, k]*k!*StirlingS2[n-k+1, k+1]; Table[t[n, k], {n, 0, 12}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Dec 19 2013 *)

T(n,k) = C(n,k) * k! * stirling2(n-k+1,k+1).
E.g.f.: exp(y*x*(exp(x)-1))*exp(x). - Geoffrey Critzer, Feb 09 2013
Sum_{k=1..floor(n/2)} T(n,k) = A235596(n+1). - Alois P. Heinz, Jun 21 2019

A133386 Number of forests of labeled rooted trees with n nodes, containing exactly 2 trees of height one, all others having height zero.

Original entry on oeis.org

0, 0, 0, 0, 12, 120, 750, 3780, 16856, 69552, 272250, 1026300, 3762132, 13498056, 47615750, 165683700, 570024240, 1942538592, 6566094450, 22038141420, 73510278380, 243854707320, 804962754750, 2645408201700, 8658857196552, 28237920483600, 91778694166250

Offset: 0

Alois P. Heinz, Nov 22 2007

nonn

			a(4) = 12 because 12 trees of the given kind exist: 1<-3 2<-4, 1<-4 2<-3, 1<-2 3<-4, 1<-4 3<-2, 1<-2 4<-3, 1<-3 4<-2, 2<-1 3<-4, 2<-4 3<-1, 2<-1 4<-3, 2<-3 4<-1, 3<-1 4<-2 and 3<-2 4<-1.

Alois P. Heinz, Table of n, a(n) for n = 0..650
A. P. Heinz, Finding Two-Tree-Factor Elements of Tableau-Defined Monoids in Time O(n^3), Ed. S. G. Akl, F. Fiala, W. W. Koczkodaj: Advances in Computing and Information, ICCI90 Niagara Falls, LNCS 468, Springer-Verlag (1990), pp. 120-128.
Index entries for linear recurrences with constant coefficients, signature (18,-141,630,-1767,3222,-3815,2826,-1188,216).

Cf. A058877, A000248.
Column k=2 of A133399.
Column 2 of A198204. - Peter Bala, Aug 01 2012

a:= n-> n*(n-1)*Stirling2(n-1, 3):
seq(a(n), n=0..50);

Join[{0},Table[n(n-1)StirlingS2[n-1,3],{n,30}]] (* or *) LinearRecurrence[{18,-141,630,-1767,3222,-3815,2826,-1188,216},{0,0,0,0,12,120,750,3780,16856},30] (* Harvey P. Dale, May 02 2015 *)

a(n) = n*(n-1) * Stirling2(n-1,3).
G.f.: -2*x^4*(85*x^4-180*x^3+141*x^2-48*x+6) / ((x-1)^3*(3*x-1)^3*(2*x-1)^3). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009
a(0)=0, a(1)=0, a(2)=0, a(3)=0, a(4)=12, a(5)=120, a(6)=750, a(7)=3780, a(8)=16856, a(n)=18*a(n-1)-141*a(n-2)+630*a(n-3)-1767*a(n-4)+ 3222*a(n-5)- 3815*a(n-6)+2826*a(n-7)-1188*a(n-8)+216*a(n-9). - Harvey P. Dale, May 02 2015

cp's OEIS Frontend

A058877 Number of labeled acyclic digraphs with n nodes containing exactly n-1 points of in-degree zero.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Sage

Formula

Extensions

A141618 Triangle read by rows: number of nilpotent partial transformations (of an n-element set) of height r (height(alpha) = |Im(alpha)|), 0 <= r < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A052892 E.g.f. is series reversion of log(1+x)*(1-x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A133399 Triangle T(n,k)=number of forests of labeled rooted trees with n nodes, containing exactly k trees of height one, all others having height zero (n>=0, 0<=k<=floor(n/2)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A133386 Number of forests of labeled rooted trees with n nodes, containing exactly 2 trees of height one, all others having height zero.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula