A048493 -id:A048493 - 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

A048483 Array read by antidiagonals: T(k,n) = (k+1)2^n - k.

Original entry on oeis.org

1, 2, 1, 4, 3, 1, 8, 7, 4, 1, 16, 15, 10, 5, 1, 32, 31, 22, 13, 6, 1, 64, 63, 46, 29, 16, 7, 1, 128, 127, 94, 61, 36, 19, 8, 1, 256, 255, 190, 125, 76, 43, 22, 9, 1, 512, 511, 382, 253, 156, 91, 50, 25, 10, 1, 1024, 1023, 766, 509, 316, 187

Offset: 0

Clark Kimberling

n-th difference of (T(k,n),T(k,n-1),...,T(k,0)) is k+1, for n=1,2,3,...; k=0,1,2,...

			1 2 4 8 16 32 ...
1 3 7 15 31 63 ...
1 4 10 22 46 94 ...
1 5 13 29 61 125 ...
1 6 16 36 76 156 ...

Rows are A000079 (k=0), A000225 (k=1), A033484 (k=2), A036563 (k=3), A048487 (k=4), A048488 (k=5), A048489 (k=6), A048490 (k=7), A048491 (k=8).

Main diagonal is A048493. Cf. A048494.

G.f.: (1-x+kx)/[(1-x)(1-2x)]. E.g.f.: (k+1)*exp(2x) - k*exp(x).

Recurrences: T(k, n) = 2T(k, n-1)+k = T(k-1, n)+2^n-1, T(k, 0) = 1.

Edited by Ralf Stephan, Feb 05 2004

A260005 a(n) = f(2,n,2), where f is the Sudan function defined in A260002.

Original entry on oeis.org

19, 10228, 15569256417, 5742397643169488579854258, 36681813266165915713665394441869800619098139628586701684547

Offset: 0

Natan Arie Consigli, Jul 23 2015

nonn

Naturally a subsequence of A260004.
See A260002-A260003 for the evaluation of the Sudan function.
Using f(2,n,2) = f(1, f(2,n,1), f(2,n,1)+2) = 2^(f(2,n,1)+2)*(f(2,n,1)+2)-f(2,n,1)-4 and f(2,n,1) = f(1, n, n+1) = 2^(n+1)*(n+2)-(n+3) we have:
a(n)=f(2,n,2)
    =f(1, 2^(n+1)*(n+2)-(n+3), 2^(n+1)*(n+2)-(n+3)+2)
    =2^(2^(n+1)*(n+2)-(n+3)+2)*(2^(n+1)*(n+2)-(n+3)+2)-2^(n+1)*(n+2)+(n+3)-4
    =2^(2^(n+1)*(n+2)-(n+1))*(2^(n+1)*(n+2)-(n+1))-2^(n+1)*(n+2)+(n-1).

			a(1) = f(2,1,2) = f(1,f(2,1,1),f(2,1,1)+2) = f(1,8,10) = 2^10*(8+2)-10-2 = 10228.

Natan Arie' Consigli, Table of n, a(n) for n = 0..6
Wikipedia, Sudan function (see 3rd line of "Values of F2(x, y)" table).

Cf. A048493 (f(2,n,1)), A260002, A260003, A260004, A260006.

[2^(2^(n+1)*(n+2)-(n+1))*(2^(n+1)*(n+2)-(n+1))-2^(n+1)*(n+2)+(n-1):n in [0..5]]; // Vincenzo Librandi, Jul 27 2015

Table[2^(2^(n + 1) (n + 2) - (n + 1)) (2^(n + 1) (n + 2) - (n + 1)) - 2^(n + 1) (n + 2) + (n - 1), {n, 0, 5}] (* Vincenzo Librandi, Jul 27 2015 *)

a(n) = 2^(2^(n+1)*(n+2)-(n+1))*(2^(n+1)*(n+2)-(n+1))-2^(n+1)*(n+2)+(n-1);
vector(10, n, a(n-1)) \\ Altug Alkan, Oct 01 2015

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

A260003 Values f(1,x,y) with x>=0, y>0, in increasing order, where f is the Sudan function defined in A260002.

Original entry on oeis.org

1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 24, 25, 26, 27, 28, 29, 31, 32, 33, 35, 36, 37, 39, 40, 41, 42, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 63, 64, 65, 66, 67, 69, 71, 72, 73, 74, 75

Offset: 1

Natan Arie Consigli, Jul 23 2015

nonn

Equivalently, numbers of the form 2^y(x+2)-y-2.
Using f(1,x,y) = f(0, f(1,x,y-1), f(1,x,y-1)+y) = 2*f(1,x,y-1) + y
f(1,x,y) + y + 2 = 2*(f(1,x,y-1)+y-1+2) let g(y) = f(1,x,y) + y + 2 then g(y) = 2*g(y-1). This means g(y)=2^y*g(0) and f(1,x,y) + y + 2 = 2^y(f(1,x,0)+2) but f(1,x,0) = x so f(1,x,y) = 2^y(x+2) - y - 2.
In this list we suppose that y>0. If we include y=0, every natural number would be in the sequence.

			19 is listed because f(1,1,3) = 2^3*(1+2) - 3 - 2 = 19.

Cf. A000325 (f(1,2,n)), A005408 (f(1,n,1)=2n+1), A048493 (f(1,n,2)), A079583 (f(1,1,n)), A123720 (f(1,4,n)), A133124(f(1,3,n)), A260002, A260004, A260005 (f(2,n,2)), A260006.

A260004 Values of f(2,x,y) in increasing order, for x>=0, y>0 where f is the Sudan function defined in A260002.

Original entry on oeis.org

1, 8, 19, 27, 74, 185, 440, 1015, 2294, 5109, 10228, 11252, 24563, 53234, 114673, 245744, 524271, 1114094, 2359277, 4980716, 10485739, 22020074, 46137321, 88080360, 96468968, 201326567, 419430374, 872415205, 1811939300, 15569256417

Offset: 1

Natan Arie Consigli, Jul 23 2015

nonn

This is a subsequence of A260003 since f(2,x,y)= f(1, f(2,x,y-1), f(2,x,y-1)+y).
In this list we suppose that y>0. If we take y=0, all the natural numbers would be in the sequence.
To evaluate the Sudan function see A260002-A260003.

			f(2,0,1) = f(1, f(2,0,0), f(2,0,0)+1) = f(1,0,1) = 2^1(0+2)-1-2 = 1;
f(2,0,2) = f(1, [f(2,0,1)], [f(2,0,1)+1+1]) = f(1,1,3) = 2^3(1+2)-3-2 = 19;

Cf. A048493 (f(2,n,1)), A260002, A260003, A260005 (f(2,n,2)), A260006.

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

A048483 Array read by antidiagonals: T(k,n) = (k+1)2^n - k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A260005 a(n) = f(2,n,2), where f is the Sudan function defined in A260002.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A260003 Values f(1,x,y) with x>=0, y>0, in increasing order, where f is the Sudan function defined in A260002.

Views

Author

Keywords

Comments

Examples

Crossrefs

A260004 Values of f(2,x,y) in increasing order, for x>=0, y>0 where f is the Sudan function defined in A260002.

Views

Author

Keywords

Comments

Examples

Crossrefs