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

1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 4, 4, 1, 5, 7, 2, 1, 6, 11, 6, 1, 1, 7, 16, 13, 3, 1, 8, 22, 24, 9, 1, 9, 29, 40, 22, 3, 1, 10, 37, 62, 46, 12, 1, 1, 11, 46, 91, 86, 34, 4, 1, 12, 56, 128, 148, 80, 16, 1, 13, 67, 174, 239, 166, 50, 4, 1, 14, 79, 230, 367, 314, 130, 20, 1, 1, 15, 92, 297, 541, 553, 296, 70, 5

Offset

0,5

Comments

Equivalently, T(n,k) is the number of independent vertex sets of size k in two disjoint paths, one of length floor(n/2) and the other of length ceiling(n/2). - Andrew Howroyd, Jan 01 2024

Links

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

Kenneth Edwards and Michael A. Allen, New Combinatorial Interpretations of the Fibonacci Numbers Squared, Golden Rectangle Numbers, and Jacobsthal Numbers Using Two Types of Tile, arXiv:2009.04649 [math.CO], 2020.

Kenneth Edwards and Michael A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, J. Int. Seq. 24 (2021) Article 21.3.8.

John Konvalina, On the number of combinations without unit separation., Journal of Combinatorial Theory, Series A 31.2 (1981): 101-107. See Table I.

Formula

T(n,k) = A335964(n+2,k).

T(n,0) = 1.

T(n,1) = n.

T(1,k) = 0 if k>1.

T(n,k) = T(n-1,k) + T(n-3,k-1) + T(n-4,k-2).

G.f.: (1 + y*x + (y^2 + y)*x^2 + y^2*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,  2;
  1,  4,  4;
  1,  5,  7,  2;
  1,  6, 11,  6,  1;
  1,  7, 16, 13,  3;
  1,  8, 22, 24,  9;
  1,  9, 29, 40, 22,  3;
  ...

Mathematica

Flatten[Drop[CoefficientList[CoefficientList[Series[1/((1+x^2*y)(1-x-x^2*y)), {x, 0, 17}], x], y], 2]] (* Michael A. Allen, Dec 27 2021 *)

Prog

(PARI) T(n) = {[Vecrev(p) | p <- Vec((1 + y*x + (y^2 + y)*x^2 + y^2*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

Cf. A335964.

See A348447 for the circular case.

Sequence in context: A137569 A266715 A089177 * A023996 A307998 A355147

Adjacent sequences: A348442 A348443 A348444 * A348446 A348447 A348448

Keyword

nonn,tabf

Author

N. J. A. Sloane, Oct 22 2021

Extensions

Terms corrected and extended by Michael A. Allen, Dec 27 2021

Status

approved