A093729 - OEIS

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.

%I #28 Aug 27 2024 22:20:10

%S 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,

%T 6377,6377,1656,274,40,6,1,0,171886,171886,36987,4721,515,57,7,1,0,

%U 7892642,7892642,1391106,134899,10810,867,77,8,1,0,627340987,627340987,89574978,6501536,376175,21456,1351,100,9,1

%N 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.

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

%C 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.

%H G. C. Greubel, <a href="/A093729/b093729.txt">Antidiagonals n = 0..50, flattened</a>

%H M. Cook and M. Kleber, <a href="https://doi.org/10.37236/1522">Tournament sequences and Meeussen sequences</a>, Electronic J. Comb. 7 (2000), #R44.

%H Michael Somos, <a href="https://math.stackexchange.com/q/477910">A functional power series equation</a>, Mathematics StackExchange answer.

%F 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).

%F 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.

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

%e Array begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, ...],

%e 0, 1, 2, 3, 4, 5, 6, 7, 8, ...],

%e 0, 2, 7, 15, 26, 40, 57, 77, 100, ...],

%e 0, 7, 41, 123, 274, 515, 867, 1351, 1988, ...],

%e 0, 41, 397, 1656, 4721, 10810, 21456, 38507, 64126, ...],

%e 0, 397, 6377, 36987, 134899, 376175, 880032, .................],

%e 0, 6377, 171886, 1391106, 6501536, ...],

%e 0, 171886, 7892642, .....................];

%e Antidiagonals begin as:

%e 1;

%e 0, 1;

%e 0, 1, 1;

%e 0, 2, 2, 1;

%e 0, 7, 7, 3, 1;

%e 0, 41, 41, 15, 4, 1;

%e 0, 397, 397, 123, 26, 5, 1;

%e 0, 6377, 6377, 1656, 274, 40, 6, 1;

%e 0, 171886, 171886, 36987, 4721, 515, 57, 7, 1;

%t 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. *)

%o (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))))))}

%o (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 */

%o (SageMath)

%o @CachedFunction

%o def T(n, k):

%o if n<0: return 0

%o elif n==0: return 1

%o elif k==0: return 0

%o elif k<n+1: return T(n,k-1) - T(n-1,k) + T(n-1,2*k-1) + T(n-1,2*k)

%o else: return sum((-1)^(j-1)*binomial(n+1,j)*T(n, k-j) for j in range(1,n+2))

%o def A093729(n,k): return T(n-k,k)

%o flatten([[A093729(n,k) for k in range(n+1)] for n in range(16)]) # _G. C. Greubel_, Feb 22 2024

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

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

%K nonn,tabl

%O 0,8

%A _Paul D. Hanna_, Apr 14 2004; revised Oct 14 2005