2014 dxdy logo

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

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




 
 Книги на полке, сочетания
Сообщение24.06.2014, 18:25 
Помогите разобраться:
Сколькими способами можно выбрать k книг из n, стоящих на полке, так, чтобы между любыми двумя выбранными было бы не менее m книг?

Нашла ограничение: $1\leqslant m\leqslant (n-k)/(k-1)$, иначе ничего не выйдет.

При $m=1$ получаем стандартную задачу о "не соседях", где число способов - $C^k_{n-k+1}$.

А вот при произвольном m получила (методом подбора) число способов - $C^k_{n-km+m}$.

Считает данная формула вроде бы верно, но не могу прийти к ней аналитически.

Помогите, пожалуйста!

 
 
 
 Re: Книги на полке, сочетания
Сообщение25.06.2014, 09:13 
По сравнению со случаем $m=1$: надо, помимо вычитания $k$ выбранных книжек, удалить еще по $(m-1)$ оставленных из каждого промежутка между соседними выбранными. Тогда остаётся невыбранных: $n-k-(k-1)(m-1)=n-km+m-1$. И надо поставить $k$ перегородок между ними или по краям, откуда и $C_{n-km+m}^k$.

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


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