( 9 points) Jared is asked in class to decode a message by reordering letters in a certain order, but unfortunately, they never learned how to read. Jared can only distinguish what each letter looks like, and is trying every possible ordering of letters, since they cannot read. Thus far, they only know the letters of the first part of the message: aeeegginnnoopruuvvy There are 19 total characters in the first part of the message. (a) (3 points) In how many ways can Jared order the letters (without spaces)? (Note that repeated letters are considered identical. For example, the first 'e' in the string is indistinguishable from the other two 'e' characters in the string) (b) (3 points) Taking pity on Jared, the instructor, Dr Astley, gives them the full words in the message to arrange to the correct message, and lets them know that 'never' is always immediately followed by 'gonna'. Jared, still unable to read, attempts every valid ordering possible with this newfound information. In total, there are 28 words, and 19 distinct words, in this message. In how many ways can Jared order these words? (repeated words, like 'you' are considered the same as the other instances of 'you' in the string) Below is a table of each of the counts of words, followed by a list of words that have that count in the message: (c) (3 points) Next, Prof Astley wants to arrange the words in the message using the words from part c) into a circle, while rotating the message around, so that the message scrolls around the circle indefinitely. In doing so, because of the rotation, some messages are considered indistinct from others. For example if the message was "never gonna give you up" arranged in a circle clockwise in that order, this is considered indistinguishable from the message "up never gonna give you" since the first message can be rotated around to match the second message. With the same words and counts as part c), and with "never" always immediately followed by "gonna", in how many ways can Jared arrange these words in a circle? (12 points) A little Snek is trying to travel from the bottom left corner of a grid, at (0,0), to the top-right of the grid, at (6,9), to get the Mouse sitting at (6,9) so that they can "become friends". The grid is shown below: The snake can only move along the grid lines and can move 1 unit at a time either to the right, or up. (a) (3 points) How many different ways can the Snek travel from the bottom left corner (0,0) to the top right corner (6,9) only by moving to the right or up? (b) (3 points) Suppose that there is cheese that the Snek wants to pick up at (2,4) for a "gift". How many ways can the Snek get from the bottom left corner to the top right corner if they are required to visit (2,4) ? (c) (3 points) Now suppose that there is a sign at position (4,7) labeled "Definitely Not a Snek Trap" that the Snek has a feeling that they should avoid on the way to the mouse. How many ways can the Snek get from the bottom left corner to the top right corner if they avoid going to (4,7) ? (Note: for this part they do not have to grab the cheese) (d) (3 points) Now suppose that the Snek wants to pick up the cheese at (2,4) while ALSO avoiding the "Definitely Not a Snek Trap" sign at (4,7) on their way to the mouse. How many ways can the Snek get from the bottom left corner to the top right corner if they are required to visit (2,4) and must avoid going to (4,7) ? (15 points) In a certain children's card game, a player has a deck of 40 cards. Each of those 40 cards is either a monster card, a spell card, or a trap card (with each card being exactly one of these). This player's 40 card deck has 19 monster cards, 15 spell cards, and 6 trap cards, that may or may not be distinct from one another (there are potentially identical copies of the same card, or not). Each game begins with drawing a 5 card hand from the deck, called "the opening hand". (a) (3 points) Suppose every card in the player's deck is distinct (so all 40 cards are unique). In how many ways can the player have an opening hand with only spell cards? (b) (3 points) Suppose every card in the player's deck is distinct (so all 40 cards are unique). In how many ways can the player have an opening hand with 2 monster cards, 2 spell cards, and 1 trap card? (c) (3 points) Suppose every card in the player's deck is distinct (so all 40 cards are unique). In how many ways can the player have an opening hand with at least 2 monster cards and at least 1 spell card? (d) (6 points) A first turn kill (FTK) hand is a hand with a specific selection of cards that allow the player to win on the first turn. For a particular FTK hand, a player can win if they have at least 1 of card F ("Friends"), at least 1 of card U ("U \& Me"), and at least 1 of card N ("NE-where \& NE-time") in their opening hand. Suppose the player has 3 identical copies each of card F, card U, and card N (total 9 cards) in their deck, and suppose every other card in their deck is distinct from any other card in the deck (total 34 unique cards). How many opening hands are an FTK hand with the F card, the U card, and the N card