1

Consider a sequence of $n$ objects where $n$ is odd. I need help counting the number of ways of selecting $k$ items where the middle object is never selected. Additionally, two selected items must have $h \geq 1$ items or more in between.

Inspired by this answer, I tried $\binom{k + (n - k - h(k - 1))}{k}=\binom{n - h(k - 1)}{k}$ which comes from there being $h(k - 1)$ minimum total space in between selected elements.

Of course this does not solve the whole problem, because in some instances the middle element is still being selected. I tried finding the number of times the middle element had been selected (to then subtract it from the previous result) but to no avail.

I also considered eliminating the middle element, spliting the sequence in half, and examining each distribution of selected elements between subsequences, but that ended in a big sum of combinations. Because I'll use this result in a computer program it is desirable that there are as few calculations as possible, so a fixed expression would be ideal.

How may I solve this problem?

cabralpinto
  • 135

1 Answers1

0

Firstly, it is better to say that there are $(2n+1)$ total slots so that there are $n$ slots on each side apart from the middle bar

You can have a max of $\lceil{\frac{n}{2}}\rceil = c,\;\;say$ selections on each side

If you select $a$ on the left side, you need to select $(k-a)$ on the right side, and you will need to work out separately for each partition of $k: 0-1,\;0-2,\;0-3,\;1-1,\;1-2,\;1-3,\;2-2,\;2-3,\;3-3$
with the asymmetrical ones having a mirror image

A few illustrations of how to work out for $n=5$ should put you on the way.

$\displaylines {k = 1,a =0 , k-a = 1\;\; or\;\; vice-versa: 2*\binom51 = 10}\\k =2, a=1, k-a=1: \binom51\binom51 = 25\;\;\; and\; so\; on.$

To explain the binomial coefficients, in the first case with just $1$ object to be selected from RHS, there will be $4$ unwanted objects with $5$ gaps where we can place $k-a\;: -\circ-\circ-\circ-\circ-$

You should now be able to work out for other cases, and encapsulate the formula, having studied the answer you cited

But you can't avoid summation of possibly a large number of cases , depending on how large $n$ is

true blue anil
  • 41,295
  • I was really trying to avoid the large summation of combinations, but unfortunately there doesn't seem to be a way. I'll try to find an efficent way to do it in my program. – cabralpinto Apr 14 '21 at 14:05
  • Yea, since a number of cases are being put together, summation is unavoidable, but on a computer that is no problem, all you have to do is to put the formula in terms of the variables in a loop. – true blue anil Apr 14 '21 at 15:51
  • The problem is that multiple calls to a combinations function actually end up getting quite expensive in the context I'm working on, so I'll probably end up using a dynamic programming approach. It's a bigger apparatus than what I initially had planned, but oh well. – cabralpinto Apr 14 '21 at 16:29