Ytukyg

Following the solution to my previous post in:
Counting unique element output from a product of combination

where the number of unique string-variants generated from a given string is:

$$
1+sum_{k=1}^r 3^kbinom{n}{k}
$$

How to solve the summation so that I could use this formula for large $r$?

My attempt:
I try to solve it using a general formula:
$$
S{n} = frac{a_1(1-r^n)}{1-r}
$$
for $a = 3$ and the common factor $r = 3$. But it turns out that is wrong since the formula above did not has anything to do with the binomial coefficient. Anyone can help?

This sum does not have an elementary representation. Let $f(r,n)$ be your sum. By a CAS
begin{align*}
f(r,n) &= 1 + sum_{k=1}^r 3^k binom{n}{k} \
&= 4^n - 3^{r+1}binom{n}{r+1}{}_2F_1(1,r-n+1;r+2;-3)
end{align*}

where ${}_2F_1$ is the Gaussian hypergeometric function. Even assuming $r$ and $n$ integers with $0 < r < n$, there are no simplifications to elementary functions.

For $1 leq r < n$, use the sum. This is easy as long as $n$ is not large. You give no hints about the size of $n$ in your question. Your prior post claims you are only interested in $1 leq r leq 4$, so this sum is nearly immediate.

For $r geq n$, $f(r,n) = 4^n$. This follows from your sum since $binom{n}{n+1} = binom{n}{n+2} = cdots = 0$, so the sum cuts itself off after $r = n$, and a standard identity (first one at that link, taking $x = 3$ and realizing the $k = 0$ term is the "$1+$" in $f$). In the context of your previous post (not having read it in detail) -- once you've decided to replace every character in your string, then you have any $n$-length string you want from your 4 character alphabet, giving $4^n$ possibilities.

Digging through OP's referenced Question, he most likely intends $1 leq r leq 4$ and $r leq n$. These constraints appear nowhere in the current Question. With those constraints ...
begin{align*}
f(1,n) &= 1 + 3n text{,} \
f(2,n) &= 1 + 3n + frac{9}{2}n(n-1) text{,} \
f(3,n) &= frac{1}{2}(9n^2 -3n+2) + frac{9}{2}n(n-1)(n-2) text{, and} \
f(4,n) &= frac{1}{2}(9n^3 - 18 n^2 + 15 n + 2) + frac{27}{8}n(n-1)(n-2)(n-3) text{.}
end{align*}

For example, $f(4,10,000) = 33,734,252,812,372,501$. I note this because representing such quantities in a programming language as precise integers (instead of imprecise floating point approximations) can require some effort. Letting $r$ and $n$ be "large" necessitates this effort. If you intend to generate these numbers in a programming language, it would help to know which language you are targetting.

Just testing for timing, I get the complete set of results for $n = 10,000$ in about 180 ms using this code:

import itertools

import time



class sumterm:

    """Iterator to produce terms of a specific sum counting replaced strings."""

    def __init__(self, nInit):

        # Rememember: Iterators start in a "prior to the first element" state 

        # and are expected to yield the first element on the first call to 

        # __next__().

        self.n = nInit

        self.k = 0

        self.term = 1  # 3^k binom(n,k) = 1 binom(n,0) = 1, when k = 0



    def __iter__(self):

        try: self.n

        except NameError: raise ValueError("sumterm objects must be initialized before iterating.")



        return self



    def __next__(self):

        if self.k < self.n:

            # 3^(k+1) binom(n,k+1) = 3^k binom(n,k) * 3(n-k)/(k+1)

            # Integer division ( // ) is safe because divisibility is ensured.

            self.term = self.term * 3*(self.n - self.k) // (self.k+1)

            self.k += 1

            return self.term

        else:

            raise StopIteration



n = 10000

tBefore = time.time()

terms = list(iter(sumterm(n)))

partialSums = [1+x for x in itertools.accumulate(terms) ]

tAfter = time.time()



print("For n = ", n, ", k = 1 .. 11: ",  partialSums[:11])

print("Took",  tAfter - tBefore,  " seconds.")

Don't bother trying to print the last few terms. $4^{10,000}$ is too large to usefully look at.

Note that partialSums[k-1] is $f(k,n)$ for $k leq n$.

begin{align*}
f(1,n) &= 1 + sum_{k=1}^1 3^k binom{n}{k} \
&= 1 + 3^1 binom{n}{1} \
&= 1 + 3 n text{, } \
f(2,n) &= 1 + sum_{k=1}^2 3^k binom{n}{k} \
&= 1 + 3^1 binom{n}{1} + 3^2 binom{n}{2} \
&= 1 + 3 n + 9frac{n(n-1)}{2} text{, } \
f(3,n) &= 1 + sum_{k=1}^3 3^k binom{n}{k} \
&= 1 + 3^1 binom{n}{1} + 3^2 binom{n}{2} + 3^3 binom{n}{3} \
&= 1 + 3 n + 9frac{n(n-1)}{2} + 27frac{n(n-1)(n-2)}{6} \
&= frac{1}{2}(2 + 6n + 9n(n-1)) + frac{9}{2}n(n-1)(n-2) \
&= frac{1}{2}(9n^2 - 3 n + 2) + frac{9}{2}n(n-1)(n-2) text{,}
end{align*}
and
begin{align*}
f(4,n) &= 1 + sum_{k=1}^4 3^k binom{n}{k} \
&= 1 + 3^1 binom{n}{1} + 3^2 binom{n}{2} + 3^3 binom{n}{3} + 3^4 binom{n}{4} \
&= 1 + 3 n + 9frac{n(n-1)}{2} + 27frac{n(n-1)(n-2)}{6} + 81frac{n(n-1)(n-2)(n-3)}{24} \
&= frac{1}{2}(2 + 6n + 9n(n-1) + 9n(n-1)(n-2)) + frac{27}{8}n(n-1)(n-2)(n-3) \
&= frac{1}{2}(9 n^3 - 18 n^2 + 15 n + 2) + frac{27}{8}n(n-1)(n-2)(n-3) text{.} \
end{align*}

In case you are interested in asymptotics:

$$begin{align}
s(n,r)&=sum_{k=1}^r 3^kbinom{n}{k}\
&=2^nsum_{k=1}^r 3^kfrac{binom{n}{k}}{2^n}\
&approx frac{2^n}{sqrt{pi n /2}} int_0^r 3^x expleft( -frac{2}{n}(x-n/2)^2 right)
dx \
end{align}$$

If $r > 0.78 n$ we can apply Laplace's method and get the first order approximation:

$$ frac{log (s(n,r))}{n} to log(2) + frac{log^2(3)+ 4 log 3}{8}approx 1.393$$

For smaller $r$ , a similar approximation can be obtained (tell me if you are interested) but it involves both $(n,r)$ variables.