OFFSET
1,5
COMMENTS
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 one correct answer, i.e., r=1, given k questions and n possible answers, 1 <= k <= n.
LINKS
D. Hanson, K. Seyffarth and J. H. Weston, Matchings, Derangements, Rencontres, Mathematics Magazine, Vol. 56, No. 4, September 1983.
FORMULA
T(n,k) = F(n,k)*Sum{((-1)^j)*C(k-1, j)*(n-1-j)! (j=0 to k-1)}, where F(n,k) = k/(n-k)!, for 1 <= k <= n.
From Johannes W. Meijer, Jul 27 2011: (Start)
T(n,k) = k*T(n-1,k-1) + T(n-1,k) with T(n,1) = 1 and T(n,n) = A000240(n). [Hanson et al.]
T(n,k) = (n-1)*T(n-1,k-1) + (k-1)*T(n-2,k-2) + (1-k)*A076731(n-2,k-2) + A076731(n-1,k-1) with T(0,0) = T(n,0) = 0 and T(n,1) = 1. [Hanson et al.]
T(n,k) = k*A060475(n-1,k-1).
T(n,k) = (k/(n-k)!)*A047920(n-1,k-1).
Sum_{k=1..n} T(n,k) = A193463(n); row sums.
Sum_{k=1..n} T(n,k)/k = A003470(n-1). (End)
EXAMPLE
Triangle begins
1;
1,0;
1,2,3;
1,4,9,8;
...
MAPLE
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(seq(A076732(n, k), k=1..n), n=1..10); # Johannes W. Meijer, Jul 27 2011
MATHEMATICA
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]];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 14 2023 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Mohammad K. Azarian, Oct 28 2002
EXTENSIONS
Edited and information added by Johannes W. Meijer, Jul 27 2011
STATUS
approved