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
Examples
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; ...
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.
Programs
-
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 *) -
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
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
Extensions
Terms corrected and extended by Michael A. Allen, Dec 27 2021
Comments