2
$\begingroup$

Suppose I have a number $N$, In how many ways can I choose any number of numbers from $[1, N)$, such that if I choose $t$ numbers which are denoted by $P_i$, then the following conditions are satisfied.

$P_1 \leq K$ where $ 1 \leq K \leq N$

$N - P_t \leq K $

$P_i - P_{i-1} \leq K$

Example

  1. N = 10, K = 6

So, the number of ways I can choose numbers are,

$((4), (5), (6))$

$((1, 4),(1, 5), (1, 6), (1, 7), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8) \space .......... )$

$.$

$.$

$.$

$.$

$.$

$(1, 2,3,4,5,6,7,8,9)$

Till now, I could only think of

Ans = Number of ways $\frac{N}{K}$ number can be selected + number of ways $\frac{N}{K} + 1$ numbers can be selected + ... + Number of ways N - 1 numbers can be selected.

But I am having a tough time going ahead of this. How do I proceed mathematically. Can I get a general formula?

$\endgroup$
  • $\begingroup$ For specifically $t$ numbers selected, instead of looking at the $t$-tuple $(P_1,P_2,\dots,P_t)$ look instead at the $(t+1)$-tuple $(P_1,P_2-P_1,P_3-P_2,\dots,P_t-P_{t-1},N-P_t)$. Let us relabel these entries as $(x_1,x_2,\dots,x_{t+1})$. Notice then that we are asking how many solutions there are to the system $\begin{cases} x_1+x_2+\dots+x_{t+1}=N\\ 1\leq x_i\leq K~~~\forall i\in\{1,2,\dots,t\}\\1\leq x_{t+1}\end{cases}$. Proceed as normal via stars-and-bars and inclusion-exclusion and sum over all possible values of $t$. $\endgroup$ – JMoravitz May 14 '17 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.