The Christmas Stocking Theorem – A Festive Combinatorics Identity

Το Θεώρημα της Χριστουγεννιάτικης Κάλτσας

Το Θεώρημα της Χριστουγεννιάτικης Κάλτσας είναι μια κομψή ταυτότητα της συνδυαστικής, γνωστή και από προβλήματα επιπέδου International Mathematical Olympiad (IMO).

Δηλώνει ότι για κάθε μη αρνητικό ακέραιο n και κάθε θετικό ακέραιο k, ισχύει:

\[\sum_{i=0}^{k-1} \binom{n+i}{i} = \binom{n+k}{k-1}\]

Η ονομασία του θεωρήματος προέρχεται από μια διαισθητική συνδυαστική ερμηνεία, η οποία θυμίζει το γέμισμα μιας χριστουγεννιάτικης κάλτσας με δώρα.

Το θεώρημα εμφανίστηκε ως IMO Idea #150 με αφορμή την IMO 2016 στο Χονγκ Κονγκ.

The Christmas Stocking Theorem

The Christmas Stocking Theorem is an elegant identity from combinatorics, well known from problems at the level of the International Mathematical Olympiad (IMO).

It states that for any non-negative integer n and any positive integer k, the following holds:

∑_i=0^k−1 ( n + i
i ) = ( k + n
k − 1 )

The name of the theorem comes from a combinatorial interpretation reminiscent of filling a Christmas stocking with gifts.

The identity appeared as IMO Idea #150 in connection with IMO 2016, held in Hong Kong.