A277919 Triangle read by rows: CL(n,k) is the number of labeled subgraphs with k edges of the n-cycle C_n.

1, 1, 1, 3, 2, 1, 7, 6, 3, 1, 15, 16, 10, 4, 1, 31, 40, 30, 15, 5, 1, 63, 96, 84, 50, 21, 6, 1, 127, 224, 224, 154, 77, 28, 7, 1, 255, 512, 576, 448, 258, 112, 36, 8, 1, 511, 1152, 1440, 1248, 810, 405, 156, 45, 9, 1, 1023, 2560, 3520, 3360, 2420, 1362, 605, 210, 55, 10, 1

Offset

0,4

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Thomas Selig, Combinatorial aspects of sandpile models on wheel and fan graphs, arXiv:2202.06487 [math.CO], 2022.

Formula

The identity CL(n,k) = 2^(n-2*k) * CL(n,n-k) can be proved combinatorially.

G.f.: (1 - 2*x + 2*x^2)/((1-x)*(1 - y*x - 2*x + y*x^2)). - Andrew Howroyd, Sep 27 2019

Example

For row 3 of the triangle below: there are 7 labeled subgraphs of the triangle C_3 with 0 edges, 6 with 1 edge, 3 with 2 edges, and 1 with 3 edges (C_3 itself).
Triangle begins:
     1;
     1,    1;
     3,    2,    1;
     7,    6,    3,    1;
    15,   16,   10,    4,    1;
    31,   40,   30,   15,    5,    1;
    63,   96,   84,   50,   21,    6,   1;
   127,  224,  224,  154,   77,   28,   7,   1;
   255,  512,  576,  448,  258,  112,  36,   8,  1;
   511, 1152, 1440, 1248,  810,  405, 156,  45,  9,  1;
  1023, 2560, 3520, 3360, 2420, 1362, 605, 210, 55, 10, 1;
  ...

Prog

(PARI) T(n)={[Vecrev(p) | p<-Vec((1 - 2*x + 2*x^2)/((1-x)*(1 - y*x - 2*x + y*x^2)) + O(x*x^n))]}
{ my(A=T(12)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Sep 27 2019

Crossrefs

Row sums give A005592.

Middle diagonal gives A110170.

Sequence in context: A129689 A115990 A350571 * A094531 A274293 A161009

Adjacent sequences: A277916 A277917 A277918 * A277920 A277921 A277922

Keyword

nonn,tabl

Author

John P. McSorley, Nov 03 2016

Extensions

More terms from John P. McSorley, Nov 17 2016

Status

approved