A059516 -id:A059516 - cp's OEIS frontend

A316674 Number A(n,k) of paths from {0}^k to {n}^k that always move closer to {n}^k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 13, 26, 4, 1, 1, 75, 818, 252, 8, 1, 1, 541, 47834, 64324, 2568, 16, 1, 1, 4683, 4488722, 42725052, 5592968, 26928, 32, 1, 1, 47293, 617364026, 58555826884, 44418808968, 515092048, 287648, 64, 1

Offset: 0

Alois P. Heinz, Jul 10 2018

A(n,k) is the number of nonnegative integer matrices with k columns and any number of nonzero rows with column sums n. - Andrew Howroyd, Jan 23 2020

			Square array A(n,k) begins:
  1,  1,     1,         1,              1,                    1, ...
  1,  1,     3,        13,             75,                  541, ...
  1,  2,    26,       818,          47834,              4488722, ...
  1,  4,   252,     64324,       42725052,          58555826884, ...
  1,  8,  2568,   5592968,    44418808968,      936239675880968, ...
  1, 16, 26928, 515092048, 50363651248560, 16811849850663255376, ...

Alois P. Heinz, Antidiagonals n = 0..48, flattened

Columns k=0..3 give: A000012, A011782, A052141, A316673.
Rows n=0..2 give: A000012, A000670, A059516.
Main diagonal gives A316677.
Cf. A011782, A219727, A262809, A331315, A331485, A331636.

A:= (n, k)-> `if`(k=0, 1, ceil(2^(n-1))*add(add((-1)^i*
     binomial(j, i)*binomial(j-i, n)^k, i=0..j), j=0..k*n)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

A[n_, k_] := Sum[If[k == 0, 1, Binomial[j+n-1, n]^k] Sum[(-1)^(i-j)* Binomial[i, j], {i, j, n k}], {j, 0, n k}];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Nov 04 2021 *)

T(n,k)={my(m=n*k); sum(j=0, m, binomial(j+n-1,n)^k*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))} \\ Andrew Howroyd, Jan 23 2020

A(n,k) = A262809(n,k) * A011782(n) for k>0, A(n,0) = 1.

A(n,k) = Sum_{j=0..n*k} binomial(j+n-1,n)^k * Sum_{i=j..n*k} (-1)^(i-j) * binomial(i,j). - Andrew Howroyd, Jan 23 2020

A059515 Square array T(k,n) by antidiagonals, where T(k,n) is number of ways of placing n identifiable nonnegative intervals with a total of exactly k starting and/or finishing points.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 7, 1, 0, 0, 0, 12, 25, 1, 0, 0, 0, 6, 138, 79, 1, 0, 0, 0, 0, 294, 1056, 241, 1, 0, 0, 0, 0, 270, 5298, 7050, 727, 1, 0, 0, 0, 0, 90, 12780, 70350, 44472, 2185, 1, 0, 0, 0, 0, 0, 16020, 334710, 817746, 273378, 6559, 1, 0, 0, 0, 0, 0

Offset: 0

Henry Bottomley, Jan 19 2001

See A300729 for a triangular version of this array. - Peter Bala, Jun 13 2019

			Rows are: 1,0,0,0,0,..., 0,1,1,0,0,..., 0,1,7,12,6,..., 0,1,25,138,294,..., etc. T(1,1)=1 since if a is starting point of interval and A is end point then only possibility is aA (zero length). T(2,1)=1 since possibility is a-A (positive length). T(3,2)=12 since possibilities are: aA-b-B, b-aA-B, b-B-aA, bB-a-A, a-bB-A, a-A-bB, ab-A-B, ab-B-A, a-b-AB, b-a-AB, a-bA-B, b-a-AB.

IBM Ponder This, Jan 01 2001

Sum of rows gives A059516. Columns include A000007, A057427, A058481, A059117. Final positive number in each row is A000680.

Cf. A300729.

T(k, n) = T(k - 2, n - 1) * k * (k - 1)/2 + T(k - 1, n - 1) * k^2 + T(k, n - 1) * k * (k + 1)/2 with T(0, 0) = 1 = lambda(k, n) + lambda(k + 1, n) where lambda is A059117(k, n).

A300729 Number of arrangements on a line of n finite closed intervals (possibly of zero length) with k distinct endpoints (n >= 1, 1 <= k <= 2*n).

Original entry on oeis.org

1, 1, 1, 7, 12, 6, 1, 25, 138, 294, 270, 90, 1, 79, 1056, 5298, 12780, 16020, 10080, 2520, 1, 241, 7050, 70350, 334710, 875970, 1335600, 1184400, 567000, 113400, 1, 727, 44472, 817746, 6849900, 31500180, 87348240, 152643960, 169533000, 116235000, 44906400, 7484400

Offset: 1

Peter Bala, Mar 12 2018

A122193(n,k) equals the number of arrangements on a line of n (nondegenerate) finite closed intervals having k distinct endpoints. The entries T(n,k) of the present table satisfy T(n,k) = A122193(n,k) + A122193(n,k+1). Proof. In an arrangement contributing to T(n,k) either the intervals are all nondegenerate, and there are A122193(n,k) arrangements of this type, or at least one of the intervals in the arrangement is degenerate. The following argument to show there are A122193(n,k+1) arrangements of the latter type is taken from the solution to the problem posed in the 'IBM Ponder This' link.
In an arrangement of n nondegenerate finite closed intervals having k+1 distinct endpoints, the rightmost point is the right endpoint of one or more intervals. If we move each of these right endpoints to coincide with their corresponding left endpoint then we obtain an arrangement of n finite closed intervals with k distinct endpoints, where at least one of the intervals has zero length. The reverse mapping is clear: given an arrangement of n finite closed intervals with k distinct endpoints, where at least one of the intervals has zero length, take each interval of zero length and move all the right endpoints of these degenerate intervals to a single new rightmost point. This produces an arrangement of n nondegenerate finite closed intervals having k+1 distinct endpoints. (End proof)
Most of the properties of the present table now follow from the properties of A122193.
Reading the table by antidiagonals produces A059515.

			Table begins
      |k=0   1   2     3     4      5      6      7     8
---------------------------------------------------------
  n=0 |  1
    1 |  0   1   1
    2 |  0   1   7    12     6
    3 |  0   1  25   138   294    270     90
    4 |  0   1  79  1056  5298  12780  16020  10080  2520
   ...
T(2,3) = 12: The 12 arrangements with 3 endpoints of two (possibly degenerate) intervals [a, A] and [b, B] are
     aA-b-B, b-aA-B, b-B-aA, bB-a-A, a-bB-A, a-A-bB,
     ab-A-B, ab-B-A, a-b-AB, b-a-AB, a-bA-B, b-a-AB.
Here, for example, the notation aA-b-B indicates a = A < b < B, so the interval [a, A] is degenerate and lies to the left of the nondegenerate interval [b, B].
Row 2: (1, 7, 12, 6)
(x*(x + 1)/2)^2 = C(x,1) + 7*C(x,2) + 12*C(x,3) + 6*C(x,4).
Row 3: (1, 25, 138, 294, 270, 90)
(x*(x + 1)/2)^3 = C(x,1) + 25*C(x,2) + 138*C(x,3) + 294*C(x,4) + 270*C(x,5) + 90*C(x,6).
Sums of powers of triangular numbers:
Sum_{i = 1..n-1} (i*(i+1)/2)^2 = C(n,2) + 7*C(n,3) + 12*C(n,4) + 6*C(n,5);
Sum_{i = 1..n-1} (i*(i+1)/2)^3 = C(n,2) + 25*C(n,3) + 138*C(n,4) + 294*C(n,5) + 270*C(n,6) + 90*C(n,7).

Peter Bala, Deformations of the Hadamard product of power series
M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
IBM Ponder This, Jan 01 2001
Helmut Prodinger, On Touchard's continued fraction and extensions: combinatorics-free, self-contained proofs , arXiv:1102.5186 [math.CO], 2011.

Cf. A059516 (row sums), A059515, A087127, A122193, A131689.

A300729 := proc (n, k)
add((-1)^(k-i)*binomial(k, i)*((1/2)*i*(i+1))^n, i = 0..k);
end proc:
for n from 0 to 8 do
seq(A300729(n, k), k = 0..2*n)
end do;

T[0, 0] = 1; T[n_, k_] := Sum[(-1)^(k-i)*Binomial[k, i]*((1/2)*i*(i+1))^n, {i, 0, k}]; Table[T[n, k], {n, 1, 6}, {k, 1, 2 n}] // Flatten (* Jean-François Alcover, Mar 16 2018 *)

T(n,k) = Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i) * (i*(i+1)/2)^n for 0 <= k <= 2*n.
T(n,k) = A122193(n,k) + A122193(n,k+1).
T(n,k) = k*(k+1)/2*T(n-1,k) + k^2*T(n-1,k-1) + k*(k-1)/2*T(n-1,k-2) for 1 < k <= 2*n with boundary conditions T(0,0) = 1, T(0,n) = 0 for n >= 1; T(n,1) = 1 for n >= 1 and T(n,k) = 0 if k > 2*n.
Double e.g.f.: exp(-x)*Sum_{n>=0} exp( binomial(n+1,2)*y )* x^n/n! = 1 + (x + x^2/2!)*y + (x + 7*x^2/2! + 12*x^3/3! + 6*x^4/4!)*y^2/2! + ....
The n-th row of the table is given by the matrix product P^(-1)*v_n, where P denotes Pascal's triangle A007318 and v_n is the sequence (0, 1, 3^n, 6^n, 10^n, ...) regarded as an infinite column vector, where 1, 3, 6, 10, ... is the sequence of triangular numbers A000217. Cf. A087127 and A122193.
n-th row polynomial R(n,x) = (x + x^2) o ... o (x + x^2) (n factors) where o denotes the black diamond product of power series as defined by Dukes and White.
R(n,x) = Sum_{i >= 1} (i*(i+1)/2)^n*x^i/(1 + x)^(i+1) for n >= 1.
x*R(n,x) = (1 + x)* the n-th row polynomial of A122193 for n >= 1.
(1 + x)*R(n,x) = x * the n-th row polynomial of A087127 for n >= 1.
Sum_{k = 1..2*n} T(n,k)*binomial(x,k) = (binomial(x+1,2))^n for n >= 1.
Sum_{i = 1..n-1} (i*(i+1)/2)^m = Sum_{k = 1..2*m} T(m,k)*binomial(n,k+1) for m >= 1. See Example section below.
R(n,x) = 1/2^n*Sum_{k = 0..n} binomial(n,k)*F(n+k,x), where F(n,x) = Sum_{k = 0..n} k!*Stirling2(n,k)*x^k is the n-th Fubini polynomial, the n-th row polynomial of A131689.
R(n+1,x) = 1/2*(x + x^2) * (d/dx)^2 ( (x + x^2)*R(n,x) ).
R(n,x) = R(n,-1 - x).
The zeros of R(n,x) belong to the interval [-1, 0].
For n >= 1, the alternating sum of the n-th row equals 0.
E.g.f. as a continued fraction: 1/(1 + (x + x^2)*(1 - exp(t))/(1 + (x + x^2)*(1 -exp(2*t))/(1 + (x + x^2)*(1 - exp(3*t))/(1 + ...)))) = 1 + (x + x^2)*t + (x + 7*x^2 + 12*x^3 + 6*x^4)*t^2/2! + ... (use Prodinger, equation 1.1). - Peter Bala, Jun 13 2019

A059517 The sequence A059515(3,n). Number of ways of placing n identifiable nonnegative intervals with a total of exactly three starting and/or finishing points.

Original entry on oeis.org

0, 0, 12, 138, 1056, 7050, 44472, 273378, 1659936, 10018650, 60289032, 362265618, 2175188016, 13055911050, 78349815192, 470141937858, 2820980767296, 16926272024250, 101558794406952, 609356253226098, 3656147979709776, 21936919259318250, 131621609699088312

Offset: 0

Henry Bottomley, Jan 19 2001

			a(2)=12 since if aA indicates a zero length interval and a-A one of positive length the possibilities are: aA-b-B, b-aA-B, b-B-aA, bB-a-A, a-bB-A, a-A-bB, ab-A-B, ab-B-A, a-b-AB, b-a-AB, a-bA-B, b-a-AB.

IBM Ponder This, Jan 01 2001
Index entries for linear recurrences with constant coefficients, signature (10,-27,18).

Cf. A059516.

concat([0,0], Vec(-6*x^2*(3*x+2)/((x-1)*(3*x-1)*(6*x-1)) + O(x^100))) \\ Colin Barker, Sep 13 2014

a(n) = A058809(n)+A059116(n) = 6^n-3*3^n+3 (for n>0).
a(n) = 10*a(n-1)-27*a(n-2)+18*a(n-3) for n>3. - Colin Barker, Sep 13 2014
G.f.: -6*x^2*(3*x+2) / ((x-1)*(3*x-1)*(6*x-1)). - Colin Barker, Sep 13 2014

More terms from Colin Barker, Sep 13 2014

cp's OEIS Frontend

A316674 Number A(n,k) of paths from {0}^k to {n}^k that always move closer to {n}^k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059515 Square array T(k,n) by antidiagonals, where T(k,n) is number of ways of placing n identifiable nonnegative intervals with a total of exactly k starting and/or finishing points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A300729 Number of arrangements on a line of n finite closed intervals (possibly of zero length) with k distinct endpoints (n >= 1, 1 <= k <= 2*n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059517 The sequence A059515(3,n). Number of ways of placing n identifiable nonnegative intervals with a total of exactly three starting and/or finishing points.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions