

A335974


Number of tieless quidditch games with n scoring events.


1



2, 4, 4, 8, 12, 24, 40, 80, 140, 280, 504, 1008, 1848, 3696, 6864, 13726, 25740, 51450, 97240, 194210, 369512, 737124, 1410864, 2810178, 5408312, 10752868, 20801200, 41273500, 80233200, 158851800, 310235040, 612835830, 1202160780, 2369260560, 4667212440
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Quidditch is a sport invented by author J. K. Rowling for her fantasy book series Harry Potter.
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.
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.
A tieless game is one in which the teams never have the same score (except at the beginning, when no team has scored yet).
For n <= 15 and all odd n: a(n) = 2*A063886(n)
For even n greater than 15: a(n) = 2*(A063886(n) + A009766((n2+14)/2,(n214)/2))


REFERENCES

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


LINKS

Cameron Ford, Table of n, a(n) for n = 1..333
Wikipedia, Quidditch


FORMULA

A063886(n1) gives the number of n1 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 n1 scores (all of which are +10 or 10). Therefore, as the last score can be +150 or 150, there are 2*A063886(n1) quidditch games with n scoring events which are tieless after n1 scores.
To be tied after n scores, one team must be 150 points ahead after n1 scores and then the other team must catch the snitch. If n1 is less than 15, this cannot happen. Additionally, if n is odd, then after n1 scores the difference between the scores is an even multiple of 10, so cannot be 150.
Now, for even n greater than 15, we must subtract from 2*A063886(n1) the number of games which are tieless after n1 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 n2 +10s and 10s in the middle such that the net score after n1 scores is +150 and the cumulative number of 10s in the n2 block is never more than the cumulative number of +10s.
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 = n2 and m = k+14. Solving this gives m = (n+12)/2 and k = (n16)/2. Doubling, to count the games where the home team catches the snitch, we have the number of games which are tieless after n1 scoring events but tied after the snitch catch is 2*Catalan((n+12)/2,(n16)/2) hence giving the formula below.
Therefore, the total number of tieless quidditch games with n scoring events is:
2*A063886(n1) if n is odd or n < 16.
2*A063886(n1)  2*A009766((n+12)/2,(n16)/2) otherwise


EXAMPLE

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).


PROG

(Python)
def number_of_tieless_quidditch_games(n):
"""
Takes an integer n, and returns a list containing the number of tieless
quidditch games with 1, 2, 3 .... n scoring events.
Note, the last scoring event is always catching the snitch, which gives
+150 if the home team caught it, or 150 if the away team caught it.
All scoring events prior to the snitch being caught are worth +10 or 10.
"""
dictionary_of_scores = {0:1}
# The keys of this dictionary represent possible scores.
# The values represent the number of ways this score can be reached with
# the game being tieless.
list_to_return = []
for i in range(n):
# We have a dictionary of tieless games with i ten point scoring events.
# Check still tieless after snitch catch
number_of_tieless_games = 0
for score, number_of_ways in dictionary_of_scores.items():
if score != 150: # away team can catch snitch without a tie
number_of_tieless_games += number_of_ways
if score != 150: # home team can catch snitch without a tie
number_of_tieless_games += number_of_ways
list_to_return.append(number_of_tieless_games)
# Update dictionary to have one more ten point scoring event
old_dictionary = dictionary_of_scores
dictionary_of_scores = {}
for scoring_event in (10, 10):
for score, number_of_ways in old_dictionary.items():
new_score = score + scoring_event
if score + scoring_event != 0:
dictionary_of_scores[new_score] =\
dictionary_of_scores.get(new_score, 0) + number_of_ways
return list_to_return


CROSSREFS

Inspired by A137684 and Robin Smyrl.
Tieless games: A137684 (American football), A135490 (basketball), A135489 (basketball 18961967), A334288 (rugby union), this sequence (quidditch).
Cf. A063886.
Sequence in context: A135268 A245619 A131771 * A047073 A308528 A069753
Adjacent sequences: A335971 A335972 A335973 * A335975 A335976 A335977


KEYWORD

nonn


AUTHOR

Cameron Ford, Jul 03 2020


STATUS

approved



