A060475 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,8

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

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. [From 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).

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

EXAMPLE

Triangle begins

1, 0,

1, 1, 1,

1, 2, 3, 2,

1, 3, 7, 11, 9,

1, 4, 13, 32, 53, 44,

...

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 *)

PROG

(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

(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

(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

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.