Alice's school is planning to take some students from her class on a field trip. Alice is really excited about it. There are a total of S students in her class. But due to budget constraints, the school is planning to take only N students for the trip. These students will be picked randomly. And each student has equal chance of being picked.
Alice's friend circle has M students including her. Though she is excited about the field trip, she will enjoy it only if there are atleast K of her friends with her on the trip. She is wondering what are the chances of that happening. She needs your help. Tell her the probability that she will enjoy given that she goes on the trip.

-----Input:-----
First line of input contains a single integer T, the number of test cases.

Each test starts with a single line having 4 space separated integers, S, N, M and K.

-----Output:-----
For each test case, output a line containing the required probability. The answer will be accepted if the relative error is not more than 10-6.

-----Constraints:-----
1 ≤ T ≤ 100
1 ≤ S ≤ 1000
1 ≤ N ≤ S
1 ≤ M ≤ S
0 ≤ K < M

-----Example:-----Input:
3
10 10 5 3
10 4 6 4
3 2 2 1

Output:
1.000000
0.000000
0.500000

-----Explanation:-----Case #1:
Every student will be taken to the trip. So all her 4 friends will accompany her to the trip no matter what. 
Case #2:
Alice wants 4 out of her 5 friends to come along with her which isn't possible because the school is willing to pick only 4 students for the trip.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Probability

Starter code:

Solutions:
def nck(n, k):
	if k > n or k < 0:
		return 0
	if k < n - k:
		k = n - k
	ans = 1.0
	for i in range(1, n - k + 1):
		ans = ans * (k + i) / i
	return ans
tc = int(input())
while tc:
	(s, n, m, k) = input().split()
	(s, n, m, k) = (int(s), int(n), int(m), int(k))
	prob = 0.0
	i = k
	while i < m:
		prob = prob + nck(m - 1, i) / nck(s - 1, n - 1) * nck(s - m, n - i - 1)
		i = i + 1
	print('{0:.6f}'.format(prob))
	tc = tc - 1


nCr = [[0 for x in range(1001)] for x in range(1001)]
for i in range(0, 1001):
	nCr[i][0] = 1
	nCr[i][i] = 1
for i in range(1, 1001):
	for j in range(1, 1001):
		if i != j:
			nCr[i][j] = nCr[i - 1][j] + nCr[i - 1][j - 1]
t = eval(input())
for rajarshisarkar in range(0, t):
	(s, n, m, k) = list(map(int, input().split(' ')))
	foo = 0.0
	tot = float(nCr[s - 1][n - 1])
	if s == n:
		print('1.000000\n')
		continue
	if k > n:
		print('0.000000\n')
		continue
	if m > n:
		wola = n
	else:
		wola = m
	for i in range(k, wola):
		foo += nCr[m - 1][i] * nCr[s - m][n - i - 1]
	print('%f\n' % float(foo / tot))


import sys

def main():
	maxN = 1010
	c = [[0] * maxN for x in range(maxN)]
	for i in range(maxN):
		c[i][0] = 1
		c[i][i] = 1
	for i in range(1, maxN):
		for j in range(1, maxN):
			if i != j:
				c[i][j] = c[i - 1][j] + c[i - 1][j - 1]
	t = int(sys.stdin.readline())
	for i in range(t):
		(s, n, m, k) = list(map(int, sys.stdin.readline().split(' ')))
		D = float(c[s - 1][n - 1])
		N = 0.0
		if s == n:
			print(1.0)
			continue
		if k > n:
			print(0.0)
			continue
		upper = min(m, n)
		for j in range(k, upper):
			N += c[m - 1][j] * c[s - m][n - 1 - j]
		ans = float(N / D)
		print('%f' % ans)
main()


coff = [[0 for x in range(1003)] for x in range(1003)]

def precompute():
	coff[0][0] = 1
	coff[1][0] = coff[1][1] = 1
	for i in range(2, 1002, 1):
		for j in range(0, i + 1, 1):
			if i == j:
				coff[i][j] = 1
			elif j == 0:
				coff[i][j] = 1
			else:
				coff[i][j] = coff[i - 1][j] + coff[i - 1][j - 1]

def main():
	precompute()
	t = eval(input())
	for i in range(0, t, 1):
		(s, n, m, k) = map(int, input().split(' '))
		if s == n:
			print('1.000000\n')
			continue
		if k > n:
			print('0.000000\n')
			continue
		else:
			total = float(coff[s - 1][n - 1])
			chance = 0.0
			for j in range(k, m):
				chance += coff[m - 1][j] * coff[s - m][n - j - 1]
			print('%f\n' % float(chance / total))
main()


nCr = [[0 for x in range(1001)] for x in range(1001)]
for i in range(0, 1001):
	nCr[i][0] = 1
	nCr[i][i] = 1
for i in range(1, 1001):
	for j in range(1, 1001):
		if i != j:
			nCr[i][j] = nCr[i - 1][j] + nCr[i - 1][j - 1]
t = eval(input())
for __ in range(0, t):
	s = input().split()
	(s, n, m, k) = (int(s[0]), int(s[1]), int(s[2]), int(s[3]))
	if s == n:
		print('1.000000')
		continue
	foo = float(0.0)
	s = s - 1
	n = n - 1
	m = m - 1
	bar = float(nCr[s][n])
	x = k - 1
	if k > n:
		print('0.000000')
		continue
	for i in range(0, x + 1):
		foo = foo + nCr[m][i] * nCr[s - m][n - i]
	ans = float(1 - foo / bar)
	print(ans)


fac = [1]

def fact():
	fac[0] = 1
	for i in range(1, 1001):
		fac.append(i * fac[i - 1])

def nCk(N, K):
	nn = N
	klim = min(K, N - K) + 1
	res = 1
	for kk in range(1, klim):
		res *= nn
		res /= kk
		nn -= 1
	return res

def test1():
	CC = input()
	CCT = CC.split()
	S = int(CCT[0])
	N = int(CCT[1])
	M = int(CCT[2])
	K = int(CCT[3])
	total = nCk(S - 1, N - 1)
	klim = min(M, N)
	num = 0
	for kk in range(K, klim):
		if S - M < N - kk - 1:
			continue
		num += nCk(M - 1, kk) * nCk(S - M, N - kk - 1)
	ans = num / float(total)
	print('%.9f' % ans)

def test2():
	CC = input()
	CCT = CC.split(' ')
	S = int(CCT[0])
	N = int(CCT[1])
	M = int(CCT[2])
	K = int(CCT[3])
	total = fac[S - 1] / fac[N - 1] / fac[S - N]
	klim = min(M, N)
	num = 0
	for kk in range(K, klim):
		if S - M < N - kk - 1:
			continue
		num += fac[M - 1] / fac[kk] / fac[M - kk - 1] * fac[S - M] / fac[N - kk - 1] / fac[S - M - N + kk + 1]
	ans = num / float(total)
	print('%.9f' % ans)
t = int(input())
for tt in range(0, t):
	test1()


def main():
	matrix = 1001 * [None]
	for i in range(1001):
		matrix[i] = (i + 1) * [None]
	matrix[0][0] = 1
	matrix[1][0] = 1
	matrix[1][1] = 1
	for i in range(1001):
		for j in range(i + 1):
			if j == 0:
				matrix[i][j] = 1
			elif j == i:
				matrix[i][j] = 1
			else:
				matrix[i][j] = matrix[i - 1][j] + matrix[i - 1][j - 1]
	sum = 0
	t = int(input())
	for i in range(t):
		i = i + 1
		s = input()
		l = list(map(int, s.split(' ')))
		if l[0] == l[1] or l[2] == 1 or l[0] == 1 or (l[0] - l[2] < l[1] - l[3] - 1):
			print(1.0)
		elif l[1] <= l[3]:
			print(0.0)
		else:
			for j in range(l[3], min(l[2], l[1])):
				sum = sum + matrix[l[2] - 1][j] * matrix[l[0] - l[2]][l[1] - j - 1]
				j = j + 1
			print(float(sum / matrix[l[0] - 1][l[1] - 1]))
		sum = 0
main()


a = [[0] * 1010 for x in range(1010)]
for i in range(1007):
	a[0][i] = 0
for i in range(1007):
	a[i][0] = 1
for i in range(1, 1005):
	for j in range(1, i + 1):
		a[i][j] = a[i - 1][j - 1] + a[i - 1][j]
test = int(input())
while test > 0:
	sum = 0.0
	(s, n, m, k) = list(map(int, input().split()))
	if s == 1:
		print(1.0)
		test = test - 1
		continue
	r = a[s][n]
	for i in range(k, m):
		p = a[m][i + 1]
		if n < i + 1 or s - m < n - (i + 1):
			q = 0
		else:
			q = a[s - m][n - (i + 1)]
		sum = sum + float(p * q * (i + 1) * s)
	sum = sum / float(r * m * n)
	print('%.6f' % sum)
	test = test - 1


nCr = [[0 for x in range(1001)] for x in range(1001)]
for i in range(0, 1001):
	nCr[i][0] = 1
	nCr[i][i] = 1
for i in range(1, 1001):
	for j in range(1, 1001):
		if i != j:
			nCr[i][j] = nCr[i - 1][j] + nCr[i - 1][j - 1]
t = eval(input())
for _ in range(0, t):
	(s, n, m, k) = list(map(int, input().split(' ')))
	y = 0
	if s == n:
		print('1.000000')
		continue
	if k > m or k > n:
		print('0.000000')
		continue
	total = float(nCr[s - 1][n - 1])
	if m > n:
		z = m
	else:
		z = n
	for i in range(k, z):
		y += nCr[m - 1][i] * nCr[s - m][n - i - 1]
	print('%.6f' % float(y / total))


comb = [[0.0 for j in range(1001)] for i in range(1001)]
comb[0][0] = 0
for i in range(1001):
	comb[i][0] = 1
	comb[i][i] = 1
	for j in range(1, i):
		comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j]
t = int(input())
for i in range(t):
	(S, N, M, K) = map(int, input().split())
	todas = comb[S - 1][N - 1]
	M -= 1
	if todas < 1:
		print(0)
		continue
	O = S - M - 1
	pueden = 0
	for j in range(K, M + 1):
		if K > N - 1:
			continue
		if N - 1 - j < 0:
			continue
		pueden += comb[M][j] * comb[O][N - 1 - j]
	print('%.6f' % (pueden / todas))


a = []
for i in range(1001):
	a.append(0.0)
t = int(input())
while t > 0:
	t -= 1
	line = input().split()
	s = int(line[0])
	n = int(line[1])
	m = int(line[2])
	k = int(line[3])
	ans = 0
	div = 0
	for j in range(m):
		if s - m >= n - j - 1 and n - j - 1 >= 0 and (m - 1 >= j):
			a[j] = 1.0
			break
		else:
			a[j] = 0.0
	for i in range(j + 1, m):
		if s - m >= n - i - 1 and n - i - 1 >= 0 and (m - 1 >= i):
			a[i] = a[i - 1] * (m - i) * (n - i) / (i * (s - n - m + i + 1))
		else:
			a[i] = 0.0
	for i in range(m):
		if i >= k:
			ans += a[i]
		div += a[i]
	print('{0:.6f}'.format(ans / div))


fact = [None] * 1001
fact[0] = 1
for i in range(1, 1001):
	fact[i] = fact[i - 1] * i
t = int(input())
for z in range(t):
	(s, n, m, k) = map(int, input().split())
	P = 0
	for i in range(k, min(n, m)):
		P += fact[m - 1] / (fact[i] * fact[m - i - 1]) * (fact[s - m] / (fact[s - m - n + i + 1] * fact[n - i - 1]))
	Q = fact[s - 1] / (fact[n - 1] * fact[s - n])
	ans = float(P / Q)
	print('%.6f' % ans)


for _ in range(int(input())):
	(S, N, M, K) = map(int, input().split())

	def cnk(n, k):
		k_min = min(k, n - k)
		(num, denom) = (1, 1)
		for x in range(1, k_min + 1):
			num *= n - x + 1
			denom *= x
		return num // denom
	total = cnk(S - 1, N - 1)
	upper_lim = min(M, N)
	num = 0
	for k in range(K, upper_lim + 1 - 1):
		if S - M >= N - k - 1:
			num += cnk(M - 1, k) * cnk(S - M, N - k - 1)
	ans = num / float(total)
	print('%.9f' % ans)


a = [[0] * 1010 for i in range(1010)]
for i in range(1007):
	(a[0][i], a[i][0]) = (0, 1)
for i in range(1, 1005):
	for j in range(1, i + 1):
		a[i][j] = a[i - 1][j - 1] + a[i - 1][j]
for _ in range(int(input())):
	sum = 0.0
	(s, n, m, k) = map(int, input().split(' '))
	if s == 1:
		print('1.000000')
		continue
	r = a[s][n]
	for i in range(k, m):
		p = a[m][i + 1]
		if n < i + 1 or s - m < n - (i + 1):
			q = 0
		else:
			q = a[s - m][n - (i + 1)]
		sum = sum + float(p * q * (i + 1) * s)
	sum = sum / float(r * m * n)
	print('%.6f' % sum)


import math
f = [1]
for i in range(1, 1002):
	f.append(i * f[i - 1])

def c(n, r):
	if n < r:
		return 0
	else:
		return float(f[n] / (f[n - r] * f[r]))
t = int(input())
while t > 0:
	[s, n, m, k] = [int(i) for i in input().split()]
	ways = 0.0
	if k == 0 or s == n:
		print(float(1))
	elif k >= n:
		print(float(0))
	else:
		j = k - 1
		flag = 0
		while s - m >= 0 and j >= 0 and (n - j - 1 >= 0):
			ways = ways + c(m - 1, j) * c(s - m, n - j - 1)
			j -= 1
		p = ways / c(s - 1, n - 1)
		p = 1 - p
		print(p)
	t -= 1


def nCk(N, K):
	nn = N
	klim = min(K, N - K) + 1
	res = 1
	for kk in range(1, klim):
		res *= nn
		res /= kk
		nn -= 1
	return res

def doTest():
	CC = input()
	CCT = CC.split()
	S = int(CCT[0])
	N = int(CCT[1])
	M = int(CCT[2])
	K = int(CCT[3])
	den = nCk(S - 1, N - 1)
	klim = min(M, N)
	num = 0
	for kk in range(K, klim):
		if S - M < N - kk - 1:
			continue
		num += nCk(M - 1, kk) * nCk(S - M, N - kk - 1)
	ans = num / float(den)
	print('%.9f' % ans)
T = int(input())
for tt in range(0, T):
	doTest()


from decimal import *
factlist = []
factlist.append(1)
for i in range(1, 1001):
	factlist.append(factlist[i - 1] * i)

def comb(n, m):
	if m > n:
		return 0
	elif n == m:
		return 1
	else:
		cmb = factlist[n] // (factlist[m] * factlist[n - m])
		return cmb
t = int(input())
while t:
	t -= 1
	(s, n, m, k) = map(int, input().split())
	s -= 1
	n -= 1
	m -= 1
	if n < k:
		print(0.0)
	elif (s == n) | (s == m) & (n >= k) | (n - s + m >= k):
		print(1.0)
	else:
		ans = 0
		for i in range(k, m + 1):
			ans = ans + comb(m, i) * comb(s - m, n - i)
		ans1 = comb(s, n)
		getcontext().prec = 6
		print(Decimal(ans) / Decimal(ans1))


nCr = [[0 for x in range(1001)] for x in range(1001)]
for i in range(0, 1001):
	nCr[i][0] = 1
	nCr[i][i] = 1
for i in range(1, 1001):
	for j in range(1, 1001):
		if i != j:
			nCr[i][j] = nCr[i - 1][j] + nCr[i - 1][j - 1]

def main():
	t = int(input())
	for i in range(t):
		num = 0
		line = input().split(' ')
		s = int(line[0])
		n = int(line[1])
		m = int(line[2])
		k = int(line[3])
		if k > n - 1:
			print('0.000000')
		else:
			j = k
			while j < n and j < m:
				p = int(nCr[m - 1][j])
				q = int(nCr[s - m][n - j - 1])
				num = int(num) + p * q
				j = j + 1
			den = int(nCr[s - 1][n - 1])
			ans = float(num) / den
			print('{0:.11f}'.format(ans))

def __starting_point():
	main()
__starting_point()


import sys

class first:
	a = []
	for i in range(1005):
		a.append([])
	for i in range(1005):
		for j in range(1005):
			if j == 0:
				a[i].append(1)
			elif i == 0:
				a[i].append(0)
			elif j <= i:
				a[i].append(a[i - 1][j] + a[i - 1][j - 1])
			else:
				a[i].append(0)
	t = input()
	while int(t) != 0:
		lst = list(map(int, input().split()))
		s = lst[0]
		n = lst[1]
		m = lst[2]
		k = lst[3]
		if n <= k:
			print('0.000000')
		elif n - k - 1 > s - m:
			print('1.000000')
		else:
			s -= 1
			n -= 1
			m -= 1
			if m < n:
				min = m
			else:
				min = n
			op = 0
			for i in range(k, min + 1):
				op += a[m][i] * a[s - m][n - i] / a[s][n]
			print('%.6f' % op)
		t = int(t) - 1


dp = []

def pre():
	for i in range(1002):
		dp.append([])
		for j in range(i + 1):
			if i == 0 or i == j or j == 0:
				dp[i].append(1)
			else:
				dp[i].append(dp[i - 1][j - 1] + dp[i - 1][j])
t = int(input())
pre()
for y in range(t):
	line = input().split()
	s = int(line[0])
	n = int(line[1])
	m = int(line[2])
	k = int(line[3])
	if k == 0:
		print('1.000000')
		continue
	if s == n:
		print('1.000000')
		continue
	s = s - 1
	n = n - 1
	m = m - 1
	if n < k:
		print('0.000000')
		continue
	if n - (s - m) >= k:
		print('1.000000')
		continue
	total = 0
	for i in range(k, m + 1):
		if n - i >= 0:
			total += dp[m][i] * dp[s - m][n - i]
	print('{0:.6f}'.format(total / dp[s][n]))


import math
a = [[0] * 1001 for _ in range(1001)]
for i in range(0, 1001):
	for j in range(0, i + 1):
		if j == 0 or j == i:
			a[i][j] = 1
		else:
			a[i][j] = a[i - 1][j - 1] + a[i - 1][j]
t = int(input())
while t > 0:
	line = input()
	line = line.split(' ')
	s = int(line[0])
	n = int(line[1])
	m = int(line[2])
	k = int(line[3])
	save = 0
	while k < m and k < n:
		save = save + a[m - 1][k] * a[s - m][n - k - 1]
		k = k + 1
	ans = save / a[s - 1][n - 1]
	print('%.6f' % ans)
	t = t - 1


di = {}

def fact(n):
	di[0] = 1
	a = 1
	for i in range(1, n + 1):
		a *= i
		di[i] = a

def comb(n, r):
	return di[n] / (di[r] * di[n - r])
t = int(input())
fact(1000)
while t > 0:
	l = input()
	a = l.split()
	s = int(a[0])
	n = int(a[1])
	m = int(a[2])
	k = int(a[3])
	d = comb(s - 1, n - 1)
	p = 0
	kk = m + n - 1 - s
	if k < kk:
		k = kk
	while k <= n - 1 and k <= m - 1:
		p += comb(m - 1, k) * comb(s - m, n - 1 - k)
		k += 1
	p = p / d
	print(p)
	t -= 1


import sys

def foo(a, b):
	i = a
	c = b
	n = 1
	an = 1
	if a - b < c:
		c = a - b
	while n <= c:
		an = an * i / n
		i -= 1
		n += 1
	return an
tc = eval(input())
for i in range(tc):
	a = input().split()
	total = int(a[0]) - 1
	selection = int(a[1]) - 1
	friends = int(a[2]) - 1
	need = int(a[3])
	res = 0
	maxi = foo(total, selection)
	if need > selection:
		print('0')
	elif need < friends - need:
		for j in range(need):
			if selection - j >= 0 and total - friends >= selection - j:
				res += foo(friends, j) * foo(total - friends, selection - j)
		res = float(res) / maxi
		print(1.0 - res)
	else:
		for j in range(need, friends + 1, 1):
			if selection - j >= 0 and total - friends >= selection - j:
				res += foo(friends, j) * foo(total - friends, selection - j)
		res = float(res) / maxi
		print(res)