A348447 Irregular triangle read by rows: T(n,k) (n >= 0) is the number of ways of selecting k objects from n objects arranged in a circle with no two selected objects having unit separation (i.e. having exactly one object between them).

1, 1, 1, 1, 2, 1, 1, 3, 1, 4, 4, 1, 5, 5, 1, 6, 9, 1, 7, 14, 7, 1, 8, 20, 16, 4, 1, 9, 27, 30, 9, 1, 10, 35, 50, 25, 1, 11, 44, 77, 55, 11, 1, 12, 54, 112, 105, 36, 4, 1, 13, 65, 156, 182, 91, 13, 1, 14, 77, 210, 294, 196, 49, 1, 15, 90, 275, 450, 378, 140, 15

Offset

0,5

Comments

For odd n, T(n,k) is the number of independent vertex sets of size k in an n-cycle. For even n, T(n,k) is the number of independent vertex sets of size k in two disjoint (n/2)-cycles. Here, a cycle of length one or two is taken to be a path. - Andrew Howroyd, Jan 01 2024

Links

Andrew Howroyd, Table of n, a(n) for n = 0..2578 (rows 0..100)

John Konvalina, On the number of combinations without unit separation., Journal of Combinatorial Theory, Series A 31.2 (1981): 101-107. See Table II (which erroneously lacks the n=k=2 element).

Formula

G.f.: -3 + y*x + y*(2 + y)*x^2 + (4 - 3*x - y*x^3)/((1 + y*x^2)*(1 - x - y*x^2)). - Andrew Howroyd, Jan 01 2024

Example

Triangle begins:
  1;
  1,   1;
  1,   2,   1;
  1,   3;
  1,   4,   4;
  1,   5,   5;
  1,   6,   9;
  1,   7,  14,   7;
  1,   8,  20,  16,   4;
  1,   9,  27,  30,   9;
  1,  10,  35,  50,  25;
  1,  11,  44,  77,  55,  11;
  1,  12,  54, 112, 105,  36,   4;
  1,  13,  65, 156, 182,  91,  13;
  ...
If n = 2 and we call the objects 0 and 1, the permitted sets of objects are {}, {0}, {1}, and {0,1}. If n = 3 and we call the objects 0, 1, and 2, then the permitted sets of objects are {}, {0}, {1}, and {2}; {0,1} is not a permitted set in this case since the objects lie in a circle and 2 lies between 0 and 1 in one direction. - Michael A. Allen, Apr 25 2022

Prog

(PARI) T(n) = {[Vecrev(p) | p <- Vec(-3 + y*x + y*(2 + y)*x^2 + (4 - 3*x - y*x^3)/((1 + y*x^2)*(1 - x - y*x^2)) + O(x*x^n))]}
{ my(A=T(10)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Jan 01 2024

Crossrefs

See A348445 for the case when the n objects are on a line.

The triangles A034807, A061896, A152060 are very similar.

The k=2 column is (essentially) A347553.

Sequence in context: A245717 A248008 A327981 * A277606 A228267 A170820

Adjacent sequences: A348444 A348445 A348446 * A348448 A348449 A348450

Keyword

nonn,tabf

Author

N. J. A. Sloane, Oct 23 2021

Extensions

Corrected by Michael A. Allen, Apr 25 2022

Terms a(56) and beyond from Andrew Howroyd, Jan 01 2024

Status

approved