Cammini minimi nell'ipercubo Q4 evitando un vertice

Nell'ipercubo Q4 i vertici sono le 16 stringhe binarie di lunghezza 4 e due stringhe sono adiacenti se differiscono in esattamente un bit. Quanti cammini di lunghezza minima da 0000 a 1111 non passano per il vertice 1000?