A144645 Triangle in A144643 read upwards by columns.

1, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 6, 7, 1, 0, 1, 10, 25, 15, 0, 0, 1, 15, 65, 90, 25, 0, 0, 1, 21, 140, 350, 280, 35, 0, 0, 1, 28, 266, 1050, 1645, 770, 35, 0, 0, 1, 36, 462, 2646, 6825, 6930, 1855, 0, 0, 0, 1, 45, 750, 5880, 22575, 39795, 26425, 3675, 0, 0, 0

Offset

0,8

Links

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394 [math.CO], 2017.

David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.

Formula

From G. C. Greubel, Oct 11 2023: (Start)

T(n, k) = A144643(n-k, n).

T(n, k) = A144644(n, n-k).

T(n, k) = t(n-k, n), where t(n, k) = Sum_{j=0..3} binomial(k-1, j) * t(n-1, k-j-1), with t(n,n) = 1, t(n,k) = 0 if n < 1 or n > k.

Sum_{k=0..n} T(n, k) = A001681(n). (End)

Example

Triangle begins:
  1;
  1,  0;
  1,  1,   0;
  1,  3,   1,    0;
  1,  6,   7,    1,     0;
  1, 10,  25,   15,     0,     0;
  1, 15,  65,   90,    25,     0,     0;
  1, 21, 140,  350,   280,    35,     0,    0;
  1, 28, 266, 1050,  1645,   770,    35,    0,   0;
  1, 36, 462, 2646,  6825,  6930,  1855,    0,   0,   0;
  1, 45, 750, 5880, 22575, 39795, 26425, 3675,   0,   0,   0;

Mathematica

Table[BellY[n, n-k, {1, 1, 1, 1}], {n, 0, 15}, {k, 0, n}]]//Flatten (* G. C. Greubel, Oct 11 2023; based on A144644 *)

Prog

(Magma)
function t(n, k)
  if k eq n then return 1;
  elif k le n-1 or n le 0 then return 0;
  else return (&+[Binomial(k-1, j)*t(n-1, k-j-1): j in [0..3]]);
  end if;
end function;
A144645:= func< n, k | t(n-k, n) >;
[A144645(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 11 2023
(SageMath)
@CachedFunction
def t(n, k):
    if (k==n): return 1
    elif (k<n or n<1): return 0
    else: return sum(binomial(k-1, j)*t(n-1, k-j-1) for j in range(4))
def A144645(n, k): return t(n-k, n)
flatten([[A144645(n, k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Oct 11 2023

Crossrefs

Cf. A001681 (row sums), A144643, A144644.

Sequence in context: A256551 A144417 A085791 * A151510 A151512 A106800

Adjacent sequences: A144642 A144643 A144644 * A144646 A144647 A144648

Keyword

nonn,tabl

Author

David Applegate and N. J. A. Sloane, Jan 25 2009

Status

approved