Hockey Stick Identity (Christmas Stocking Identity) – A Powerful Combinatorial Identity Explained

Ταυτότητα του Ραβδιού του Χόκεϋ

Η ταυτότητα του ραβδιού του χόκεϋ (γνωστή και ως Hockey-stick identity, «χριστουγεννιάτικη κάλτσα», «boomerang» ή θεώρημα του Chu) είναι μία βασική συνδυαστική ταυτότητα που μετατρέπει ένα άθροισμα διωνυμικών συντελεστών σε έναν μοναδικό συντελεστή.

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

Ορισμός

Για κάθε ακέραιους αριθμούς n, r με n ≥ r ≥ 0 ισχύει:

∑_i=rⁿ C(i,r) = C(n+1, r+1)

όπου C(n,k) = (n choose k) = n! / (k!(n−k)!) είναι ο διωνυμικός συντελεστής.

Παράδειγμα

Στη σειρά n = 6, r = 2 του τριγώνου του Pascal:

C(2,2) + C(3,2) + C(4,2) + C(5,2) + C(6,2)
= 1 + 3 + 6 + 10 + 15 = 35 = C(7,3)

Οι αριθμοί 1 – 3 – 6 – 10 – 15 – 35 σχηματίζουν το χαρακτηριστικό «ραβδί».

Αλγεβρική Απόδειξη (Τηλεσκοπική)

Χρησιμοποιούμε την ταυτότητα του Pascal:

C(t,k) = C(t+1,k+1) − C(t,k+1)

Αθροίζοντας από t = r έως n:

∑ C(t,r) = C(n+1,r+1) − C(r,r+1) = C(n+1,r+1)

Συνδυαστική Απόδειξη (Διπλό Μέτρημα)

Μετράμε τον αριθμό των υποσυνόλων με r+1 στοιχεία ενός συνόλου n+1 στοιχείων.

Αν το μεγαλύτερο στοιχείο ενός υποσυνόλου είναι το i+1, τότε τα υπόλοιπα r στοιχεία επιλέγονται από τα πρώτα i στοιχεία με C(i,r) τρόπους.

Το άθροισμα για i = r, … , n οδηγεί ακριβώς στην ταυτότητα.

Εφαρμογές

• Γρήγορος υπολογισμός αθροισμάτων διωνυμικών συντελεστών
• Προβλήματα κατανομών τύπου stars & bars
• Δυναμικός προγραμματισμός και αλγόριθμοι Pascal

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

Hockey Stick Identity

The Hockey Stick Identity is a fundamental combinatorial identity that transforms a sum of binomial coefficients into a single coefficient.

Its name comes from the characteristic shape formed when the identity is visualized in Pascal’s Triangle, resembling a hockey stick.

Definition

For integers n ≥ r ≥ 0:

∑_i=rⁿ C(i,r) = C(n+1, r+1)

where C(n,k) = n! / (k!(n−k)!).

Example

C(2,2) + C(3,2) + C(4,2) + C(5,2) + C(6,2)
= 35 = C(7,3)

Algebraic Proof

C(t,k) = C(t+1,k+1) − C(t,k+1)

Summing from t = r to n yields:

C(n+1,r+1