A076732 -id:A076732 - cp's OEIS frontend

A193463 Row sums of triangle A076732.

1, 1, 6, 22, 117, 705, 4972, 39916, 360105, 3606865, 39721266, 477061026, 6205806061, 86925018817, 1304396077272, 20877063837400, 355003736855697, 6391465311099681, 121460116022428510, 2429579599296960430, 51027940329395658981, 1122742916106886416001

Offset: 1

Johannes W. Meijer, Jul 27 2011

a(n)/ceiling(n/2), i.e., a(n) divided by the positive integers repeated, leads to another sequence of integer numbers [1, 1, 3, 11, 39, 235, 1243, 9979, ... ].

Alois P. Heinz, Table of n, a(n) for n = 1..450

Cf. A047920, A076732.

A193463:=proc(n): add(A076732(n,k), k=1..n) end: A076732:=proc(n,k): (k/(n-k)!)*A047920(n,k) end: A047920:=proc(n,k): add(((-1)^j)*binomial(k-1,j)*(n-1-j)!, j=0..k-1) end: seq(A193463(n), n=1..22);

A000240[n_] := Subfactorial[n] - (-1)^n;
T[n_, k_] := T[n, k] = Switch[k, 1, 1, n, A000240[n], _, k*T[n - 1, k - 1] + T[n - 1, k]];
a[n_] := Sum[T[n, k], {k, 1, n}];
Table[a[n], {n, 1, 22}] (* Jean-François Alcover, Nov 14 2023 *)

a(n) = Sum_{k=1..n} A076732(n,k).
a(n) = Sum_{k=1..n} (k/(n-k)!)*A047920(n,k).
a(n) = Sum_{k=1..n} (k/(n-k)!) * Sum_{j=0..k-1} (-1)^j*binomial(k-1,j)*(n-1-j)!.

A076731 Table T(n,k) giving number of ways of obtaining exactly 0 correct answers on an (n,k)-matching problem (1 <= k <= n).

Original entry on oeis.org

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

Offset: 1

Mohammad K. Azarian, Oct 28 2002

Hanson et al. define the (n,k)-matching problem in the following realistic way. A matching question on an exam has k questions with n possible answers to choose from, each question having a unique answer. If a student guesses the answers at random, using each answer at most once, what is the probability of obtaining r of the k correct answers?
The T(n,k) represent the number of ways of obtaining exactly zero correct answers, i.e., r=0, given k questions and n possible answers, 1 <= k <= n.
T(n,k) is the number of injections from [1,...,k] into [1,...,n] with no fixed points. - David Bevan, Apr 29 2013

			0; 1,1; 2,3,2; 3,7,11,9; ...
Formatted as a square array:
0 1 2 3 4 5 6 7 8
1 3 7 13 21 31 43 57 which equals A002061
2 11 32 71 134 227 356 which equals A094792
9 53 181 465 1001 1909 which equals A094793
44 309 1214 3539 8544 which equals A094794
265 2119 9403 30637 which equals A023043
1854 16687 82508 which equals A023044
14833 148329 which equals A023045
Columns give A000255 A000153 A000261 A001909 A001910
Formatted as a triangular array (mirror image of A086764):
0
1 1
2 3 2
3 7 11 9
4 13 32 53 44
5 21 71 181 309 265
6 31 134 465 1214 2119 1854
7 43 227 1001 3539 9403 16687 14833
8 57 356 1909 8544 30637 82508 148329 133496

D. Hanson, K. Seyffarth and J. H. Weston, Matchings, Derangements, Rencontres, Mathematics Magazine, Vol. 56, No. 4, September 1983.
StackExchange, How many injective functions f:[1,...,m]->[1,...,n] have no fixed point?

Cf. A076732, A086764.

Similar to A060475.

A076731 := proc(n,k): (1/(n-k)!)*A061312(n-1,k-1) end: A061312:=proc(n,k): add(((-1)^j)*binomial(k+1,j)*(n+1-j)!, j=0..k+1) end: for n from 1 to 7 do seq(A076731(n,k), k=1..n) od; seq(seq(A076731(n,k), k=1..n), n=1..9); # Johannes W. Meijer, Jul 27 2011

t[n_,k_] := k!(n - k)! SeriesCoefficient[Exp[z(1-u+u^2z)/(1-z u)]/(1-z u), {z,0,n}, {u,0,k}]; Table[t[n,k], {n,9}, {k,n}] //TableForm (* David Bevan, Apr 29 2013 *)
t[n_, k_] := Pochhammer[n-k+1, k]*Hypergeometric1F1[-k, -n, -1]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 29 2013 *)

T(n,k) = F(n,k)*Sum{((-1)^j)*C(k, j)*(n-j)! (j=0 to k)}, where F(n,k) = 1/(n-k)! for 1 <= k <= n.
From Johannes W. Meijer, Jul 27 2011: (Start)
T(n,k) = (n-1)*T(n-1,k-1) + (k-1)*T(n-2,k-2) with T(n,1) = (n-1) and T(n,n) = A000166(n) [Hanson et al.]
T(n,k) = (1/(n-k)!)*A061312(n-1,k-1)
sum(T(n,k), k=1..n) = A193464(n); row sums. (End)
T(n,k) = k!(n-k)![z^n*u^k]J(z,u) where J(z,u) = exp(z(1-u+z*u^2)/(1-z*u))/(1-z*u) is the exponential generating function of labeled digraphs consisting just of directed paths and oriented cycles (of length at least 2), z marking the vertices and u the edges; [z^n*u^k]J(z,u) is the coefficient of z^n*u^k in J(z,u). - David Bevan, Apr 29 2013

Additional comments from Zerinvary Lajos, Mar 30 2006

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

Original entry on oeis.org

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

Henry Bottomley, Mar 16 2001

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

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

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

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.

[[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

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

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

{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

[[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

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

cp's OEIS Frontend

A193463 Row sums of triangle A076732.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A076731 Table T(n,k) giving number of ways of obtaining exactly 0 correct answers on an (n,k)-matching problem (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula