Я застрял в этой проблеме. Я думаю, что это эквивалентно тому, чтобы показать, что 2m выбирает m, является большой тетой 4 мощности n, но все равно трудно ее доказать.Как доказать биномиальный коэффициент - это асимптотическая большая тета двух до степени n?
Спасибо от @ LutzL-х внушения. Раньше я думал о приближении движения. 
O -часть должна быть легко. Выбор именно п/2 элементов из п является частным случаем выбора произвольных комбинаций из п элементов, т.е. решить для каждого из этих п элементов, следует ли выбрать его или нет.
Ом -part сложнее. На самом деле, plotting 4n/binomial(2 n, n) for moderately large n Я не вижу никаких признаков того, что это будет сглажено, чтобы оставаться ниже некоторой константы. Говоря интуитивно, чем больше n, тем более особенным является случай, когда вы произвольно выбираете n элементов и по совпадению случайно выбираете n/2 из них. Это вероятность того, должна стремиться к нулю, как п увеличивается, а это означает, что 2 п всегда должна расти быстрее, чем п выбрать п/2. Вы уверены, что правильно поняли эту часть своей задачи?
Вы можете использовать формулу Стирлинга для факториалов.
n! = sqrt(2*pi*(n+theta)) * (n/e)^n
где theta находится между 0 и 1, с сильной тенденцией к 0.
Спасибо, но с формулой Стирлинга я все еще не могу доказать нижнюю границу. Любое предложение? –
@xxx_yyyy Обратите внимание, что это * равенство *. Поэтому 'theta == 0' является нижней границей, а' theta == 1' является верхней границей. –
Вы не можете доказать нижнюю границу, так как это неправильно. Как вы уже выяснили, это должно быть в терминах '2^n/sqrt (n)'. – LutzL
Это не Тетя (2^n/sqrt (n)) и фактически выбирает (n, n/2) ~ 2^n/sqrt (pi * (n/2)) как n- > бесконечность). См. https://en.wikipedia.org/wiki/Central_binomial_coefficient
Спасибо за ваше мнение. Честно говоря, я не уверен, что нижняя граница 2^n верна. Есть ли нижняя граница, о которой вы можете думать? –
Но я видел, что оценка 2m выбирает m, которая, как представляется, имеет более высокую и нижнюю границу постоянных времен 4^n. –
В формуле по Стирлингу можно увидеть, что 'binom {2n} {n} = Theta (4^n/sqrt (n))'. Квадратный корневой фактор делает запрошенную нижнюю границу невозможной. Как вы можете протестировать через WA http://www.wolframalpha.com/input/?i=plot+4^n+%2F+sqrt%28n%29+%2F+binomial%282*n,+n%29+for + п + от + 0 + до + 1000 – LutzL