Martin Barlow And S. James Taylor published a number of papers on this topic, for example:
- Fractional dimension of sets in discrete spaces, Journal of Physics A: Mathematical and General, Volume 22 (1989)
- Defining fractal subsets of ${\mathbb Z}^d$, Proc. London Math. Soc. Volume 64 1992
The second is available online.
Both authors did plenty of important work studying the fractal properties of stochastic processes. Taylor proved the seminal result that brownian motion in $\mathbb R^d$ almost surely has dimension 2 when $d>1$. As such, they are primarily interested in definitions of fractal dimension that yield expected results when studying random walks on $\mathbb Z^d$.
The basic idea is to define the lattice cube
$$V_n = \{x\in{\mathbb Z}^d: -n/2<x_i<n/2, \, \forall i\}.$$
The fractal dimension of a set $A\in\mathbb Z^d$ can then be defined by
$$\lim_{n\rightarrow\infty} \frac{\log(\#(A\cap V_n))}{\log(n)}.$$
A $\limsup$ or $\liminf$ can also be used to yield an upper or lower dimension.
This looks quite a lot like box counting dimension and has many of the properties that you might expect. For example, you can estimate $\#(A\cap V_n)$ to within a constant multiple and still get the correct result since
$$\lim_{n\rightarrow\infty} \frac{\log(ca_n)}{\log(b_n)} = \lim_{n\rightarrow\infty} \frac{\log(c)+\log(a_n)}{\log(b_n)} = \lim_{n\rightarrow\infty} \frac{\log(a_n)}{\log(b_n)}.$$
Of course, you can do the same with $n$ which effectively allows us to compute the dimension using any sequence that doesn't go to $\infty$ faster than exponentially. This allows us to easily compute the dimension of your discrete Cantor set. To work in the non-negative integers, let's define
$$V_n = {\mathbb Z}\cap[0,n]$$
and we'll define $S$ be the set of non-negative integers whose base-three expansion contains only the digits 0 and 2. (Note that I've included zero, which I think is a bit more natural, since the integer zero in $S$ corresponds to the left most point of the Cantor set.) Then, it's not hard to show that
$$\#(S\cap V_{3^n}) = 2^n$$
so that
$$\text{dim}(S) = \lim_{n\rightarrow\infty} \frac{\log(\#(S\cap V_{3^n}))}{\log(3^n)} = \frac{\log 2}{\log 3}.$$
Your Pascal/Sierpinski example can be computed in a similar manner. I guess the binomial coefficients mod 2 fit into grid like so:
Note that's $2^4$ rows with $3^4$ ones. In general, we have $2^n$ rows with $3^n$ ones so that the dimension works out to be $\log(3)/\log(2)$.
