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,2

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}.

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.

Example

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;
  ...

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 *)

Crossrefs

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

T(2n,n) give A340766.

Cf. A073044, A105438.

Sequence in context: A048790 A027421 A131252 * A133805 A131254 A210229

Adjacent sequences: A345120 A345121 A345122 * A345124 A345125 A345126

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 08 2021

Status

approved