PUMaC 2015 · 组合（A 组） · 第 1 题

PUMaC 2015 — Combinatorics (Division A) — Problem 1

[ 3 ] A word is an ordered, non-empty sequence of letters, such as word or wrod . How many distinct words can be made from a subset of the letters c, o, m, b, o , where each letter in the list is used no more than the number of times it appears?

解析

[ 3 ] A word is an ordered, non-empty sequence of letters, such as word or wrod . How many distinct words can be made from a subset of the letters c, o, m, b, o , where each letter in the list is used no more than the number of times it appears? Solution: We use casework on the length of the word. • There are 4 one-letter words: { c, o, m, b } . • There is 1 two-letter word with 2 o ’s and 4 · 3 = 12 two-letter words with at most one o for a total of 13. ( ) 3 • There are · 3 = 9 three-letter words with 2 o ’s (we choose the positions of the o ’s and 2 then choose the third letter) and 4 · 3 · 2 = 24 for a total of 33. • Note that the number of four-letter words is equal to the number of five-letter words, as 5! the last letter is determined by the first four, for a total of = 60 each. 2! Summing, we obtain a total of 170 words. Author: Bill Huang