|
|
A076732
|
|
Table T(n,k) giving number of ways of obtaining exactly one correct answer on an (n,k)-matching problem (1 <= k <= n).
|
|
4
|
|
|
1, 1, 0, 1, 2, 3, 1, 4, 9, 8, 1, 6, 21, 44, 45, 1, 8, 39, 128, 265, 264, 1, 10, 63, 284, 905, 1854, 1855, 1, 12, 93, 536, 2325, 7284, 14833, 14832, 1, 14, 129, 908, 5005, 21234, 65821, 133496, 133497, 1, 16, 171, 1424, 9545, 51264, 214459, 660064, 1334961, 1334960
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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.
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/(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
|
|
|
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]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|