login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=1..55.

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

CROSSREFS

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

KEYWORD

nonn,tabl

AUTHOR

Mohammad K. Azarian, Oct 28 2002

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 02:51 EDT 2020. Contains 334747 sequences. (Running on oeis4.)