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.

h operator“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 x+y+z=15

Solution:

3H15=3+15-1C15=136

Sample Problem 2:

Find the number of positive integers that satisfy w+x+y+z=15

Solution:

Since w,x,y,z \geq 1,

we can find the answer by deducing it by finding the number of sets of non-negative integers that satisfy

A+B+C+D=11,  (A,B,C are non-negative integers)

4H11 = 14C11 = 728 sets.

What we did is changing w+x+y+z=15 to A+B+C+D=11,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.

w+x+y+z =15 \to (A+1)+(B+1)+(C+1)+(D+1)=15

[The “derivation”]

Sample Problem 3:

There are 30 voters and 10 candidates in an election. In how many ways can the candidates receive their votes?

Solution:

Let a,b,c,d,e,f,g,h,i,j be the candidates.

a+b+c+\dots+i+j=30

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?

Solution:

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.

Solution:

Let A, B, C and D are the groups.

A+B+C+D=10

and A,B,C,D\geq 2
so from A + B + C + D = 10,

It will be,

(x+2)+(y+2)+(z+2)+(w+2)=10

x+y+z+w=2

4H2 = 5C2 = 10 ways.

Latest posts by Daniel James Agsaullo Molina (see all)

You may also like...