A345123 Number T(n,k) of ordered subsequences of {1,...,n} containing at least k elements and such that the first differences contain only odd numbers; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 2, 1, 4, 3, 1, 7, 6, 3, 1, 12, 11, 7, 3, 1, 20, 19, 14, 8, 3, 1, 33, 32, 26, 17, 9, 3, 1, 54, 53, 46, 34, 20, 10, 3, 1, 88, 87, 79, 63, 43, 23, 11, 3, 1, 143, 142, 133, 113, 83, 53, 26, 12, 3, 1, 232, 231, 221, 196, 156, 106, 64, 29, 13, 3, 1, 376, 375, 364, 334, 279, 209, 132, 76, 32, 14, 3, 1

Offset: 0

Author

Alois P. Heinz, Jun 08 2021

Keywords

• nonn
• tabl

Comments

The sequence of column k satisfies a linear recurrence with constant coefficients of order 2k if k >= 2 and of order 3 for k in {0, 1}.

Examples

			T(0,0) = 1: [].
T(1,1) = 1: [1].
T(2,2) = 1: [1,2].
T(3,1) = 6: [1], [2], [3], [1,2], [2,3], [1,2,3].
T(4,0) = 12: [], [1], [2], [3], [4], [1,2], [1,4], [2,3], [3,4], [1,2,3], [2,3,4], [1,2,3,4].
T(6,3) = 17: [1,2,3], [1,2,5], [1,4,5], [2,3,4], [2,3,6], [2,5,6], [3,4,5], [4,5,6], [1,2,3,4], [1,2,3,6], [1,2,5,6], [1,4,5,6], [2,3,4,5], [3,4,5,6], [1,2,3,4,5], [2,3,4,5,6], [1,2,3,4,5,6].
Triangle T(n,k) begins:
    1;
    2,   1;
    4,   3,   1;
    7,   6,   3,   1;
   12,  11,   7,   3,   1;
   20,  19,  14,   8,   3,   1;
   33,  32,  26,  17,   9,   3,  1;
   54,  53,  46,  34,  20,  10,  3,  1;
   88,  87,  79,  63,  43,  23, 11,  3,  1;
  143, 142, 133, 113,  83,  53, 26, 12,  3, 1;
  232, 231, 221, 196, 156, 106, 64, 29, 13, 3, 1;
  ...
		

References

• Chu, Hung Viet, Various Sequences from Counting Subsets, Fib. Quart., 59:2 (May 2021), 150-157.

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• Chu, Hung Viet, Various Sequences from Counting Subsets, arXiv:2005.10081 [math.CO], 2021.

Crossrefs

Columns k=0-3 give: A000071(n+3), A001911, A001924(n-1), A344004.

T(2n,n) give A340766.

Cf. A073044, A105438.

Programs

Maple

b:= proc(n, l, t) option remember; `if`(n=0, `if`(t=0, 1, 0), `if`(0
      in [l, irem(1+l-n, 2)], b(n-1, n, max(0, t-1)), 0)+b(n-1, l, t))
    end:
T:= (n, k)-> b(n, 0, k):
seq(seq(T(n, k), k=0..n), n=0..10);
# second Maple program:
g:= proc(n, k) option remember; `if`(k>n, 0,
     `if`(k in [0, 1], n^k, g(n-1, k-1)+g(n-2, k)))
    end:
T:= proc(n, k) option remember;
     `if`(k>n, 0, g(n, k)+T(n, k+1))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);
# third Maple program:
T:= proc(n, k) option remember; `if`(k>n, 0, binomial(iquo(n+k, 2), k)+
      `if`(k>0, binomial(iquo(n+k-1, 2), k), 0)+T(n, k+1))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);

Mathematica

T[n_, k_] := T[n, k] = If[k > n, 0, Binomial[Quotient[n+k, 2], k] +
     If[k > 0, Binomial[Quotient[n+k-1, 2], k], 0] + T[n, k+1]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 11}] // Flatten (* Jean-François Alcover, Nov 06 2021, after 3rd Maple program *)