login
A144645
Triangle in A144643 read upwards by columns.
3
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
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
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved