H Operator in Combinatorics
This article was shared by 2014 MMC National Finalist Daniel James Molina. I am also fascinated with how this operator works. It is also my first time to hear that there is an H operator in combinatorics.
“Seriously, when I read the article about Kuya Micah’s solution, (stars and bars combination thing), It really blew my mind. I can’t understand stars and bars combination, because I have another kind of solution similar to him, thanks to KUMON.” – Daniel
We all know the Combinatorics symbols, C (non-repeated combination), P (non-repeated permutation), and the large π symbol (repeated permutation).
And know, I will share my knowledge of another symbol, which is H (repeated combination).
The identity goes like this: NHR = N+R-1CR
nHr means “ combination of n objects taken r at a time such that any of the n objects can be repeated”
Application of the function:
Sample Problem 1:
Find the number of non-negative integers that satisfy
Sample Problem 2:
Find the number of positive integers that satisfy
we can find the answer by deducing it by finding the number of sets of non-negative integers that satisfy
, (A,B,C are non-negative integers)
4H11 = 14C11 = 728 sets.
What we did is changing to ,since x,y,z and w have minimal value of 1 each. At least we can change it to variables that have a minimal value of 0 for easier calculations.
Sample Problem 3:
There are 30 voters and 10 candidates in an election. In how many ways can the candidates receive their votes?
Let a,b,c,d,e,f,g,h,i,j be the candidates.
since all candidates can be given no vote,
a,b,c,d,e,f,g,h,i, and j are non-negative integers.
The number of ways is 10H30 = 39C30 = 211915132
Sample Problem 4:
How many ways can you choose from 5 different fruits taken 7 at a time?
If you will choose 7 from the 5 fruits without repetition, you will only have 5 fruits chosen, so this problem is a repeated combination problem.
5H7 = 11C7 = 330 ways
Sample Problem 5:
How many ways can you group 10 people into 4 groups such that each group consist of at LEAST 2 people.
Let A, B, C and D are the groups.
so from A + B + C + D = 10,
It will be,
4H2 = 5C2 = 10 ways.