A284947 -id:A284947 - cp's OEIS frontend

A002807 a(n) = Sum_{k=3..n} (k-1)!*C(n,k)/2.

0, 0, 0, 1, 7, 37, 197, 1172, 8018, 62814, 556014, 5488059, 59740609, 710771275, 9174170011, 127661752406, 1904975488436, 30341995265036, 513771331467372, 9215499383109573, 174548332364311563, 3481204991988351553, 72920994844093191553, 1600596371590399671784

Offset: 0

N. J. A. Sloane

Number of cycles in the complete graph on n nodes K_{n}. - Erich Friedman
Number of equations that must be checked to verify reversibility of an n state Markov chain using the Kolmogorov criterion. - Qian Jiang (jiang1h(AT)uwindsor.ca), Jun 08 2009
Also the number of paths in the (n-1)-triangular honeycomb rook graph. - Eric W. Weisstein, Jul 14 2017

E.P.C. Kao, An Introduction to Stochastic Processes, Duxbury Press, 1997, 209-210. [From Qian Jiang (jiang1h(AT)uwindsor.ca), Jun 08 2009]
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).

T. D. Noe, Table of n, a(n) for n = 0..100
P. H. Brill, Chi ho Cheung, Myron Hlynka, Q. Jiang, Reversibility Checking for Markov Chains, Communications on Stochastic Analysis (2018) Vol. 12, No. 2, Art. 2, 129-135.
J. P. Char, Master circuit matrix, Proc. IEE, 115 (1968), 762-770.
F. C. Holroyd and W. J. G. Wingate, Cycles in the complement of a tree or other graph, Discrete Math., 55 (1985), 267-282.
Q. Jiang, M. Hlynka, P.H. Brill, C.H. Cheung, Reversibility Checking for Markov Chains, arXiv:1806.10154 [math.PR], 2018.
P. Pollack, Analytic and Combinatorial Number Theory Course Notes, ch. 7. [?Broken link]
P. Pollack, Analytic and Combinatorial Number Theory Course Notes, ch. 7.
M. Scullard, Reversible Markov Chains [From Qian Jiang (jiang1h(AT)uwindsor.ca), Jun 08 2009]
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Graph Path

Cf. A284947 (triangle of k-cycle counts in K_n). - Eric W. Weisstein, Apr 06 2017

Cf. A117130, A099198, A099201, A070968.

[&+[Factorial(k-1)*Binomial(n,k) div 2: k in [3..n]]: n in [3..30]]; // Vincenzo Librandi, Mar 06 2016

Table[Sum[((k-1)!Binomial[n,k])/2,{k,3,n}],{n,0,25}] (* Harvey P. Dale, Jun 24 2011 *)
a[n_] := n/4*(2*HypergeometricPFQ[{1, 1, 1 - n}, {2}, -1] - n - 1); a[0] = 0; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Oct 05 2012 *)

a(n)=sum(k=3,n, (k-1)!*binomial(n,k)/2) \\ Charles R Greathouse IV, Feb 08 2017

E.g.f.: (-1/4)*exp(x)*(2*log(1-x)+2*x+x^2). - Vladeta Jovovic, Oct 26 2004
a(n) = (n-1)*(n-2)/2 + n*a(n-1) - (n-1)*a(n-2). - Vladeta Jovovic, Jan 22 2005
a(n) ~ exp(1)/2 * (n-1)! * (1 + 1/n + 2/n^2 + 5/n^3 + 15/n^4 + 52/n^5 + 203/n^6 + 877/n^7 + 4140/n^8 + 21147/n^9 + ...). Coefficients are the Bell numbers (A000110). - Vaclav Kotesovec, Mar 08 2016
For n>2, a(n) = Sum_{k=1..n-2} A000522(k-1)*A000217(k). - Vaclav Kotesovec, Mar 08 2016

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.

Original entry on oeis.org

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

cp's OEIS Frontend

A002807 a(n) = Sum_{k=3..n} (k-1)!*C(n,k)/2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula