A002807 -id:A002807 - cp's OEIS frontend

A144151 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of ways an undirected cycle of length k can be built from n labeled nodes.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 3, 1, 5, 10, 10, 15, 12, 1, 6, 15, 20, 45, 72, 60, 1, 7, 21, 35, 105, 252, 420, 360, 1, 8, 28, 56, 210, 672, 1680, 2880, 2520, 1, 9, 36, 84, 378, 1512, 5040, 12960, 22680, 20160, 1, 10, 45, 120, 630, 3024, 12600, 43200, 113400, 201600, 181440

Offset: 0

Alois P. Heinz, Sep 12 2008

			T(4,3) = 4, because 4 undirected cycles of length 3 can be built from 4 labeled nodes:
  .1.2. .1.2. .1-2. .1-2.
  ../|. .|\.. ..\|. .|/..
  .3-4. .3-4. .3.4. .3.4.
Triangle begins:
  1;
  1, 1;
  1, 2,  1;
  1, 3,  3,  1;
  1, 4,  6,  4,  3;
  1, 5, 10, 10, 15, 12;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns 0-4 give: A000012, A000027, A000217, A000292, A050534.
Diagonal gives: A001710.
Cf. A000142, A007318.
Row sums are in A116723. - Alois P. Heinz, Jun 01 2009
Excluding columns k=0,1,and 2 the row sums are A002807. - Geoffrey Critzer, Jul 22 2016
Cf. A284947 (k-cycle counts for k >= 3 in the complete graph K_n). - Eric W. Weisstein, Apr 06 2017
T(2n,n) gives A006963(n+1) for n>=3.

T:= (n,k)-> if k<=2 then binomial(n,k) else mul(n-j, j=0..k-1)/k/2 fi:
seq(seq(T(n,k), k=0..n), n=0..12);

t[n_, k_ /; k <= 2] := Binomial[n, k]; t[n_, k_] := Binomial[n, k]*(k-1)!/2; Table[t[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 18 2013 *)
CoefficientList[Table[1 + n x (2 + (n - 1) x + 2 HypergeometricPFQ[{1, 1, 1 - n}, {2}, -x])/4, {n, 0, 10}], x] (* Eric W. Weisstein, Apr 06 2017 *)

T(n,k) = C(n,k) if k<=2, else T(n,k) = C(n,k)*(k-1)!/2.

E.g.f.: exp(x)*(log(1/(1 - y*x))/2 + 1 + y*x/2 + (y*x)^2/4). - Geoffrey Critzer, Jul 22 2016

A070968 Number of cycles in the complete bipartite graph K(n,n).

Original entry on oeis.org

0, 1, 15, 204, 3940, 113865, 4662231, 256485040, 18226108944, 1623855701385, 177195820499335, 23237493232953516, 3605437233380095620, 653193551573628900289, 136634950180317224866335, 32681589590709963123092160, 8863149183726257535369633856

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), May 17 2002

nonn

Also the number of chordless cycles in the n X n rook graph. - Eric W. Weisstein, Nov 27 2017

Andrew Howroyd, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Rook Graph

Row sums of A291909.
Main diagonal of A360849.
Cf. A002807, A068087, A288035.

seq(simplify((1/4)*hypergeom([1, 2, 2-n, 2-n], [3], 1)*(n-1)^2*n^2), n=1..20); # Robert Israel, Jan 09 2018

Table[Sum[Binomial[n, k]^2*k!*(k - 1)!, {k, 2, n}]/2, {n, 1, 17}]
Table[n^2 (HypergeometricPFQ[{1, 1, 1 - n, 1 - n}, {2}, 1] - 1)/2, {n, 20}] (* Eric W. Weisstein, Dec 14 2017 *)

for(n=1,50,print1(sum(k=2,n,binomial(n,k)^2 * k! * (k-1)!/2),","))

a(n) = Sum_{k=2..n} C(n,k)^2 * k! * (k-1)! / 2.
Recurrence: (n-2)^2*(2*n^3 - 19*n^2 + 58*n - 59)*a(n) = 2*(2*n^7 - 31*n^6 + 200*n^5 - 700*n^4 + 1442*n^3 - 1764*n^2 + 1205*n - 363)*a(n-1) - (n-1)^2*(2*n^7 - 35*n^6 + 266*n^5 - 1139*n^4 + 2962*n^3 - 4671*n^2 + 4130*n - 1578)*a(n-2) + 2*(n-2)^2*(n-1)^2*(2*n^5 - 26*n^4 + 134*n^3 - 342*n^2 + 431*n - 217)*a(n-3) - (n-3)^2*(n-2)^2*(n-1)^2*(2*n^3 - 13*n^2 + 26*n - 18)*a(n-4). - Vaclav Kotesovec, Mar 08 2016
a(n) ~ c * n! * (n-1)!, where c = BesselI(0,2)/2 = 1.1397926511680336337186... . - Vaclav Kotesovec, Mar 08 2016

More terms from Benoit Cloitre and Robert G. Wilson v, May 20 2002

a(16)-a(17) from Andrew Howroyd, Jan 08 2018

A286418 Array read by antidiagonals: T(n,m) is the number of (undirected) cycles in the rook graph K_n X K_m.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 7, 14, 14, 7, 37, 170, 312, 170, 37, 197, 2904, 13945, 13945, 2904, 197, 1172, 74779, 1241696, 3228524, 1241696, 74779, 1172, 8018, 2751790, 196846257, 1723178763, 1723178763, 196846257, 2751790, 8018

Offset: 1

Andrew Howroyd, May 08 2017

			Table starts:
================================================
m\n  1    2       3          4             5
--+---------------------------------------------
1 |  0    0       1          7            37 ...
2 |  0    1      14        170          2904 ...
3 |  1   14     312      13945       1241696 ...
4 |  7  170   13945    3228524    1723178763 ...
5 | 37 2904 1241696 1723178763 6198979538330 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..78
Eric Weisstein's World of Mathematics, Graph Cycle, Rook Graph

Main diagonal is A234624.
Columns 1..3 are A002807, A341500, A341501.
Cf. A269562, A269565.

A297670 Number of chordless cycles in the n-triangular graph.

Original entry on oeis.org

0, 0, 3, 27, 177, 1137, 7962, 62730, 555894, 5487894, 59740389, 710770989, 9174169647, 127661751951, 1904975487876, 30341995264356, 513771331466556, 9215499383108604, 174548332364310423, 3481204991988350223, 72920994844093190013, 1600596371590399670013

Offset: 2

Eric W. Weisstein, Jan 02 2018

nonn

			From _Andrew Howroyd_, Jan 04 2018: (Start)
Vertices can be represented by a pair of integers with 12 being the same as 21.
a(4) = 3 because the possible cycles are: -12-23-34-41-, -12-24-43-31-, -13-32-24-41-.
a(5) = 27 because there are 15 cycles of length 4 and 12 cycles of length 5.
(End)

Andrew Howroyd, Table of n, a(n) for n = 2..200
Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Johnson Graph
Eric Weisstein's World of Mathematics, Triangular Graph

Cf. A000292, A002807, A129349, A234629.

A297670List := proc(n) local A,R,f,i; A:=[0,0,0,6,54,354,2274]; R:=NULL;
f := i -> (24*(12*A[1]-33*A[2]+23*A[3]+3*A[4]-5*A[5])-(4*(90*A[1]-255*A[2]
+212*A[3]-26*A[4]-31*A[5]+16*A[6])+(-208*A[1]+618*A[2]-604*A[3]+197*A[4]
+15*A[5]-35*A[6]+(82*A[1]-257*A[2]+285*A[3]-137*A[4]+27*A[5]+6*A[6]+
(-20*A[1]+66*A[2]-83*A[3]+52*A[4]-18*A[5]+2*A[6]+(+2*A[1]-7*A[2]+10*A[3]
-8*A[4]+4*A[5]-A[6])*i)*i)*i)*i)*i)/((-24+(17+(i-6)*i)*i)*i);
for i from 1 to n do if i<7 then R:=R,A[i+1]/2 else A[1]:=A[2];A[2]:=A[3];
A[3]:=A[4];A[4]:=A[5];A[5]:=A[6];A[6]:=A[7];A[7]:=f(i); R:=R,A[7]/2 fi od;
R end: A297670List(22); # Peter Luschny, Jan 06 2018

Table[Sum[n!/(2 k (n - k)!), {k, 4, n}], {n, 2, 20}]
Table[n ((3 - 2 n) n + 6 HypergeometricPFQ[{1, 1, 1 - n}, {2}, -1] - 7)/12, {n, 2, 20}]
RecurrenceTable[{-(-1 + n) n (1 + n) + (4 + 2 (-1 + n)) a[n] + (-6 - 2 (-1 + n)) a[n + 1] + 2 a[n + 2] == 0, a[1] == 0, a[2] == 0}, a[n], {n, 2, 20}]

a(n)={sum(k=4, n, n!/(2*k*(n-k)!))} \\ Andrew Howroyd, Jan 04 2018

a(n) = Sum_{k=4..n} n!/(2*k*(n-k)!). - Andrew Howroyd, Jan 04 2018
a(n) = n*((3 - 2*n)*n + 6*Hypergeometric3F1[1, 1, 1 - n; 2; -1] - 7)/12. - Eric W. Weisstein, Jan 05 2018
-(-1 + n)*n*(1 + n) + (4 + 2*(-1 + n))*a(n) + (-6 - 2*(-1 + n))*a(n + 1) + 2*a(n + 2) = 0. - Eric W. Weisstein, Jan 07 2018
a(n) = A002807(n) - A000292(n-2). - Pontus von Brömssen, Apr 29 2023

Terms a(8) and beyond from Andrew Howroyd, Jan 04 2018

A234627 Numbers of undirected cycles in the n-sun graph.

Original entry on oeis.org

1, 3, 11, 44, 198, 1036, 6346, 45019, 364039, 3306553, 33328389, 369132782, 4456043300, 58230679722, 818965960156, 12334276322245, 198059886271741, 3377876368962559, 60978094460613103, 1161619710523459392

Offset: 1

Eric W. Weisstein, Dec 28 2013

nonn

Extended to n=1 and 2 using the closed-form sum. - Eric W. Weisstein, May 04 2017

Andrew Howroyd and Vaclav Kotesovec, Table of n, a(n) for n = 1..420 (terms 3..50 from Andrew Howroyd; terms 1..2 corrected by _Georg Fischer_, Jan 20 2019)
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Sun Graph

Cf. A002807, A192856.

Table[(2 - Binomial[n + 1, 2] + Sum[(k - 1)! (Binomial[n, k] + Sum[n 2^j Binomial[n - j - i - 1, j - 1] Binomial[i + j - 1, i] Binomial[n - 2 j - i, k - j]/j, {j, k}, {i, 0, n - j - k}]), {k, n}])/2, {n, 20}] (* Eric W. Weisstein, Dec 14 2017 *)

a(n) = (2 - binomial(n+1, 2) + sum(k=1, n, (k-1)! * (binomial(n, k) + sum(j=1, k, sum(i=0, n-j-k, n*(2^j)*binomial(n-j-i-1, j-1)*binomial(i+j-1, i)*binomial(n-2*j-i, k-j)/j)))))/2; \\ after formula; Michel Marcus, Mar 06 2016

a(n) = (1/2) * (2 - binomial(n+1, 2) + Sum_{k=1..n} (k-1)! * (binomial(n, k) + Sum_{j=1..k} Sum_{i=0..n-j-k} n*(2^j)*binomial(n-j-i-1, j-1)*binomial(i+j-1, i)*binomial(n-2*j-i, k-j)/j) ). - Andrew Howroyd, Mar 05 2016

a(n) ~ exp(3)/2 * (n-1)!. - Vaclav Kotesovec, Mar 06 2016

a(12)-a(14) from Eric W. Weisstein, Apr 09 2014

a(15)-a(20) from Andrew Howroyd, Mar 05 2016

A284947 Irregular triangle read by rows: coefficients of the cycle polynomial of the n-complete graph K_n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 4, 3, 0, 0, 0, 10, 15, 12, 0, 0, 0, 20, 45, 72, 60, 0, 0, 0, 35, 105, 252, 420, 360, 0, 0, 0, 56, 210, 672, 1680, 2880, 2520, 0, 0, 0, 84, 378, 1512, 5040, 12960, 22680, 20160, 0, 0, 0, 120, 630, 3024, 12600, 43200, 113400, 201600, 181440

Offset: 3

Eric W. Weisstein, Apr 06 2017

			1: 0
2: 0
3: x^3
4: x^3 (4 + 3 x)
5: x^3 (10 + 15 x + 12 x^2)
6: x^3 (20 + 45 x + 72 x^2 + 60 x^3)
giving
1 3-cycle in K_3
4 3-cycles and 3 4-cycles in K_4
From _Peter Luschny_, Oct 22 2017: (Start)
Prepending six zeros leads to the regular triangle:
[0] 0
[1] 0, 0
[2] 0, 0, 0
[3] 0, 0, 0,  1
[4] 0, 0, 0,  4,   3
[5] 0, 0, 0, 10,  15,   12
[6] 0, 0, 0, 20,  45,   72,   60
[7] 0, 0, 0, 35, 105,  252,  420,   360
[8] 0, 0, 0, 56, 210,  672, 1680,  2880,  2520
[9] 0, 0, 0, 84, 378, 1512, 5040, 12960, 22680, 20160
(End)

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

Cf. A002807 (row sums of a(n)).

Cf. A144151 (generalization to include 1- and 2-"cycles").

A284947row := n -> seq(`if`(k<3, 0, pochhammer(3,k-3)*binomial(n,k)), k=0..n):
seq(A284947row(n), n=3..10); # Peter Luschny, Oct 22 2017

CoefficientList[Table[-(n*x*(2 - x + n*x - 2*HypergeometricPFQ[{1, 1, 1 - n}, {2}, -x]))/4, {n, 10}], x] // Flatten

T(n, k) = binomial(n, k)*Pochhammer(3, k-3) if k >= 3 else 0. - Peter Luschny, Oct 22 2017

A117130 Maximal number of cycles in complete graph on n nodes that can be unknotted when the graph is embedded in three-dimensional Euclidean space.

Original entry on oeis.org

0, 0, 0, 1, 7, 37, 197, 1171

Offset: 0

J. H. Conway, Apr 29 2006

For n <= 6 all cycles can be unknotted and the terms agree with A002807.

Cf. A002807.

A386399 Number of forests with at most n unlabeled nodes.

Original entry on oeis.org

1, 2, 4, 7, 13, 23, 43, 80, 156, 309, 638, 1348, 2949, 6607, 15206, 35720, 85625, 208588, 515787, 1291316, 3269194, 8355832, 21539988, 55942920, 146271594, 384746580, 1017522228, 2704227858, 7219183490, 19351410860, 52068524665, 140588391713, 380824067016

Offset: 0

Max Alekseyev, Jul 20 2025

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Partial sums of A005195.

Cf. A000272, A002807, A006897, A054548, A137917, A367863, A372176.

G.f.: exp(sum_{k>0} B(x^k)/k ) / (1-x), where B(x) = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + ... = C(x)-1 and C is the g.f. for A000055.

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

A289896 Number of (undirected) cycles in the n-triangular honeycomb rook graph.

Original entry on oeis.org

0, 0, 1, 8, 45, 242, 1414, 9432, 72246, 628260, 6116319, 65856928, 776628203, 9950798214, 137612550620, 2042588039056, 32384583304092, 546155914771464, 9761655297881037, 184309987662192600, 3665514979650544153, 76586509823743735706, 1677182881414143407490

Offset: 1

Eric W. Weisstein, Jul 14 2017

nonn

Eric Weisstein's World of Mathematics, Graph Cycle

Cf. A002807 (cycles in the complete graph).

Table[Sum[Binomial[k, l] (l - 1)!, {k, n}, {l, 3, k}]/2, {n, 20}]
Table[Sum[k (2 HypergeometricPFQ[{1, 1, 1 - k}, {2}, -1] - k - 1)/4, {k, n}], {n, 20}]

a(n) = sum(k=1..n,A002807(k)).

a(n) ~ exp(1) * (n-1)! / 2. - Vaclav Kotesovec, Jun 09 2019

cp's OEIS Frontend

A144151 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of ways an undirected cycle of length k can be built from n labeled nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A070968 Number of cycles in the complete bipartite graph K(n,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A286418 Array read by antidiagonals: T(n,m) is the number of (undirected) cycles in the rook graph K_n X K_m.

Views

Author

Keywords

Examples

Links

Crossrefs

A297670 Number of chordless cycles in the n-triangular graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A234627 Numbers of undirected cycles in the n-sun graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A284947 Irregular triangle read by rows: coefficients of the cycle polynomial of the n-complete graph K_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A117130 Maximal number of cycles in complete graph on n nodes that can be unknotted when the graph is embedded in three-dimensional Euclidean space.

Views

Author

Keywords

Comments

Crossrefs

A386399 Number of forests with at most n unlabeled nodes.

Views

Author

Keywords

Links

Crossrefs