login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A335974 Number of tie-less 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 tie-less 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((n-2+14)/2,(n-2-14)/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(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 tie-less 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 tie-less after n-1 scores.

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.

Now, for even n greater than 15, we must subtract from 2*A063886(n-1) the number of games which are tie-less 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.

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 tie-less 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.

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

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

2*A063886(n-1) - 2*A009766((n+12)/2,(n-16)/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 tie-less 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 tie-less.

    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.

Tie-less games: A137684 (American football), A135490 (basketball), A135489 (basketball 1896-1967), 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 1 17:45 EDT 2020. Contains 337444 sequences. (Running on oeis4.)