A093729 Square table T, read by antidiagonals, where T(n,k) gives the number of n-th generation descendents of a node labeled (k) in the tree of tournament sequences.

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 7, 7, 3, 1, 0, 41, 41, 15, 4, 1, 0, 397, 397, 123, 26, 5, 1, 0, 6377, 6377, 1656, 274, 40, 6, 1, 0, 171886, 171886, 36987, 4721, 515, 57, 7, 1, 0, 7892642, 7892642, 1391106, 134899, 10810, 867, 77, 8, 1, 0, 627340987, 627340987, 89574978, 6501536, 376175, 21456, 1351, 100, 9, 1

Offset

0,8

Comments

Column 1, of array T and antidiagonals, equals A008934, which is the number of tournament sequences.

A tournament sequence is an increasing sequence of positive integers (t_1,t_2,...) such that t_1 = 1 and t_{i+1} <= 2*t_i, where integer k>1.

Links

G. C. Greubel, Antidiagonals n = 0..50, flattened

M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.

Michael Somos, A functional power series equation, Mathematics StackExchange answer.

Formula

T(0, k)=1 for k>=0, T(n, 0)=0 for n>=1; else T(n, k) = T(n, k-1) - T(n-1, k) + T(n-1, 2*k-1) + T(n-1, 2*k) for k<=n; else T(n, k) = Sum_{j=1..n+1} (-1)^(j-1)*C(n+1, j)*T(n, k-j) for k>n (Cook-Kleber).

Column k of T equals column 0 of the matrix k-th power of triangle A097710, which satisfies the matrix recurrence: A097710(n, k) = [A097710^2](n-1, k-1) + [A097710^2](n-1, k) for n>k>=0.

Sum_{k=0..n} T(n-k, k) = A093730(n) (antidiagonal row sums).

Example

Array begins:
  1,      1,       1,       1,       1,      1,      1,     1,     1, ...],
  0,      1,       2,       3,       4,      5,      6,     7,     8, ...],
  0,      2,       7,      15,      26,     40,     57,    77,   100, ...],
  0,      7,      41,     123,     274,    515,    867,  1351,  1988, ...],
  0,     41,     397,    1656,    4721,  10810,  21456, 38507, 64126, ...],
  0,    397,    6377,   36987,  134899, 376175, 880032, .................],
  0,   6377,  171886, 1391106, 6501536, ...],
  0, 171886, 7892642, .....................];
Antidiagonals begin as:
  1;
  0,      1;
  0,      1,      1;
  0,      2,      2,     1;
  0,      7,      7,     3,    1;
  0,     41,     41,    15,    4,   1;
  0,    397,    397,   123,   26,   5,   1;
  0,   6377,   6377,  1656,  274,  40,   6,   1;
  0, 171886, 171886, 36987, 4721, 515,  57,   7,   1;

Mathematica

t[n_?Negative, _] = 0; t[0, _] = 1; t[n_, k_] /; k <= n := t[n, k] = t[n, k - 1] - t[n-1, k] + t[n - 1, 2 k - 1] + t[n - 1, 2 k]; t[n_, k_] := t[n, k] = Sum[(-1)^(j - 1)*Binomial[n + 1, j]*t[n, k - j], {j, 1, n + 1}]; Flatten[Table[t[i - k, k - 1], {i, 10}, {k, i}]] (* Jean-François Alcover, May 31 2011, after PARI prog. *)

Prog

(PARI) {T(n, k)=if(n<0, 0, if(n==0, 1, if(k==0, 0, if(k<=n, T(n, k-1)-T(n-1, k)+T(n-1, 2*k-1)+T(n-1, 2*k), sum(j=1, n+1, (-1)^(j-1)*binomial(n+1, j)*T(n, k-j))))))}
(PARI) {a(n, m) = my(A=1); for(k=1, n, A = (A - q^k * r * subst( subst(A, q, q^2), r, r^2)) / (1-q); subst(subst(A, r, q^(m-1)), q, 1)}; /* Michael Somos, Jun 19 2017 */
(SageMath)
@CachedFunction
def T(n, k):
    if n<0: return 0
    elif n==0: return 1
    elif k==0: return 0
    elif k<n+1: return T(n, k-1) - T(n-1, k) + T(n-1, 2*k-1) + T(n-1, 2*k)
    else: return sum((-1)^(j-1)*binomial(n+1, j)*T(n, k-j) for j in range(1, n+2))
def A093729(n, k): return T(n-k, k)
flatten([[A093729(n, k) for k in range(n+1)] for n in range(16)]) # G. C. Greubel, Feb 22 2024

Crossrefs

Cf. A008934, A097710, A113080, A113081, A113092, A113103.

Cf. A008934 (column k=1 of array and antidiagonals), A093730 (antidiagonal row sums).

Sequence in context: A254883 A266599 A327365 * A113080 A174420 A360604

Adjacent sequences: A093726 A093727 A093728 * A093730 A093731 A093732

Keyword

nonn,tabl

Author

Paul D. Hanna, Apr 14 2004; revised Oct 14 2005

Status

approved