|
%I #20 Nov 14 2023 07:05:24
%S 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,
%T 1854,1855,1,12,93,536,2325,7284,14833,14832,1,14,129,908,5005,21234,
%U 65821,133496,133497,1,16,171,1424,9545,51264,214459,660064,1334961,1334960
%N Table T(n,k) giving number of ways of obtaining exactly one correct answer on an (n,k)-matching problem (1 <= k <= n).
%C 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?
%C 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.
%H D. Hanson, K. Seyffarth and J. H. Weston, <a href="http://www.jstor.org/stable/2689812">Matchings, Derangements, Rencontres</a>, Mathematics Magazine, Vol. 56, No. 4, September 1983.
%F 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.
%F From _Johannes W. Meijer_, Jul 27 2011: (Start)
%F 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.]
%F 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.]
%F T(n,k) = k*A060475(n-1,k-1).
%F T(n,k) = (k/(n-k)!)*A047920(n-1,k-1).
%F Sum_{k=1..n} T(n,k) = A193463(n); row sums.
%F Sum_{k=1..n} T(n,k)/k = A003470(n-1). (End)
%e Triangle begins
%e 1;
%e 1,0;
%e 1,2,3;
%e 1,4,9,8;
%e ...
%p 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
%t A000240[n_] := Subfactorial[n] - (-1)^n;
%t T[n_, k_] := T[n, k] = Switch[k, 1, 1, n, A000240[n], _, k*T[n-1, k-1] + T[n-1, k]];
%t Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Nov 14 2023 *)
%Y Columns: A000012(n), 2*A001477(n-2), 3*A002061(n-2), 4*A094792(n-4), 5*A094793(n-5), 6*A094794(n-6), 7*A094795(n-7); A000240(n), A000166(n). - _Johannes W. Meijer_, Jul 27 2011
%K nonn,tabl
%O 1,5
%A _Mohammad K. Azarian_, Oct 28 2002
%E Edited and information added by _Johannes W. Meijer_, Jul 27 2011
|
