Skip to content

Homework 1

combi_spring_25_hw_1.pdf

Please explicitly state the principles of combinatorics you use in your solutions. If applicable, construct a bijection between sets to support your reasoning. While it is not necessary to show your work in detail, ensure that you identify any algebraic equations you are solving and double-check that your solutions are accurate.

  1. How many 4-digit numbers are there such that the sum of their digits is strictly less than 10? For example, the sum of the digits of 1023 is 6, and the sum of the digits of 4005 is 9.

    Assume the number is \((a,b,c,d)\), since it must be 4-digit, then \(a=1,\ldots,9\)​

    \(A_{i}:=\{(a,b,c,d)\mid a+b+c+d=i\}\)

    Then \(A=A_{1}\cup A_{2}\cup\ldots\cup A_{9}\)​

    And we know

    \(A_{1}=\{(0,0,0,0)\}\), then \(|A_{1}|=1=\binom{0+3}{3}\)​

    \(A_{2}=\{(2,0,0,0),,(1,1,0,0),(1,0,1,0),(1,0,0,1)\}\), then \(|A_{2}|=4=\binom{1+3}{3}\)​

    \(A_{3}=\left\lbrace\left(3,0,0,0\right),,\left(2,1,0,0\right),\left(2,0,1,0\right ),\left(2,0,0,1\right),,\left(1,1,1,0\right),\left(1,1,0,1\right),\left(1,0,1,1\right )\,,,\left(1,2,0,0\right),\left(1,0,2,0\right),\left(1,0,0,2\right)\right\rbrace\), then \(|A_{3}|=10=\binom{2+3}{3}\)

    .......

    \(|A_{9}|=\binom{8+3}{3}=165\)

    Interpretation: We can regard each number of digit be some balls, number 5 represents 5 balls

    If we calculate the possibilities of the sum of digits being \(i\), this is equivalent to that we need to separate \(i\) balls into \(4\) groups

    That is we need to insert \(3\) boards into \(i\) balls and the first group must have more than \(0\) ball and other groups can have \(0\) ball

    Thus we can add \(1\) ball to group 2,3,4 and remove it in the end, it won't change the result

    Thus we have \(i+3\) balls and need to separate into \(4\) groups and each group must have more than \(0\) ball

    And we have \(i+3-1\) positions to insert \(3\) boards

    Thus the result is \(\binom{i-1+3}{3}\)

    Thus use addition principle since they are all disjoint by definition. Then \(|A|=\sum_{i=1}^{9}\left|A_{1}\right|=\sum_{i=1}^{9}\binom{i-1+3}{3}=495\)​

  2. Find the number of ways to represent 7200 as a product of three natural numbers, such that none of them is divisible by 10. The representations that differ by the order of factors only are considered the same. E.g., \(8 \times 225 \times 4\) and \(4 \times 225 \times 8\) are the same representations.

    Let \(A\) be a set contains all the representation of 7200 as a product of three natural numbers such that none of them is divisible by 10

    Also, we know \(7200=8\times225\times4=2^{5}\times3^{2}\times5^{2}\), then these are factors of 7200

    Then each natural number shouldn't contain \(2,5\) at same time, assume \(7200=a\times b\times c\)

    Then we classify by the number of \(5\)

    1. \(a:5^2,b:5^0,c:5^0\)​

      Then \(2\) only can in \(b\) and \(c\)​

      1. \(a=5^{2}\times3^{2},b=2^{5},c=1\)

        \(a=5^{2}\times3^{2},b=2^{4},c=2^{1}\)​

        \(a=5^{2}\times3^{2},b=2^{3},c=2^{2}\) 2. \(a=5^{2}\times3^{1},b=3\times2^{5},c=1\)​

        \(a=5^{2}\times3^{1},b=3\times2^{4},c=2^{1}\)

        \(a=5^{2}\times3^{1},b=3\times2^{3},c=2^{2}\)​

        \(a=5^{2}\times3^{1},b=2^{5},c=3\)

        \(a=5^{2}\times3^{1},b=2^{4},c=3\times2^{1}\)

        \(a=5^{2}\times3^{1},b=2^{3},c=3\times2^{2}\) 3. \(a=5^{2},b=3^{2}\times2^{5},c=1\)

        \(a=5^{2},b=3^{2}\times2^{4},c=2\)​

        \(a=5^{2},b=3^{2}\times2^{3},c=2^{2}\)

        \(a=5^{2},b=3\times2^{5},c=3\)​

        \(a=5^{2},b=3\times2^{4},c=3\times2\)

        \(a=5^{2},b=3\times2^{3},c=3\times2^{2}\)​

        \(a=5^{2},b=2^{5},c=3^{2}\)

        \(a=5^{2},b=2^{4},c=3^{2}\times2\)

        \(a=5^{2},b=2^{3},c=3^{2}\times2^{2}\)​ 2. \(a:5^{1},b:5^{1},c:5^{0}\)

      Then \(2\) can only in \(c\)​

      1. \(a=5\times3^{2},b=5,c=2^{5}\)

      2. \(a=5\times3,b=3\times5,c=2^{5}\)

        \(a=5\times3,b=5,c=3\times2^{5}\) 3. \(a=5,b=3^{2}\times5,c=2^{5}\)(is repeated)

        \(a=5,b=5,c=3^{2}\times2^{5}\)

        \(a=5,b=3\times5,c=3\times2^{5}\)(is repeated)

    Finally, by addition principle we have \(22\) possibilities

  3. Out of 50 students, 25 can speak French, 18 can speak Russian, and 12 can speak Spanish. 8 can speak French and Russian, 6 can speak French and Spanish, and 4 can speak Russian and Spanish. 3 students speak all three languages. How many students speak none of these languages?

    \(50\) students in total — \(T\)

    \(F\subset T\) — subset of students who speak French. 25
    ​\(R\subset T\) — subset of students who speak Russian. 18

    \(S\subset T\) — subset of students who speak Russian. 12

    \(\left|F\cap R\right|=8\), \(\left|F\cap S\right|=6\), \(\left|R\cap S\right|=4\), \(\left|F\cap R\cap S\right|=3\)

    Since the number of students who speak at least one of these languages(\(O\)) is disjoint to students speak none of these languages(\(N\)​)

    And the sum of these two is \(T\)

    Thus we can compute the number of students who speak at least one of these languages, then use subtraction principle since \(N=T\setminus O\)

    Then assume \(O=x\)

    speak only one language

    \(|F|-\left(|F\cap R|-|F\cap R\cap S|\right)-\left(\left|F\cap S\right|-|F\cap R\cap S|\right)-|F\cap R\cap S|=25-\left(8-3\right)-\left(6-3\right)-3=14\) since subtraction principle

    \(|R|-\left(|R\cap S|-|F\cap R\cap S|\right)-\left(\left|R\cap F\right|-|F\cap R\cap S|\right)-|F\cap R\cap S|=18-\left(4-3\right)-\left(8-3\right)-3=9\)

    \(|S|-\left(|F\cap S|-|F\cap R\cap S|\right)-\left(\left|S\cap R\right|-|F\cap R\cap S|\right)-|F\cap R\cap S|=12-\left(4-3\right)-\left(6-3\right)-3=5\)

    speak exactly two language

    \(|F\cap R|-|F\cap R\cap S|=8-3=5\)

    \(|F\cap S|-|F\cap R\cap S|=6-3=3\)

    \(|S\cap R|-|F\cap R\cap S|=4-3=1\)

    Then \(|O|=\left(14+9+5\right)+\left(5+3+1\right)+3=40\) since addition principle

    Thus \(|N|=|T|-|O|=10\) since subtraction principle

  4. Consider all 3-letter words formed using the letters of the English alphabet. Two words are called similar if one can be obtained from the other by shifting each of its letters by the same number of positions in the alphabet. For example, the words acz and cfb are similar because each letter in acz is shifted by 2 positions to obtain the corresponding letter in cfb:

    • \(a \to c\);
    • \(c \to f\);
    • \(z \to b\);

    How many distinct 3-letter words are there, up to similarity (saying differently, how many equivalence classes of similar words are there)?

    We should fix the first letter, then consider the difference of two nearby letter

    For example, \(abd\), the difference is \(1,2\) since \(a\to b\) is 1 and \(b\to d\) is 2 written as \((1,2)\)

    Then the classed of similar words is determined by the difference between \(a\), \(b\) and \(c,d\)

    Thus we only need to count the possibilities of difference is \(26\)

    Then the difference between \(a\), \(b\) and \(c,d\) can be (0,0),...,(0,26),(1,0),...,(1,26),...,(26,0),...,(26,26)

    Then use addition principle since these are disjoint

    Then the possibility is \(\underbrace{26+...+26}_{26\text{ times }}=26^{2}=676\)​

‍