1,5

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.

D. Hanson, K. Seyffarth and J. H. Weston, Matchings, Derangements, Rencontres, Mathematics Magazine, Vol. 56, No. 4, September 1983.

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)

Triangle begins

1;

1,0;

1,2,3;

1,4,9,8;

...

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

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

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

Sequence in context: A119865 A177896 A193920 * A130152 A211233 A084608

Adjacent sequences: A076729 A076730 A076731 * A076733 A076734 A076735

nonn,tabl

Mohammad K. Azarian, Oct 28 2002

Edited and information added by Johannes W. Meijer, Jul 27 2011

approved