2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Отношение количества размещений к сочетаниям
Сообщение04.12.2015, 21:34 
Добрый день.
Побочно проводимой работе возникла небольшая математическая задачка, заключающаяся в определении поведения функции отношения между сочетаниями с повторениями и размещениями с повторениями при тех же параметрах n и k (по терминологии википедии). В качестве функции отношения, по известным причинам, выбрано отношение логарифмов по k. Если учитывать только главные степени, то данная аппроксимация говорит об асимптотике k. Однако численный эксперимент в matlab говорит о гладкой функции графиком отдалёно напоминающим $xe^{-x}$ с максимумом в районе 3-4 и с другим снижением.
Таким образом, вопрос стоит следующим образом: дан биномиальный коэффициент
$\left( \begin{array}{c} n+k-1 & k \end{array} \right)=\frac{\left(n+k-1\right)!}{k!\left(n-1\right)!}$
Найти функцию от n и k (или только от k при заданном n) или её асимптотику при $n\to\infty$. Есть ли предел при $k\to n$
$f\left(n,k\right)=\frac{n}{\log _k \left(\frac{\left(n+k-1\right)!}{k!\left(n-1\right)!}\right)}$
Скорее всего есть известное готовое решение, но с наскока в интернете найти его не удалось.

 
 
 
 Re: Отношение количества размещений к сочетаниям
Сообщение05.12.2015, 08:22 
Максимум, как и всегда у биномиального коэффициента, будет при $2k=n+k-1$.
Асимптотику найти по двум переменным не всегда возможно. Если нужна асимптотика максимума, то подставляйте $k$, дающее максимум.

Korban5 в сообщении #1079545 писал(а):
Есть ли предел при $k\to n$
$f\left(n,k\right)=\frac{n}{\log _k \left(\frac{\left(n+k-1\right)!}{k!\left(n-1\right)!}\right)}$
А это - тривиальный вопрос. В чем конкретные затруднения?

 
 
 
 Re: Отношение количества размещений к сочетаниям
Сообщение05.12.2015, 09:20 
Цитата:
Максимум, как и всегда у биномиального коэффициента, будет при $2k=n+k-1$.

Наверное не правильно выразился, интересно поведение функции на интервале от $[0;n]$ при заданном $n$, и особенно в районе максимума при небольших $k$. Может в понедельник постараюсь вставить рисунок. График идёт следующим образом, резко возрастает до $3-4$ по $k$, а затем идёт медленный спад. Хотелось бы получить какую-нибудь аналитическую аппроксимацию данного процесса.
Цитата:
Есть ли предел при $k\to n$

Имелось в виду его значение. Не получилось разобраться с верхним факториалом ("rising factorial").

 
 
 
 Re: Отношение количества размещений к сочетаниям
Сообщение05.12.2015, 09:38 
Korban5 в сообщении #1079672 писал(а):
Наверное не правильно выразился, интересно поведение функции на интервале от [0;n] при заданном n, и особенно в районе максимума при небольших k

Ответ тот же:
Sonic86 в сообщении #1079660 писал(а):
Максимум, как и всегда у биномиального коэффициента, будет при $2k=n+k-1$.
Да и вообще: пусть есть последовательность $a_k$. Надо найти максимум. А что такое максимум? Максимум - это такое $r$, что $a_{r-1}<a_r>a_{r+1}$. Получаем неравенство, сидим, решаем, глядишь - чего-то получится.

Korban5 в сообщении #1079672 писал(а):
мелось в виду его значение. Не получилось разобраться с верхним факториалом ("rising factorial").
Что конкретно не получилось? (Вы же читали правила форума, да?)

 
 
 
 Re: Отношение количества размещений к сочетаниям
Сообщение05.12.2015, 09:43 
 i  Korban5 Оформляйте все формулы, пожалуйста. Исправлено.

 
 
 
 Re: Отношение количества размещений к сочетаниям
Сообщение05.12.2015, 10:49 
Цитата:
Максимум, как и всегда у биномиального коэффициента, будет при $2k=n+k-1$.

В контексте функции $f\left(n,k\right)=\frac{n}{\log _k \left(\frac{\left(n+k-1\right)!}{k!\left(n-1\right)!}\right)}$
Это должен быть минимум.
Ситуация следующая, для того чтобы примерно понять поведение функции был рассмотрен многочлен $x\left(x+1\right)\left(x+2\right)...$ делённый на $k!$.
В первом приближении взяли только наибольшую степень и применив формулу стирлинга получили приближение $f\left(k\right)\approx{k}. Построив график функции обнаружил, что её поведение существенно отличается.
В принципе достаточно два параметра зависимость значение максимума и его аргумента от n, а так же приближённое выражение для снижения функции в дальнейшем по k.
Понятно, вопрос был задан не правильно. Показалось, что отношение между числом размещений с повторениями и сочетаний с повторениями должно было быть уже где-то рассмотрено. Попробую дальше сам.

 
 
 
 Re: Отношение количества размещений к сочетаниям
Сообщение06.12.2015, 13:38 
Цитата:
Максимум, как и всегда у биномиального коэффициента, будет при $2k=n+k-1$.

Неверно,
$\left(\left( \begin{array}{c} n & k \end{array} \right)\right)=$\left( \begin{array}{c} n+k-1 & k \end{array} \right)=\frac{\left(n+k-1\right)!}{k!\left(n-1\right)!}$
Неубывающая функция от k.
Для первоначальной функции отношений логарифмов, перевернув её, применяя везде Стирлинга и выведя $\ln{k}$ в числитель нашёл аппроксимацию $\frac{k}{\ln{k}}$ с минимумом в $e$ (т.е. 3). Для меня в принципе достаточно.
Вот ещё что получилось, вроде бы тоже правильно.
Само выражение очень похоже на определение гамма функции через предел
$\Gamma\left(t\right)=\lim_{n\to\infty} \frac{n!n^t}{t\left(t+1\right)\ldots\left(t+n\right)}$
(Если есть ссылка на этот предел не в википедии, то киньте сюда пожалуйста)
Если рассматриваем только целые числа, то получим предел
$\Gamma\left(t\right)=\lim_{n\to\infty} \frac{\left(t-1\right)!n!n^t}{\left(t+n\right)!}$
Учитывая, что $\Gamma\left(t+1\right)=t!$ делам замену переменной $k=t+1$, тогда
$\Gamma\left(k-1\right)=\lim_{n\to\infty} \frac{\left(k-2\right)!n!n^{k-1}}{\left(k-1+n\right)!}$
$\Gamma\left(k-1\right)= \frac{1}{k\left(k-1\right)}\lim_{n\to\infty} \frac{k!n!n^k}{n\left(k-1+n\right)!}$
$\Gamma\left(k-1\right)= \frac{1}{k\left(k-1\right)}\lim_{n\to\infty} \frac{k!\left(n-1\right)!n^k}{\left(k-1+n\right)!}$
$\frac{k!\left(n-1\right)!n^k}{\left(k-1+n\right)!} = n^k/{$\left( \begin{array}{c} n+k-1 & k \end{array} \right)}=f(k)$
$f(k)=$k\left(k-1\right)$\Gamma\left(k-1\right)
$f(k)=k$\Gamma\left(k\right)
$f(k)=$\Gamma\left(k+1\right)=k!

 
 
 
 Re: Отношение количества размещений к сочетаниям
Сообщение06.12.2015, 20:56 
Да вроде всё сходится. Только отношение конечно надо изначально было искать не логарифм $\log _k \left(x\right)$, а корень по k, т.е. $x^{1/k}$

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group