A335974 - OEIS

%I #34 Jan 08 2021 20:52:52

%S 2,4,4,8,12,24,40,80,140,280,504,1008,1848,3696,6864,13726,25740,

%T 51450,97240,194210,369512,737124,1410864,2810178,5408312,10752868,

%U 20801200,41273500,80233200,158851800,310235040,612835830,1202160780,2369260560,4667212440

%N Number of tieless quidditch games with n scoring events.

%C Quidditch is a sport invented by author J. K. Rowling for her fantasy book series Harry Potter.

%C In quidditch, the match ends when the snitch is caught. The team which caught it is awarded 150 points. All other scoring events are worth 10 points, and occur when the quaffle is thrown through one of the hoops.

%C A game is, therefore, a list of +10s and -10s, with a final entry of either +150 or -150. Negative points are for the away team, positive points are for the home team.

%C A tieless game is one in which the teams never have the same score (except at the beginning, when no team has scored yet).

%C For n <= 15 and all odd n: a(n) = 2*A063886(n)

%C For even n greater than 15: a(n) = 2*(A063886(n) + A009766((n-2+14)/2,(n-2-14)/2))

%D J. K. Rowling, Harry Potter and the Philosopher's Stone, Chapter 10, Bloomsbury, 1997.

%H Cameron Ford, <a href="/A335974/b335974.txt">Table of n, a(n) for n = 1..333</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Quidditch">Quidditch</a>

%F A063886(n-1) gives the number of n-1 step walks on a line starting from the origin but not returning to it. This is equivalent to the number of quidditch games with n scoring events which are tieless after the first n-1 scores (all of which are +10 or -10). Therefore, as the last score can be +150 or -150, there are 2*A063886(n-1) quidditch games with n scoring events which are tieless after n-1 scores.

%F To be tied after n scores, one team must be 150 points ahead after n-1 scores and then the other team must catch the snitch. If n-1 is less than 15, this cannot happen. Additionally, if n is odd, then after n-1 scores the difference between the scores is an even multiple of 10, so cannot be 150.

%F Now, for even n greater than 15, we must subtract from 2*A063886(n-1) the number of games which are tieless after n-1 scores but tied after n scores. For this to be the case, supposing the away team catches the snitch, we must have the game starting with +10, ending with -150 and with a block of n-2 +10s and -10s in the middle such that the net score after n-1 scores is +150 and the cumulative number of -10s in the n-2 block is never more than the cumulative number of +10s.

%F Catalan's triangles, Catalan(m,k) gives the number of sequences of m +10s and k -10s such that the cumulative number of -10s is never greater than the cumulative number of +10s. We require m+k = n-2 and m = k+14. Solving this gives m = (n+12)/2 and k = (n-16)/2. Doubling, to count the games where the home team catches the snitch, we have the number of games which are tieless after n-1 scoring events but tied after the snitch catch is 2*Catalan((n+12)/2,(n-16)/2) hence giving the formula below.

%F Therefore, the total number of tieless quidditch games with n scoring events is:

%F 2*A063886(n-1) if n is odd or n < 16.

%F 2*A063886(n-1) - 2*A009766((n+12)/2,(n-16)/2) otherwise

%e a(3) = 4 because to avoid a tie after two scoring events, the same team must score the first two goals, i.e., the game starts (+10,+10) or (-10,-10). Then there are two options for who catches the snitch. So the tieless games with three scoring events are (-10,-10,-150), (-10,-10,+150), (+10,+10,-150) and (+10,+10,+150).

%o (Python)

%o def number_of_tieless_quidditch_games(n):

%o     """

%o     Takes an integer n, and returns a list containing the number of tieless

%o     quidditch games with 1, 2, 3 .... n scoring events.

%o     Note, the last scoring event is always catching the snitch, which gives

%o     +150 if the home team caught it, or -150 if the away team caught it.

%o     All scoring events prior to the snitch being caught are worth +10 or -10.

%o     """

%o     dictionary_of_scores = {0:1}

%o     # The keys of this dictionary represent possible scores.

%o     # The values represent the number of ways this score can be reached with

%o     # the game being tieless.

%o     list_to_return = []

%o     for i in range(n):

%o         # We have a dictionary of tieless games with i ten point scoring events.

%o         # Check still tieless after snitch catch

%o         number_of_tieless_games = 0

%o         for score, number_of_ways in dictionary_of_scores.items():

%o             if score != 150: # away team can catch snitch without a tie

%o                 number_of_tieless_games += number_of_ways

%o             if score != -150: # home team can catch snitch without a tie

%o                 number_of_tieless_games += number_of_ways

%o         list_to_return.append(number_of_tieless_games)

%o         # Update dictionary to have one more ten point scoring event

%o         old_dictionary = dictionary_of_scores

%o         dictionary_of_scores = {}

%o         for scoring_event in (-10, 10):

%o             for score, number_of_ways in old_dictionary.items():

%o                 new_score = score + scoring_event

%o                 if score + scoring_event != 0:

%o                     dictionary_of_scores[new_score] =\

%o                     dictionary_of_scores.get(new_score,0) + number_of_ways

%o     return list_to_return

%Y Inspired by A137684 and Robin Smyrl.

%Y Tieless games: A137684 (American football), A135490 (basketball), A135489 (basketball 1896-1967), A334288 (rugby union), this sequence (quidditch).

%Y Cf. A063886.

%K nonn

%O 1,1

%A _Cameron Ford_, Jul 03 2020