<<DiscreteMath`Combinatorica`

Problem 15

How many solutions of  (Subscript[x, 1]) + (Subscript[x, 2]) + (Subscript[x, 3]) + (Subscript[x, 4]) + (Subscript[x, 5]) = 21?

(Subscript[x, 1]) ≥ 1?

Binomial[21 - 1 + 4, 4]

If (Subscript[x, 1]) ≥ 2,  (Subscript[x, 2]) ≥ 2,  
      (Subscript[x, 3]) ≥ 2,  
      (Subscript[x, 4]) ≥ 
        2,  (Subscript[x, 5])≥2 ?

Binomial[21 - 10 + 4, 4]

(Subscript[x, 1]) ≤ 10?

Binomial[21 + 4, 4] - Binomial[21 - 11 + 4, 4]

Sum[Binomial[21 + 3 - k, 3], {k, 0, 10}]

(Subscript[x, 1]) ≤ 3, 1 ≤ (Subscript[x, 2]) ≤ 3 and (Subscript[x, 3]) ≥ 15?

x1g3 = Binomial[21 - 4 + 4, 4]

x2r = 
      Binomial[21 - 1 + 3, 3] + Binomial[21 - 2 + 3, 3] + 
        Binomial[21 - 3 + 3, 3]

x3g14 = Binomial[21 - 15 + 4, 4]

x3g14c = 
      Binomial[(21 - 15 - 4) - 1 + 3, 3] + 
        Binomial[(21 - 15 - 4) - 2 + 3, 3] + 
        Binomial[(21 - 15 - 4) - 3 + 3, 3]

x3g14r = 
      Binomial[(21 - 15) - 1 + 3, 3] + 
        Binomial[(21 - 15) - 2 + 3, 3] + 
        Binomial[(21 - 15) - 3 + 3, 3]

x3g14r - x3g14c

Or, easier way:

restriction on (Subscript[x, 3]) and a part of (Subscript[x, 2])

Binomial[(21 - 15 - 1) + 4, 4]

How many solutions of  (Subscript[y, 1]) + (Subscript[y, 2]) + (Subscript[y, 3]) + (Subscript[y, 4]) + (Subscript[y, 5]) = 5 such that (Subscript[y, 1]) ≤ 3 and (Subscript[y, 2]) ≤ 2?  Look at the complement: How many solutions such that (Subscript[y, 1]) > 3 or (Subscript[y, 2]) > 2? These are disjoint sets.

Binomial[(5 - 4) + 4, 4]

Binomial[(5 - 3) + 4, 4]

Problem 16

How many solutions of  (Subscript[x, 1]) + (Subscript[x, 2]) + (Subscript[x, 3]) + (Subscript[x, 4]) + (Subscript[x, 5]) + (Subscript[x, 6]) = 29?

Binomial[34, 5]

If (Subscript[x, 1]) ≥ 1,  (Subscript[x, 2]) ≥ 2,  
      (Subscript[x, 3]) ≥ 3,  (Subscript[x, 4]) ≥ 4,  
      (Subscript[x, 5]) ≥ 
        6,  (Subscript[x, 6])≥6 ?

Binomial[12, 5]

(Subscript[x, 1]) ≤ 5?

Binomial[34, 5] - Binomial[28, 5]

Sum[Binomial[33 - k, 4], {k, 0, 5}]

(Subscript[x, 1]) ≤ 7 and (Subscript[x, 2]) ≥ 9?

x2g8 = Binomial[20 + 5, 5]

x1g7 = Binomial[21 + 5, 5]

x2g8x1g7 = Binomial[12 + 5, 5]

x2g8 - x2g8x1g7

Problem 20

Binomial[11 + 3, 3]

Length[
      Select[Flatten[Table[{x, y, z}, {x, 0, 11}, {y, 0, 11}, {z, 0, 11}], 
          2], (Apply[Plus, #] < 12) &]]

Problem 23

((12!)/(((2!))^6))

(* The second way is by the product rule :  
          There are 12 choose 2 ways of selecting the red team,  
      there are 10 choose 2 ways of selecting green team,  
      there are 8 choose 2 ways of selecting blue team,   ...  *)

Product[Binomial[2 k, 2], {k, 6, 1, -1}]

Problem 25

How many positive integers less than (10^6) have the sum of their digits equal to 19.

Binomial[24, 5] - 6 Binomial[14, 5]

Length[
      Select[IntegerDigits[#] & /@ 
          Range[999999], (Apply[Plus, #] == 19) &]]

How about the sum is 20

Length[
      Select[IntegerDigits[#] & /@ 
          Range[999999], (Apply[Plus, #] == 20) &]]

Binomial[25, 5] - (6 Binomial[15, 5] - Binomial[6, 2])

How about the sum is 21

Length[
      Select[IntegerDigits[#] & /@ 
          Range[999999], (Apply[Plus, #] == 21) &]]

Binomial[26, 
        5] - (6 Binomial[16, 5] - 2  Binomial[6, 2])

Problem 26

How many positive integers less than (10^6) have the sum of their digits equal to 13 and exactly one digit equal to 9.

Binomial[13 + 5, 5] - 6  Binomial[3 + 5, 5]

Binomial[13 + 5, 5] - 6  Binomial[4 + 5, 5]

(Binomial[13 + 5, 5] - 
          6  Binomial[3 + 5, 5]) - (Binomial[13 + 5, 5] - 
          6  Binomial[4 + 5, 5])

6 Binomial[4 + 4, 4]

Length[
      Select[IntegerDigits[#] & /@ 
          Range[999999], (And[Apply[Plus, #] == 13, 
              Max[#] == 9]) &]]

Problem 27

There arc 10 questions on a discrete mathematics final exam. How many ways are there to assign scores to the problems if the sum of the scores is 100 and each question is worth at least 5 points?

Binomial[50 + 9, 9]

Binomial[50 + 9, 9]

Problem 33

3     + 
   + 
1     +  
2*2     +  
2     +  
   + 
1     +  
Binomial[3, 2]*2      +  
Binomial[3, 1]*2      +  
   + 
Binomial[4, 
            3]*2     +  
Binomial[4, 2]*2     +  
   
Binomial[5, 3] 
        2

Notice

5!/3!

Binomial[5, 3] Binomial[2, 1]

A similar explanation.

{O, R, O, N, O}

Binomial[3, 1]    + (3*2 + 1)    + (3*2*1 + Binomial[3, 2]*2  + 1)    + ( 
        Binomial[4, 2]*2  + Binomial[4, 3]*2 )    + ((5!)/(3!))

Problem 34

SEERESS

Strings of length 5

There are 3^5 = 243 strings of length 5 using these three characters. Out of these 243 strings there are 90 strings that use one of these 3 Es, 1 R and 1 S, or 3 Es, 0 R and 2 S, or 2 Es, 1 R and 2 Ss, or 2 Es, 0 R and 3 Ss, or 1 E, 1 R and 3 Ss.  That is there are 90 strings of length 5 that can be formed from these 7 characters. Below is Mathematica proof of that. The corresponding calculation is as follows

((5!)/(3! 1! 1!)) + ((5!)/(3! 0! 2!)) + ((5!)/(2! 1! 2!)) + ((5!)/(2! 0! 3!)) + ((5!)/(1! 1! 3!))

Mathematica selects all such strings in the following command. We had to identify E to 0, R to 1, S to 2 to do the selection.

Length[
      Select[Strings[{0, 1, 2}, 5], 
        Function[y, 
          Or[(Sort[y]) == {0, 0, 0, 1, 2}, (Sort[y]) == {0, 0, 0, 2, 
                2}, (Sort[y]) == {0, 0, 1, 2, 2}, (Sort[y]) == {0, 0, 
                2, 2, 2}, (Sort[y]) == {0, 1, 2, 2, 2}]]]]

Strings of length 6.

3^6

There are 3^5 = 729 strings of length 6 using these three characters. Out of these 729 strings there are 140 strings that use one of these 3 Es, 1 R and 2 Ss, or 3 Es, 0 R and 3 Ss, or 2 Es, 1 R and 3 Ss.  That is there are 90 strings of length 5 that can be formed from these 7 characters. Below is Mathematica proof of that. The corresponding calculation is as follows

((6!)/(3! 1! 2!)) + ((6!)/(3! 0! 3!)) + ((6!)/(2! 1! 3!))

Mathematica selects all such strings in the following command. We had to identify E to 0, R to 1, S to 2 to do the selection.

Length[
      Select[Strings[{0, 1, 2}, 6], 
        Function[y, 
          Or[(Sort[y]) == {0, 0, 0, 1, 2, 2}, (Sort[y]) == {0, 0, 0, 
                2, 2, 2}, (Sort[y]) == {0, 0, 1, 2, 2, 2}]]]]

Strings of length 7.

There are 140 such strings.

((7!)/(3! 1! 3!))

Mathematica selects all such strings in the following command. We had to identify E to 0, R to 1, S to 2 to do the selection.

Length[
      Select[Strings[{0, 1, 2}, 7], 
        Function[y, Or[(Sort[y]) == {0, 0, 0, 1, 2, 2, 2}]]]]

Problem, similar smaller

FEEL

Strings of length 3

3^3

There are 3^3 = 27 strings of length 3 using these three characters. Out of these 27 strings there are ?? strings that use one of these 3 Es, 1 R and 1 S, or 3 Es, 0 R and 2 S, or 2 Es, 1 R and 2 Ss, or 2 Es, 0 R and 3 Ss, or 1 E, 1 R and 3 Ss.  That is there are 90 strings of length 5 that can be formed from these 7 characters. Below is Mathematica proof of that. The corresponding calculation is as follows

((3!)/(1! 2! 0!)) + ((3!)/(1! 1! 1!)) + ((3!)/(0! 2! 1!))

Mathematica selects all such strings in the following command. We had to identify E to 0, F to 1, L to 2 in order to do the selection.

Length[
      Select[Strings[{0, 1, 2}, 3], 
        Function[y, 
          Or[(Sort[y]) == {0, 1, 1}, (Sort[y]) == {0, 1, 
                2}, (Sort[y]) == {1, 1, 2}]]]]

Strings of length 4.

3^4

There are 3^4 = 81 strings of length 4 using these three characters. Out of these 81 strings there are 12 strings that use 2 Es, 1 F and 1 L. Below is Mathematica proof of that. The corresponding calculation is as follows

((4!)/(1! 2! 1!))

Mathematica selects all such strings in the following command. We had to identify E to 0, R to 1, S to 2 to do the selection.

Length[
      Select[Strings[{0, 1, 2}, 4], 
        Function[y, Or[(Sort[y]) == {0, 1, 1, 2}]]]]

Total 24.

Problem, similar smaller

SEEDS

Strings of length 3

There are 3^3 = 27 strings of length 3 using these three characters. Out of these 27 strings there are ?? strings that use one of these 3 Es, 1 R and 1 S, or 3 Es, 0 R and 2 S, or 2 Es, 1 R and 2 Ss, or 2 Es, 0 R and 3 Ss, or 1 E, 1 R and 3 Ss.  That is there are 90 strings of length 5 that can be formed from these 7 characters. Below is Mathematica proof of that. The corresponding calculation is as follows

((3!)/(1! 2! 0!)) + ((3!)/(1! 1! 1!)) + ((3!)/(0! 2! 1!)) + ((3!)/(0! 1! 2!))

Mathematica selects all such strings in the following command. We had to identify D to 0, E to 1, S to 2 in order  to do the selection.

Length[
      Select[Strings[{0, 1, 2}, 3], 
        Function[y, 
          Or[(Sort[y]) == {0, 1, 1}, (Sort[y]) == {0, 1, 
                2}, (Sort[y]) == {1, 1, 2}, (Sort[y]) == {1, 2, 
                2}]]]]

Strings of length 4.

3^4

There are 3^4 = 81 strings of length 4 using these three characters. ??? strings of length 4 that can be formed from these 7 characters. Below is Mathematica proof of that. The corresponding calculation is as follows

((4!)/(1! 2! 1!)) + ((4!)/(1! 1! 2!)) + ((4!)/(0! 2! 2!))

Mathematica selects all such strings in the following command. We had to identify E to 0, R to 1, S to 2 to do the selection.

Length[
      Select[Strings[{0, 1, 2}, 4], 
        Function[y, 
          Or[(Sort[y]) == {0, 1, 1, 2}, (Sort[y]) == {0, 1, 2, 
                2}, (Sort[y]) == {1, 1, 2, 2}]]]]

Strings of length 5.

There are 140 such strings.

((5!)/(1! 2! 2!))

Mathematica selects all such strings in the following command. We had to identify E to 0, R to 1, S to 2 to do the selection.

Length[
      Select[Strings[{0, 1, 2}, 5], 
        Function[y, Or[(Sort[y]) == {0, 1, 1, 2, 2}]]]]

Total 75.

Problem 35

EVERGREEN

(4)E to 0, (1) G to 1, (1)N to 2, (2)R to 3, (1)V to 4

Strings of length 7

5^7

There are 5^7 = 78125 strings of length 7 using these five characters. Out of these 78125 strings there are ?? strings that use appropriate counts of each letter.  That is there are 90 strings of length 5 that can be formed from these 7 characters. Below is Mathematica proof of that. The corresponding calculation is as follows

((7!)/(4! 1! 1! 1! 0!)) + ((7!)/(4! 1! 1! 0! 1!)) + ((7!)/(4! 1! 0! 2! 0!)) + ((7!)/(4! 1! 0! 1! 1!)) + ((7!)/(4! 0! 1! 1! 1!)) + ((7!)/(4! 0! 0! 2! 1!)) + ((7!)/(3! 1! 1! 2! 0!)) + ((7!)/(3! 1! 1! 1! 1!)) + ((7!)/(3! 1! 0! 2! 1!)) + ((7!)/(3! 0! 1! 2! 1!)) + ((7!)/(2! 1! 1! 2! 1!))

Mathematica selects all such strings in the following command. We had to identify E to 0, G to 1, N to 2, R to 3, V to 4 in oeder to do the selection.

Length[
      Select[Strings[{0, 1, 2, 3, 4}, 7], 
        Function[y, 
          Or[(Sort[y]) == {0, 0, 0, 0, 1, 2, 3}, (Sort[y]) == {0, 0, 
                0, 0, 1, 2, 4}, (Sort[y]) == {0, 0, 0, 0, 1, 3, 
                3}, (Sort[y]) == {0, 0, 0, 0, 1, 3, 
                4}, (Sort[y]) == {0, 0, 0, 0, 2, 3, 
                4}, (Sort[y]) == {0, 0, 0, 0, 3, 3, 
                4}, (Sort[y]) == {0, 0, 0, 1, 2, 3, 
                3}, (Sort[y]) == {0, 0, 0, 1, 2, 3, 
                4}, (Sort[y]) == {0, 0, 0, 1, 3, 3, 
                4}, (Sort[y]) == {0, 0, 0, 2, 3, 3, 
                4}, (Sort[y]) == {0, 0, 1, 2, 3, 3, 4}]]]]

Strings of length 8.

5^8

There are 5^8 = 390625 strings of length 8 using these five characters. Out of these 390625 strings there are ???? strings that use appropriate number of each letter.   Below is Mathematica proof of that. The corresponding calculation is as follows

((8!)/(4! 1! 1! 2! 0!)) + ((8!)/(4! 1! 1! 1! 1!)) + ((8!)/(4! 1! 0! 2! 1!)) + ((8!)/(4! 0! 1! 2! 1!)) + ((8!)/(3! 1! 1! 2! 1!))

Mathematica selects all such strings in the following command. We had to identify E to 0, G to 1, N to 2, R to 3, V to 4 in oeder to do the selection.

Length[
      Select[Strings[{0, 1, 2, 3, 4}, 8], 
        Function[y, 
          Or[(Sort[y]) == {0, 0, 0, 0, 1, 2, 3, 3}, (Sort[y]) == {0, 
                0, 0, 0, 1, 2, 3, 4}, (Sort[y]) == {0, 0, 0, 0, 1, 3, 3, 
                4}, (Sort[y]) == {0, 0, 0, 0, 2, 3, 3, 
                4}, (Sort[y]) == {0, 0, 0, 1, 2, 3, 3, 4}]]]]

Strings of length 9.

5^9

There are 5^9 = 1953125 such strings

There are 7560 strings which use 4 Es, 1 G, 1 N, 2 Rs, 1 V.

((9!)/(4! 1! 1! 2! 1!))

Mathematica selects all such strings in the following command. We had to identify E to 0, G to 1, N to 2, R to 3, V to 4 in oeder to do the selection.

Length[
      Select[Strings[{0, 1, 2, 3, 4}, 9], 
        Function[y, 
          Or[(Sort[y]) == {0, 0, 0, 0, 1, 2, 3, 3, 4}]]]]

Problem 39

We have to make 12 steps: 4 in x drection, 3 in y direction and 5 in z direction. This is exactly the same as counting the number of strings of 12 characters  {x, x, x, x, y, y, y, z, z, z, z, z}

(((4 + 3 + 5)!)/(3! 4! 5!))

For a 3x3x3 cube that would be:

(((3 + 3 + 3)!)/(3! 3! 3!))