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

%I #49 Sep 08 2022 08:45:03

%S 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,

%T 1,6,31,134,465,1214,2119,1854,1,7,43,227,1001,3539,9403,16687,14833,

%U 1,8,57,356,1909,8544,30637,82508,148329,133496,1,9,73,527,3333,18089,81901,296967,808393,1468457,1334961

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

%C 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

%H G. C. Greubel, <a href="/A060475/b060475.txt">Rows n=0..100 of triangle, flattened</a>

%H A. Laradji, and A. Umar, <a href="https://www.researchgate.net/publication/226754032_Combinatorial_Results_for_the_Symmetric_Inverse_Semigroup">Combinatorial results for the symmetric inverse semigroup</a>, Semigroup Forum 75 (2007), 221-236. [From Abdullahi Umar, Sep 14 2008]

%H L. Takacs, <a href="https://doi.org/10.1007/BF00327875">The Problem of Coincidences</a>, Archive for History of Exact Sciences, Volume 21, No. 3, Sept. 1980. pp 229-244, paragraph 10 (Catalan).

%F 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).

%F From _Abdullahi Umar_, Sep 14 2008: (Start)

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

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

%F T(n,k) = A076732(n+1,k+1)/(k+1). - _Johannes W. Meijer_, Jul 27 2011

%F 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

%F T(n, k) = KummerU(-k, -n, -1). - _Peter Luschny_, Jul 07 2022

%e Triangle begins

%e 1,

%e 1, 0,

%e 1, 1, 1,

%e 1, 2, 3, 2,

%e 1, 3, 7, 11, 9,

%e 1, 4, 13, 32, 53, 44,

%e ...

%p A060475 := proc(n,k): k! * add(binomial(n-j,k-j)*(-1)^j/j!, j=0..k) end:

%p seq(seq(A060475(n,k), k=0..n), n=0..7); # _Johannes W. Meijer_, Jul 27 2011

%p T := (n,k) -> KummerU(-k, -n, -1):

%p seq(seq(simplify(T(n, k)), k = 0..n), n = 0..10); # _Peter Luschny_, Jul 07 2022

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

%o (PARI) {T(n,k) = k!*sum(j=0,k, (-1)^j*binomial(n-j, k-j)/j!)};

%o for(n=0,10, for(k=0,n, print1(T(n,k), ", "))) \\ _G. C. Greubel_, Mar 04 2019

%o (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

%o (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

%Y Columns include A000012, A001477, A002061.

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

%Y Main diagonal is abs of A002119.

%Y Similar to A076731.

%Y Row sums equal A003470. - _Johannes W. Meijer_, Jul 27 2011

%Y Cf. A047920, A008290.

%K nonn,tabl

%O 0,8

%A _Henry Bottomley_, Mar 16 2001