A038154 -id:A038154 - cp's OEIS frontend

A001339 a(n) = Sum_{k=0..n} (k+1)! binomial(n,k).

1, 3, 11, 49, 261, 1631, 11743, 95901, 876809, 8877691, 98641011, 1193556233, 15624736141, 220048367319, 3317652307271, 53319412081141, 909984632851473, 16436597430879731, 313262209859119579, 6282647653285676001, 132266266384961600021, 2916471173788403280463

Offset: 0

N. J. A. Sloane

nonn

Number of arrangements of {1, 2, ..., n, n + 1} containing the element 1. - Emeric Deutsch, Oct 11 2001
From Thomas Wieder, Oct 21 2004: (Start)
"Also the number of hierarchies with unlabeled elements and labeled levels where the levels are permuted.
"Let l_x denote level x, e.g. l_2 is level 2. Let * denote an element. Then l_1*l_2***l_3** denotes a hierarchy of n = 6 unlabeled elements with one element on level 1, three elements on level 2 and 2 elements on level 3.
"E.g. for n=3 one has a(3) = 11 possible hierarchies: l_1***, l_1**l_2*, l_1*l_2**, l_2**l_1*, l_2*l_1**, l_1*l_2*l_3*, l_3*l_1*l_2*, l_2*l_3*l_1*, l_1*l_3*l_2*, l_2*l_1*l_3*, l_3*l_2*l_1*. See A064618 for the number of hierarchies with labeled elements and labeled levels." (End)
Polynomials in A010027 evaluated at 2.
Also the permanent of any n X n cofactor of an n+1 X n+1 version of J+I other than an n X n version of J + I (that is, a (1, 2) matrix with n - 1 2s, at most one per row and column). - D. G. Rogers, Aug 27 2006
a(n) = number of partitions of [n+1] into lists of sets that are both non-nesting and non-crossing. Non-nesting means that no set is contained in the span (interval from min to max) of another. For example, a(1) counts 12, 1-2, 2-1 and a(2) counts 123, 1-23, 23-1, 3-12, 12-3, 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1. - David Callan, Sep 20 2007
Row sums of triangle A137594. - Gary W. Adamson, Jan 28 2008
From Peter Bala, Jul 10 2008: (Start)
a(n) is a difference divisibility sequence, that is, the difference a(n) - a(m) is divisible by n - m for all n and m (provided n is not equal to m). See A000522 for further properties of difference divisibility sequences.
a(n) equals the sum of the lengths of the paths between a pair of distinct vertices of the complete graph K_(n + 2) on n + 2 vertices [Hassani]. For example, for the complete graph K_4 with vertex set {A,B,C,D} the 5 paths between A and B are AB of length 1, ACB and ADB, both of length 2 and ACDB and ADCB, both of length 3. The sum of the lengths is 1 + 2 + 2 + 3 + 3 = 11 = a(2).
The number of paths between 2 distinct vertices of K_n is equal to A000522(n - 2); the number of simple cycles through a vertex of K_n equals A038154(n - 1).
Recurrence relation: a(0) = 1, a(1) = 3, a(n) = (n+2)*a(n - 1) - (n - 1)*a(n - 2) for n >= 2. The sequence b(n) := n*n! = A001563(n) satisfies the same recurrence with the initial conditions b(0) = 0, b(1) = 1. This leads to the finite continued fraction expansion a(n)/b(n) = 3 - 1/(4 - 2/(5 - 3/(6 - ... - (n - 1)/(n + 2)))), n >= 1.
Limit_{n->oo} a(n)/b(n) = e = 3 - 1/(4 - 2/(5 - 3/(6 - ... - n/((n + 3) - ...)))).
For n >= 1, a(n) = b(n)*(3 - Sum_{k=2..n} 1/(k!*(k - 1)*k)) (see the formula by Deutsch) since the rhs satisfies the above recurrence with the same initial conditions. Hence e = 3 - Sum_{k>=2} 1/(k!*(k - 1)*k).
For sequences satisfying the more general recurrence a(n) = (n + 1 + r)*a(n-1) - (n-1)*a(n-2), which yield series acceleration formulas for e/r! that involve the Poisson-Charlier polynomials c_r(-n; -1), refer to A000522 (r=0), A082030 (r=2), A095000 (r=3) and A095177 (r=4). (End)
Binomial transform of n! Offset 1. a(3) = 11. - Al Hakanson (hawkuu(AT)gmail.com), May 18 2009
Equals eigensequence of a triangle with (1, 2, 3, ...) as the right border and the rest 1's; equivalent to a(n) = [n terms of the sequence (1, 1, 1, ...) followed by (n + 1)] dot [(n + 1) terms of the sequence (1, 1, 3, 11, 245, ...)]. Example: 261 = a(4) = (1, 1, 1, 1, 5) dot (1, 1, 3, 11, 49) = 1 + 1 + 3 + 11 + 245 = 261. - Gary W. Adamson, Jul 24 2010
Number of nonnegative integers which use each digit at most once in base n+1. - Franklin T. Adams-Watters, Oct 02 2011
a(n) is the number of permutations of {1,2,...,n+2} in which there is an increasing contiguous subsequence (ascending run) beginning with 1 and ending with n+2. The number of such permutations with exactly k, 0<=k<=n, elements between the 1 and (n+2) is given by A132159(n,k) whose row sums equal this sequence. See example. - Geoffrey Critzer, Feb 15 2013

			G.f. = 1 + 3*x + 11*x^2 + 49*x^3 + 261*x^4 + 1631*x^5 + 11743*x^6 + 95901*x^7 + ...
a(2) = 11: {1, 12, 21, 13, 31, 123, 132, 213, 231, 312, 321}.
a(2) = 11 because we have 11 permutations of {1,2,3,4} (written in one line notation) that have an increasing subsequence beginning with 1 and ending with 4: 1,2,3,4; 1,2,4,3; 1,3,4,2; 1,4,2,3; 1,4,3,2; 2,1,3,4; 2,1,4,3; 2,3,1,4; 3,1,2,4; 3,1,4,2; 3,2,1,4. - _Geoffrey Critzer_, Feb 15 2013

A. Hordijk, Markov Decision Chains, pp. 97-103 in Images of SMC Research, 1996, Stichting Mathematisch Centrum, Amsterdam, Netherlands, 1996. See p. 103.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
W. A. Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 56, ex. 232.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
J. L. Adams, Conceptual Blockbusting: A Guide to Better Ideas, Freeman, San Francisco, 1974. [Annotated scans of pages 69 and 70 only]
Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7.
Paul Barry, A note on number triangles that are almost their own production matrix, arXiv:1804.06801 [math.CO], 2018.
E. Biondi, L. Divieti and G. Guardabassi, Counting paths, circuits, chains and cycles in graphs: A unified approach, Canad. J. Math. 22 1970 22-35.
Philip Feinsilver and John McSorley, Zeons, Permanents, the Johnson Scheme, and Generalized Derangements, International Journal of Combinatorics, Volume 2011, Article ID 539030, 29 pages.
Loïc Foissy and Frédéric Patras, Natural endomorphisms of shuffle algebras, arXiv preprint arXiv:1205.2986 [math.RA], 2012.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 36.
M. Hassani, Counting and computing by e, arXiv:math/0606613 [math.CO], 2006.
F. Hivert, J.-C. Novelli and J.-Y. Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 400
M. J. Knight and W. O. Egerland, Solution to Problem 5911, Amer. Math. Monthly 81 (1974) 675-676.
Zhentao Lu, Elementary proofs of generalized continued fraction formulae for e, arXiv:1907.05563 [math.NT], 2019.
Eric Weisstein's World of Mathematics, Poisson-Charlier polynomial
Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 7.

Cf. A001563, A064618, A089900, A137594.
a(n) = A000522(n+1) - A000522(n).
First differences of A000522, A007526, A026243, A073591.
Equals (1/2)*A006183(n-2).
Equals A036918(n+1) + 1.
Leftmost column of A276588.
Cf. also A136104.

A001339:=List([0..20],n-> Sum([0..n], k-> Factorial(k+1)*Binomial(n,k))); # Muniru A Asiru, Feb 17 2018

[Factorial(n)*(&+[(n-k+1)/Factorial(k): k in [0..n]]): n in [0..20]]; // G. C. Greubel, Jul 15 2019

a:=proc(n) options operator, arrow: factorial(n)*n*(3-(sum(1/(j*(j-1)*factorial(j)), j=2..n))) end proc: 1, seq(a(n),n=1..20); # Emeric Deutsch, Apr 12 2008
a := n -> hypergeom([2, -n], [], -1); seq(simplify(a(n)), n=0..18); # Peter Luschny, Sep 20 2014

a[n_] := n!*Sum[(k+1)/(n-k)!, {k, 0, n}]; a /@ Range[0, 20] (* Jean-François Alcover, Jul 13 2011 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[x] / (1 - x)^2, {x, 0, n}]] (* Michael Somos, Oct 20 2011 *)

{a(n) = if( n<0, 0, n! * polcoeff( exp(x + x * O(x^n)) / (1 - x)^2, n))} /* Michael Somos, Mar 04 2004 */

vector(20, n, n--; n!*sum(k=0,n,(n-k+1)/k!)) \\ G. C. Greubel, Jul 15 2019

[factorial(n)*sum((n-k+1)/factorial(k) for k in (0..n)) for n in (0..20)] # G. C. Greubel, Jul 15 2019

E.g.f.: exp(x)/(1-x)^2.
a(n) = round(evalf(exp(1)*(n-1)*(n-1)!)) (n>1).
a(n) = floor(n*n!*e) + 1. - Melvin J. Knight (knightmj(AT)juno.com), May 30 2001
a(n) = {e*n*n!} for n > 0, where {x} denotes the nearest integer part. Proposed by Simon Plouffe, March 1993.
The n-th row of array A089900 is the n-th binomial transform of this sequence. The (n+1)-th term of the n-th binomial transform is (n+1)^(n+1), for n >= 0. E.g., the 5th term of the 4th binomial transform is 5^5: [1, 7, 51, 389, 3125, ...]. - Paul D. Hanna, Nov 14 2003
G.f.: Sum_{k>=0} k! * (x / (1 - x))^k. - Michael Somos, Mar 04 2004
a(n) = Sum_{k = 0..n} A046716(n, k)*2^(n-k). - Philippe Deléham, Jun 12 2004
(n-1)*a(n) = n^2*a(n-1)-1. - Vladeta Jovovic, Sep 04 2004
a(n) = Sum_{k=0..n} P(n, k)*(k+1). - Ross La Haye, Aug 28 2005
a(n) = n!*n*(3 - Sum_{j=2..n} 1/(j*(j-1)*j!)) for n>=1. - Emeric Deutsch, Apr 12 2008
a(n) = (a(n-1)^2 + 2 * a(n-2)^2 + a(n-2) * a(n-3) - 4 * a(n-1) * a(n-3)) / (a(n-2) - a(n-3)) if n>1. - Michael Somos, Oct 20 2011
E.g.f.:1/Q(0); Q(k) = 1 - 2*x/(1+x/(2-x-2/(1-x*(k+1)/Q(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2011
G.f.: 1/Q(0), where Q(k) = 1 - x - x*(k+2)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 22 2013
G.f.: Q(0)/x - 1/x, where Q(k) = 1 + (2*k + 1)*x/( 1 - x - 2*x*(1-x)*(k+1)/(2*x*(k+1) + (1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 09 2013
G.f.: (2/x)/G(0) - 1/x, where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+3) - 1 + x*(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013
G.f.: Q(0)/(2*x) - 1/x, where Q(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1-x)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 08 2013
G.f.: W(0)/x - 1/x, where W(k) = 1 - x*(k+1)/( x*(k+2) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 25 2013
a(n) = hypergeometric([2, -n], [], -1). - Peter Luschny, Sep 20 2014
Upper and bottom right terms of the infinite 2 X 2 matrix product_{N=1,2,3,...} [(1,1); (1,N)]. - Gary W. Adamson, Jul 28 2016
a(n) = R(n,n+1,n) where R(x,y,z) is defined to be R(x+1,y,z+1) = R(y,x,x) + R(z,y,z), R(0,y,z+1) = R(z,y,z), R(x+1,y,0) = R(y,x,x), and R(0,y,0) = y. - David M. Cerna, Feb 16 2018
a(n) = (n + 1)!*hypergeom([-n], [-n-1], 1). - Peter Luschny, Nov 02 2018
a(n) = Integral_{x=0..1} (-LambertW(-1,-x/e))^n dx. - Gleb Koloskov, Jul 25 2021
a(n) = KummerU(-n, -n-1, 1). - Peter Luschny, May 10 2022

Typo in description in 1995 Encyclopedia of Integer Sequences corrected Mar 15 1997

Link updated by Susanne Wienand, Nov 19 2011

A038155 a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!.

Original entry on oeis.org

0, 0, 1, 6, 30, 160, 975, 6846, 54796, 493200, 4932045, 54252550, 651030666, 8463398736, 118487582395, 1777313736030, 28437019776600, 483429336202336, 8701728051642201, 165332832981201990, 3306656659624039990, 69439789852104840000

Offset: 0

N. J. A. Sloane

For n>=2, a(n) gives the operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives the number of comparisons required to find the first interchangeable element in step L3 (see answer to exercise 5). - Hugo Pfoertner, Jan 27 2003
a(n) mod 5 = A011658(n+1). - G. C. Greubel, Apr 13 2016
a(450) has 1001 decimal digits. - Michael De Vlieger, Apr 13 2016
Also the number of (undirected) paths in the complete graph K_n. - Eric W. Weisstein, Jun 04 2017

D. E. Knuth: The Art of Computer Programming, Volume 4, Combinatorial Algorithms, Volume 4A, Enumeration and Backtracking. Pre-fascicle 2B, A draft of section 7.2.1.2: Generating all permutations. Available online; see link.

Michael De Vlieger, Table of n, a(n) for n = 0..449
D. E. Knuth, TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations).
Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Graph Path

Cf. A011658, A038154, A038156, A056542, A079752, A079884, A080047, A080048, A080049.

A038155:=n->(n!/2)*add(1/k!, k=0..n-2): seq(A038155(n), n=0..30); # Wesley Ivan Hurt, Apr 16 2016

RecurrenceTable[{a[0] == 0, a[n] == Sum[a[n - 1] + k, {k, 0, n - 1}]}, a, {n, 21}] (* Ilya Gutkovskiy, Apr 13 2016 *)
Table[(n!/2) Sum[1/k!, {k, 0, n - 2}], {n, 0, 21}] (* Michael De Vlieger, Apr 13 2016 *)
Table[1/2 E (n - 1) n Gamma[n - 1, 1], {n, 0, 20}] (* Eric W. Weisstein, Jun 04 2017 *)
Table[If[n == 0, 0, Floor[n! E - n - 1]/2], {n, 0, 20}] (* Eric W. Weisstein, Jun 04 2017 *)

a(n) = 1/2*floor(n!*exp(1)-n-1), n>0. - Vladeta Jovovic, Aug 18 2002
E.g.f.: x^2/2*exp(x)/(1-x). - Vladeta Jovovic, Aug 25 2002
a(n) = Sum_{k=0..n-1} a(n-1) + k, a(0)=0. - Ilya Gutkovskiy, Apr 13 2016
a(n) = A038154(n)/2. - Alois P. Heinz, Jan 26 2017

A082458 Multiply by 1, add 1, multiply by 2, add 2, etc., starting with 0.

Original entry on oeis.org

0, 0, 1, 2, 4, 12, 15, 60, 64, 320, 325, 1950, 1956, 13692, 13699, 109592, 109600, 986400, 986409, 9864090, 9864100, 108505100, 108505111, 1302061332, 1302061344, 16926797472, 16926797485, 236975164790, 236975164804, 3554627472060, 3554627472075, 56874039553200, 56874039553216

Offset: 0

Vladeta Jovovic, Apr 25 2003

nonn

Bisections: A007526 and A038154.

Paolo Xausa, Table of n, a(n) for n = 0..800

Cf. A019464 (same, but start with 1), A019465 (start with 2), A019466 (start with 3).

Cf. A019460 .. A019463 & A082448 (similar, but first add, then multiply).

Module[{a = 0}, Join[{a}, Flatten[Array[{a *= #, a += #} &, 20]]]] (* Paolo Xausa, Oct 24 2024 *)

a(n)=if(n<2,0,if(n%2,(n+1)/2*(floor(exp(1)*((n-1)/2)!)-1),floor(exp(1)*(n/2)!)-1))

A082458(n,a=0)={for(i=2,n+1,if(bittest(i,0),a+=i\2,a*=i\2));a} \\ M. F. Hasler, Feb 25 2018

For n>=2, a(2n)=floor(e*n!)-1, a(2*n+1)=(n+1)*(floor(e*n!)-1). - Benoit Cloitre, Apr 28 2003

Edited by M. F. Hasler, Feb 25 2018

A291203 Number F(n,h,t) of forests of t labeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 1, 0, 3, 6, 0, 6, 0, 0, 0, 0, 0, 1, 0, 4, 24, 12, 0, 36, 24, 0, 24, 0, 0, 0, 0, 0, 0, 1, 0, 5, 80, 90, 20, 0, 200, 300, 60, 0, 300, 120, 0, 120, 0, 0, 0, 0, 0, 0, 0, 1, 0, 6, 240, 540, 240, 30, 0, 1170, 3000, 1260, 120, 0, 3360, 2520, 360, 0, 2520, 720, 0, 720, 0

Offset: 0

Alois P. Heinz, Aug 20 2017

Positive elements in column t=1 give A034855.
Elements in rows h=0 give A023531.
Elements in rows h=1 give A059297.
Positive row sums per layer give A235595.
Positive column sums per layer give A061356.

			n h\t: 0   1   2  3  4 5 : A235595 : A061356          : A000272
-----+-------------------+---------+------------------+--------
0 0  : 1                 :         :                  : 1
-----+-------------------+---------+------------------+--------
1 0  : 0   1             :      1  :   .              :
1 1  : 0                 :         :   1              : 1
-----+-------------------+---------+------------------+--------
2 0  : 0   0   1         :      1  :   .   .          :
2 1  : 0   2             :      2  :   .              :
2 2  : 0                 :         :   2   1          : 3
-----+-------------------+---------+------------------+--------
3 0  : 0   0   0  1      :      1  :   .   .   .      :
3 1  : 0   3   6         :      9  :   .   .          :
3 2  : 0   6             :      6  :   .              :
3 3  : 0                 :         :   9   6   1      : 16
-----+-------------------+---------+------------------+--------
4 0  : 0   0   0  0  1   :      1  :   .   .   .  .   :
4 1  : 0   4  24 12      :     40  :   .   .   .      :
4 2  : 0  36  24         :     60  :   .   .          :
4 3  : 0  24             :     24  :   .              :
4 4  : 0                 :         :  64  48  12  1   : 125
-----+-------------------+---------+------------------+--------
5 0  : 0   0   0  0  0 1 :      1  :   .   .   .  . . :
5 1  : 0   5  80 90 20   :    195  :   .   .   .  .   :
5 2  : 0 200 300 60      :    560  :   .   .   .      :
5 3  : 0 300 120         :    420  :   .   .          :
5 4  : 0 120             :    120  :   .              :
5 5  : 0                 :         : 625 500 150 20 1 : 1296
-----+-------------------+---------+------------------+--------

Alois P. Heinz, Layers n = 0..48, flattened

Cf. A000007, A000012, A000142, A000272, A000551, A001477, A001788, A001854, A002378, A023531, A034855, A038154, A059297, A061356, A089946, A126804, A234953, A235595, A235596, A243014, A291204, A291336, A291529.

b:= proc(n, t, h) option remember; expand(`if`(n=0 or h=0, x^(t*n), add(
       binomial(n-1, j-1)*j*x^t*b(j-1, 0, h-1)*b(n-j, t, h), j=1..n)))
    end:
g:= (n, h)-> b(n, 1, h)-`if`(h=0, 0, b(n, 1, h-1)):
F:= (n, h, t)-> coeff(g(n, h), x, t):
seq(seq(seq(F(n, h, t), t=0..n-h), h=0..n), n=0..8);

b[n_, t_, h_] := b[n, t, h] = Expand[If[n == 0 || h == 0, x^(t*n), Sum[
     Binomial[n-1, j-1]*j*x^t*b[j-1, 0, h-1]*b[n-j, t, h], {j, 1, n}]]];
g[n_, h_] := b[n, 1, h] - If[h == 0, 0, b[n, 1, h - 1]];
F[n_, h_, t_] := Coefficient[g[n, h], x, t];
Table[Table[Table[F[n, h, t], {t, 0, n - h}], {h, 0, n}], {n, 0, 8}] // Flatten (* Jean-François Alcover, Mar 17 2022, after Alois P. Heinz *)

Sum_{i=0..n} F(n,i,n-i) = A243014(n) = 1 + A038154(n).
Sum_{d=0..n} Sum_{i=0..d} F(n,i,d-i) = A000272(n+1).
Sum_{h=0..n} Sum_{t=0..n-h} t * F(n,h,t) = A089946(n-1) for n>0.
Sum_{h=0..n} Sum_{t=0..n-h} (h+1) * F(n,h,t) = A234953(n+1) for n>0.
Sum_{h=0..n} Sum_{t=0..n-h} (h+1)*(n+1) * F(n,h,t) = A001854(n+1) for n>0.
Sum_{t=0..n-1} F(n,1,t) = A235596(n+1).
F(2n,n,n) = A126804(n) for n>0.
F(n,0,n) = 1 = A000012(n).
F(n,1,1) = n = A001477(n) for n>1.
F(n,n-1,1) = n! = A000142(n) for n>0.
F(n,1,n-1) = A002378(n-1) for n>0.
F(n,2,1) = A000551(n).
F(n,3,1) = A000552(n).
F(n,4,1) = A000553(n).
F(n,1,2) = A001788(n-1) for n>2.
F(n,0,0) = A000007(n).

A243014 Number of acyclic digraphs (DAGS) on n labeled nodes, where the indegree and outdegree of each node is at most 1.

Original entry on oeis.org

1, 1, 3, 13, 61, 321, 1951, 13693, 109593, 986401, 9864091, 108505101, 1302061333, 16926797473, 236975164791, 3554627472061, 56874039553201, 966858672404673, 17403456103284403, 330665665962403981, 6613313319248079981, 138879579704209680001

Offset: 0

Shuaib Ahmed S, May 29 2014

nonn

a(n) is the number of acyclic digraphs (DAGS) on n labeled nodes, where the indegree and outdegree of each node is at most 1. For example, with vertex set {A,B,C} the possible ways are: one 3-component graph {A,B,C}, six 2-component graph {{A->B,C},{B->A,C},{A->C,B},{C->A,B},{C->B,A},{B->C,A}}, and six 1-component graph {{A->B->C},{B->A->C},{A->C->B},{C->A->B},{C->B->A},{B->C->A}}.

Alois P. Heinz, Table of n, a(n) for n = 0..449
Eric Weisstein's World of Mathematics, Acyclic Digraph.
Index entries for sequences related to digraphs (or directed graphs)

Cf. A003024, A038154.

@(n)(factorial(n)*sum(1./(factorial(0:n-2)))+1)

a(n) = (n!*Sum(1/k!))+1, k=0..n-2.
a(n) = (n*(a(n-1)+n-2))+1,  for n>1, a(1)=1.
a(n) = A038154(n)+1.
E.g.f.: exp(x)*(x^2-x+1)/(1-x). - Alois P. Heinz, Aug 21 2017

a(0)=1 prepended, one term corrected, more terms added by Alois P. Heinz, Aug 21 2017

A141834 Sum of the lengths of the cycles at a vertex of the complete graph K_n.

Original entry on oeis.org

6, 42, 252, 1620, 11730, 95886, 876792, 8877672, 98640990, 1193556210, 15624736116, 220048367292, 3317652307242, 53319412081110, 909984632851440, 16436597430879696, 313262209859119542, 6282647653285675962

Offset: 3

Peter Bala, Jul 09 2008

In graph theory, a complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. The complete graph on n vertices is denoted by K_n. The number of simple cycles through a vertex of K_n equals A038154(n-1). See A000522 for the number of paths between a pair of distinct vertices of K_n.

			a(4) = 42. In the complete graph K_4 with vertex set {A,B,C,D} there are 12 simple cycles at the vertex A, namely the six 3-cycles ABCA, ABDA, ACBA, ACDA, ADBA and ADCA and the six 4-cycles ABCDA, ABDCA, ACBDA, ACDBA, ADBCA and ADCBA. The sum of the lengths of these cycles is 6*3 + 6*4 = 42.

Mehdi Hassani, Counting and computing by e

Cf. A000522, A038154.

a:= n -> 2 - 2*n + (n-1)*(n-1)!*add(1/k!,k = 0..n-1): seq(a(n), n = 3..22);

a(n) = floor(n!*e) - floor((n-1)!*e) - 2*n + 1 [Hassani]. a(n) = 2 - 2*n + (n-1)*(n-1)!*sum {k = 0..n-1} 1/k!. E.g.f.: sum {n = 0..inf} a(n+3)*x^n/n! = (6+12*x-21*x^2+8*x^3+3*x^4-2*x^5)*exp(x)/(1-x)^4 = 6 + 42*x + 252*x^2/2! + ... .

A367962 Triangle read by rows. T(n, k) = Sum_{j=0..k} (n!/j!).

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 6, 12, 15, 16, 24, 48, 60, 64, 65, 120, 240, 300, 320, 325, 326, 720, 1440, 1800, 1920, 1950, 1956, 1957, 5040, 10080, 12600, 13440, 13650, 13692, 13699, 13700, 40320, 80640, 100800, 107520, 109200, 109536, 109592, 109600, 109601

Offset: 0

Peter Luschny, Dec 06 2023

			  [0]   1;
  [1]   1,    2;
  [2]   2,    4,    5;
  [3]   6,   12,   15,   16;
  [4]  24,   48,   60,   64,   65;
  [5] 120,  240,  300,  320,  325,  326;
  [6] 720, 1440, 1800, 1920, 1950, 1956, 1957;

Cf. A094587, A000142 (T(n, 0)), A052849 (T(n, 1)), A000522 (T(n, n)), A007526 (T(n,n-1)), A038154 (T(n, n-2)), A355268 (T(n, n/2)), A367963(n) (T(2*n, n)/n!).

Cf. A001339 (row sums), A087208 (alternating row sums), A082030 (accumulated sums), A053482, A331689.

T := (n, k) -> add(n!/j!, j = 0..k):
seq(seq(T(n, k), k = 0..n), n = 0..9);

Module[{n=1},NestList[Append[n#,1+Last[#]n++]&,{1},10]] (* or *)
Table[Sum[n!/j!,{j,0,k}],{n,0,10},{k,0,n}] (* Paolo Xausa, Dec 07 2023 *)

from functools import cache
@cache
def a_row(n: int) -> list[int]:
    if n == 0: return [1]
    row = a_row(n - 1) + [0]
    for k in range(n): row[k] *= n
    row[n] = row[n - 1] + 1
    return row

def T(n, k): return sum(falling_factorial(n, n - j) for j in range(k + 1))
for n in range(9): print([T(n, k) for k in range(n + 1)])

T(n, k) = A094587(n, k) * A000522(k).
T(n, k) = e * (n! / k!) * Gamma(k + 1, 1).
Sum_{k=0..n} T(n, k) * 2^(n - k) = A053482(n).
Sum_{k=0..n} T(n, k) * binomial(n, k) = A331689(n).
Recurrence: T(n, n) = T(n, n-1) + 1 starting with T(0, 0) = 1.
For k <> n: T(n, k) = n * T(n-1, k).

A119913 Number of directed simple cycles in the complete graph K_n.

Original entry on oeis.org

0, 0, 2, 14, 74, 394, 2344, 16036, 125628, 1112028, 10976118, 119481218, 1421542550, 18348340022, 255323504812, 3809950976872, 60683990530072, 1027542662934744, 18430998766219146, 349096664728623126, 6962409983976703106, 145841989688186383106

Offset: 1

Amir M. Ben-Amram (amirben(AT)mta.ac.il), Aug 02 2006

nonn

That is, the number of subsets of at least 3 elements out of n, ordered up to cyclic permutations.

For n > 2, also the number of undirected cycles in the n-barbell graph. - Eric W. Weisstein, Dec 14 2017

			a(4)=14 because there are 6 4-cycles and 8 3-cycles.

Eric Weisstein's World of Mathematics, Barbell Graph
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Graph Cycle

Cf. A038154.

Cf. A002807 (number of undirected cycles).

function a = an(n) s = 0; for i = 2:n-1 s = s+fix(exp(1)*factorial(i)); end a = s - (n+3)*(n-2)/2;

Table[n (2 HypergeometricPFQ[{1, 1, 1 - n}, {2}, -1] - n - 1)/2, {n, 20}] (* Eric W. Weisstein, Dec 14 2017 *)

a(n) = Sum_{k=3..n} C(n,k) * (k-1)!.
a(n) = Sum_{i=2..n-1} (floor(e*i!)) - (n+3)(n-2)/2.
a(n) = Sum_{k=1..n-1} A038154(k).
a(n) = 2*A002807(n). - Vladeta Jovovic, Aug 04 2006

More terms from Max Alekseyev, Jan 18 2012

cp's OEIS Frontend

A001339 a(n) = Sum_{k=0..n} (k+1)! binomial(n,k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A038155 a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A082458 Multiply by 1, add 1, multiply by 2, add 2, etc., starting with 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A291203 Number F(n,h,t) of forests of t labeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A243014 Number of acyclic digraphs (DAGS) on n labeled nodes, where the indegree and outdegree of each node is at most 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

MATLAB

Formula

Extensions

A141834 Sum of the lengths of the cycles at a vertex of the complete graph K_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A367962 Triangle read by rows. T(n, k) = Sum_{j=0..k} (n!/j!).