The following property is given for the cross-polytope in various places (e.g. in the Wikipedia article on the cross-polytope):
The number of k-dimensional components (vertices, edges, faces, etc) of the n-dimensional cross-polytope is:
$2^{k+1}{n \choose {k+1}}$
How can this be proved? This is homework, so I'd prefer hints to actual solutions.
What I have so far is: it's pretty obvious to me that the number of vertices is two times the dimension, since we start out with 2 points (-1 and 1) for one dimension, and add two more on the orthogonal dimension for each step up in dimensions. I can also see how there are 2^n different d-dimensional simplices contained in the cross-polytope: for each dimension (of which there are n), just choose either + or - its elementary vector and take the convex hull.
Finding intermediate components doesn't seem to be equivalent to finding all subset polytopes, though. For instance, the square (2-orthoplex) has vertices (-1 0), (1 0), (0 -1), (0 1). There are four edges (going along the edges). convex((-1 0) (1 0)) also fits inside the square, yet there's no edge between (-1 0) and (1 0).
The $2^{k+1}$ suggests that you're answering $k + 1$ yes/no questions (or perhaps $+$/$-$ questions?).
The ${n \choose {k+1}}$ has a natural interpretation, but as you've rightly pointed out, it's not ${2n \choose k + 1}$. Why should we only be allowed to choose from half of the vertices available?
To answer that question, let's look more closely at your two-dimensional example. For the square, I'd like to call the vertices $\pm e_i$ for $i = 1, 2$. You noted that $e_1$ and $-e_1$ aren't endpoints of a single edge; geometrically, the line connecting these points goes through the origin, and we definitely don't want that for a face. Can we turn this into a criterion for determining which subsets are the vertex sets of faces?