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

Author

Alois P. Heinz, Sep 12 2008

Keywords

• nonn
• tabl

Examples

			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;
  ...
		

Links

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

Crossrefs

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.

Programs

Maple

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);

Mathematica

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 *)

Formula

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