A348447 - OEIS

%I #30 Jan 01 2024 16:06:14

%S 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,

%T 10,35,50,25,1,11,44,77,55,11,1,12,54,112,105,36,4,1,13,65,156,182,91,

%U 13,1,14,77,210,294,196,49,1,15,90,275,450,378,140,15

%N 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).

%C 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

%H Andrew Howroyd, <a href="/A348447/b348447.txt">Table of n, a(n) for n = 0..2578</a> (rows 0..100)

%H John Konvalina, <a href="https://doi.org/10.1016/0097-3165(81)90006-6">On the number of combinations without unit separation.</a>, Journal of Combinatorial Theory, Series A 31.2 (1981): 101-107. See Table II (which erroneously lacks the n=k=2 element).

%F 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

%e Triangle begins:

%e   1;

%e   1,   1;

%e   1,   2,   1;

%e   1,   3;

%e   1,   4,   4;

%e   1,   5,   5;

%e   1,   6,   9;

%e   1,   7,  14,   7;

%e   1,   8,  20,  16,   4;

%e   1,   9,  27,  30,   9;

%e   1,  10,  35,  50,  25;

%e   1,  11,  44,  77,  55,  11;

%e   1,  12,  54, 112, 105,  36,   4;

%e   1,  13,  65, 156, 182,  91,  13;

%e   ...

%e 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

%o (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))]}

%o { my(A=T(10)); for(i=1, #A, print(A[i])) } \\ _Andrew Howroyd_, Jan 01 2024

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

%Y The triangles A034807, A061896, A152060 are very similar.

%Y The k=2 column is (essentially) A347553.

%K nonn,tabf

%O 0,5

%A _N. J. A. Sloane_, Oct 23 2021

%E Corrected by _Michael A. Allen_, Apr 25 2022

%E Terms a(56) and beyond from _Andrew Howroyd_, Jan 01 2024