0
$\begingroup$

I need a generalized formula for a set having size(s) having below restrictions,

for ex. X = 2,7,11,17,26

I want only the first combination 2+7 & ignore all of the combinations that start from 2+? (2-num combinations only) same for 3-num consider 2+7+11 & ignore all 2+7+?

enter image description here

Formula should be applicable for any set X without size restriction.

$\endgroup$
  • $\begingroup$ Please clarify your question a bit. You write combinations but also write sums (2+7) but I assume you want the number of selections of 2 numbers drawn from $X = \{1, 7, 11, 17, 26\}$ without repetition and ignoring orderings (that's what combination usually means)? $\endgroup$ – ttnick Jun 24 at 8:14
  • $\begingroup$ for me sum of 2+7=9 or any combination is not important. I am interested in knowing what if we consider only the first combination & ignore all of the combinations in that particular branch then what will be the formula to know all of the first level combinations count. $\endgroup$ – Bhagwan Parge Jun 24 at 8:38
  • 1
    $\begingroup$ The question is very unclear and it is hard to figure out what you want to achieve. $\endgroup$ – Navjot Waraich Jun 24 at 9:13
  • 1
    $\begingroup$ @NavjotWaraich some information & image included for more clarity, hope it helps. $\endgroup$ – Bhagwan Parge Jun 24 at 11:04
1
$\begingroup$

$2^{n-1}-1$

Hint: 1) if you are summing with $k$ numbers $x_1,x_2,.., x_k$ note that once you choose upto $k-1$, last selection is forced on you as the next ascending number to $x_{k-1}$. 2) You are allowed to choose first $k-1$ numbers from n-1 numbers

$\endgroup$
0
$\begingroup$

First, let's count the number of 2-combinations. You already mentioned one combination: $(2,7)$, and then there are ${4 \choose 2}$ combinations for the remaining set $\{7, 11, 17, 26\}$:

$$S_2 = 1 + {4 \choose 2}$$

With 3-combinations you said you should include $(2, 7, 11)$. Then, there are ${4 \choose 3}$ combinations for choosing triplets from $\{7, 11, 17, 26\}$ and ${4 \choose 3}$ combinations for choosing triplets from $\{2, 11, 17, 26\}$.

But with the last two numbers, we have counted some stuff twice. Concretely, we need to subtract the number of 3-combinations made from $\{11, 17, 26\}$, which is ${3 \choose 3} = 1$.

$$S_3 = 1 + {4 \choose 3} + {4 \choose 3} - 1 = 2 {4 \choose 3}$$


In the end, you have $$S = 1 + {4 \choose 2} + 2 {4 \choose 3} = 1 + 6 + 8 = 15$$ combinations.

$\endgroup$
  • $\begingroup$ Thanks. Can you give a generalized formula (set with size n) $\endgroup$ – Bhagwan Parge Jun 24 at 11:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.