A060475 Triangular array formed from successive differences of factorial numbers, then with factorials removed.

1, 1, 0, 1, 1, 1, 1, 2, 3, 2, 1, 3, 7, 11, 9, 1, 4, 13, 32, 53, 44, 1, 5, 21, 71, 181, 309, 265, 1, 6, 31, 134, 465, 1214, 2119, 1854, 1, 7, 43, 227, 1001, 3539, 9403, 16687, 14833, 1, 8, 57, 356, 1909, 8544, 30637, 82508, 148329, 133496, 1, 9, 73, 527, 3333, 18089, 81901, 296967, 808393, 1468457, 1334961

Offset: 0

Author

Henry Bottomley, Mar 16 2001

Keywords

• nonn
• tabl
• changed

Comments

T(n,k) is also the number of partial bijections (of an n-element set) with a fixed domain of size k and without fixed points. Equivalently, T(n,k) is the number of partial derangements with a fixed domain of size k in the symmetric inverse semigroup (monoid), I sub n. - Abdullahi Umar, Sep 14 2008

Examples

			Triangle begins
  1,
  1,  0,
  1,  1,  1,
  1,  2,  3,  2,
  1,  3,  7, 11,  9,
  1,  4, 13, 32, 53, 44,
  ...
		

Links

• G. C. Greubel, Rows n=0..100 of triangle, flattened
• A. Laradji, and A. Umar, Combinatorial results for the symmetric inverse semigroup, Semigroup Forum 75 (2007), 221-236. - _Abdullahi Umar_, Sep 14 2008
• L. Takacs, The Problem of Coincidences, Archive for History of Exact Sciences, Volume 21, No. 3, Sept. 1980. pp 229-244, paragraph 10 (Catalan).

Crossrefs

Columns include A000012, A001477, A002061.

Diagonals include A000166, A000255, A000153, A000261, A001909, A001910.

Main diagonal is abs of A002119.

Similar to A076731.

Row sums equal A003470. - Johannes W. Meijer, Jul 27 2011

Cf. A047920, A008290.

Programs

Magma

[[Factorial(k)*(&+[(-1)^j*Binomial(n-j, k-j)/Factorial(j): j in [0..k]]): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Mar 04 2019

Maple

A060475 := proc(n,k): k! * add(binomial(n-j,k-j)*(-1)^j/j!, j=0..k) end:
seq(seq(A060475(n,k), k=0..n), n=0..7); # Johannes W. Meijer, Jul 27 2011
T := (n,k) -> KummerU(-k, -n, -1):
seq(seq(simplify(T(n, k)), k = 0..n), n = 0..10); # Peter Luschny, Jul 07 2022

Mathematica

t[n_, k_] := k!*Sum[Binomial[n - j, k - j]*(-1)^j/j!, {j, 0, k}]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Robert G. Wilson v, Aug 08 2011 *)

PARI

{T(n,k) = k!*sum(j=0,k, (-1)^j*binomial(n-j, k-j)/j!)};
for(n=0,10, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Mar 04 2019

Sage

[[factorial(k)*sum((-1)^j*binomial(n-j, k-j)/factorial(j) for j in (0..k)) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Mar 04 2019

Formula

T(n,k) = A047920(n,k)/(n-k)! = (n-1)*T(n-1,k-1) + (k-1)*T(n-2,k-2) = (n-k+1)*T(n, k-1) - T(n-1,k-1).

From Abdullahi Umar, Sep 14 2008: (Start)

T(n,k) = k! * Sum_{j=0..k} C(n-j,k-j)*(-1)^j/j!.

C(n,k)*T(n,k) = A144089(n, k). (End)

T(n,k) = A076732(n+1,k+1)/(k+1). - Johannes W. Meijer, Jul 27 2011

E.g.f. as a square array: A(x,y) = exp(-x)/(1 - x - y) = (1 + y + y^2 + y^3 + ...) + (y + 2*y^2 + 3*y^3 + 4*y^4 + ...)*x + (1 + 3*y + 7*y^2 + 13*y^3 + ...)*x^2/2! + (2 + 11*y + 32*y^2 + 71*y^3 + ...)*x^3/3! + .... Observe that (1 - y)*A(x*(1 - y),y) = exp(x*(y - 1))/(1 - x) is the e.g.f. for A008290. - Peter Bala, Sep 25 2013

T(n, k) = KummerU(-k, -n, -1). - Peter Luschny, Jul 07 2022