How many ways are there to add up integers to $n$ such that atleast one of them equals to 1?

Question

I need to find how many ways there are to add up integers to a given number, $n$, such that at least one of them equal 1. i.e: $|${$(x_1,...,x_k) : 0\leq k \leq n, \sum _{i=1} ^k x_i=n,\exists i:x_i=1$}$|$

thanks!

note: i have been able to find a way for calculate the answer with recursion, but i couldn't find a formula.

my solution: Let $\sigma_n(k)=|${$(x_1,...,x_k):\sum x_i=n,\exists x_i=1$}$| $

and $ \gamma _n(k)=|${$(x_1,...,x_k):\sum x_i=n,\forall x_i\ne1$}$ $.

now we can see that forall k,n: $ \sigma_n(k)+\gamma_n(k)=\binom{n+k-1}{n} $.

Now we will define $ \xi_n(k,\ell)$ to be the number of all the sums of length $k$ that have exactly $\ell$ one's. we can see that $ \sigma_n(k)=\sum_{\ell=1}^k \xi_n(k,\ell) $.

we can notice that we can map all the sums that have $\ell$ ones and are of length $k$ to sums that have 0 ones and are of length $k-\ell$. this mapping sends $ \binom{n}{\ell}$ different sums that have ones to a single sum that doesn't.

so we see that: $\xi_{n}(k,\ell)=\binom{n}{\ell}\gamma_{n}(k-\ell)$.

After playing with the formulas we will get that $ \sigma_{n}(k)=\sum_{\ell=1}^{k}\binom{n}{\ell}\cdot\gamma_{n}(k-\ell)=\sum_{\ell=1}^{k}\binom{n}{\ell}\cdot\left(\binom{n+k-\ell-1}{n}-\sigma_{n}(k-\ell)\right)$ and we can evaluate $\sigma_n(k)$ recusively.

sorry if my english is bad, it's not my first languege :P

Answer 1

Note: the original post says "positive integer" and this solution is dedicated to that question, not the current one.

It is equal to the number of positive solutions minus the number of positive solutions all at least $2$.

The first number is $$n-1\choose k-1 $$

as it is same as placing $k-1$ sticks in the $n-1$ spaces between $n$ balls

For the second number,

note that $a_1+a_2+...+a_k=n$ where each $a_i\geq 2$ is same as $b_1+b_2+...+b_k=n-k$ where each $b_i=a_i-1$ and $b_i\geq 1$.

So the total number is

$${n-1\choose k-1} - {n-k-1\choose k-1}$$

Edited to include zero: If zero is allowed, then we have to add up all the cases for different numbers of zeroes and I believe there is no clean formula.

With $0$ zeroes: ${k \choose 0}({n-1\choose k-1} - {n-k-1\choose k-1})$

With $1$ zeroes: ${k \choose 1}({n-1\choose k-2} - {n-k-1\choose k-2})$

With $3$ zeroes: ${k \choose 2}({n-1\choose k-3} - {n-k-1\choose k-3})$

And so on. The sum will then be

$$\sum_{i=0}^{k-1}{k \choose i}({n-1\choose k-1-i} - {n-k-1\choose k-1-i})$$

Answer 2

The answer is

$$2^{n-1}-F_{n-1}$$

where $F_k$ is the Fibonacci sequence $F_0=0$, $F_1=1$, and $F_{k+1}=F_k+F_{k-1}$. The sequence begins $1,1,3,6,13,27,\ldots$.

To prove this is the correct formula, note that without the restriction of having at least one $1$, the answer is simply $2^{n-1}$: That is, to obtain a decomposition of $n$, start with $(1+1+\cdots+1+1)$, where you have $n-1$ addition signs, and then either place or don't place a pair of outward facing parentheses around each $+$ sign, i.e, turn some $+$'s into $)+($'s, thereby grouping batches of $1$'s. Thus we need to count (and subtract from $2^{n-1}$) the number of decompositions of $n$ that don't have any $1$'s.

Now if $n=x_1+x+x_2+\cdots+x_k$ has no $1$'s and $x_k\ge3$, then $n-1=x_1+x_2+\cdots+(x_k-1)$ has no $1$'s either, while if $x_k=2$, then $n-2=x_1+x_2+\cdots+x_{k-1}$ has no $1$'s. Consequently, the number of decompositions of $n$ without any $1$'s is the sum of the number of decompositions of $n-1$ and $n-2$ without any $1$'s, i.e., satisfies the Fibonacci-like recursion $c_n=c_{n-1}+c_{n-2}$. And since $c_1=0$ and $c_2=1$ are easy to see, we get exactly the Fibonacci numbers $F_{n-1}$.

Remark: I found the general formula at first by computing the first six cases explicitly, e.g., $3$ has $3$ compositions with at least one $1$:

$$1+1+1\quad1+2\quad2+1$$

while $6$ has $27$:

$$ \underbrace{1+1+1+1+1+1}_1\quad\underbrace{1+1+1+1+2}_5\quad\underbrace{1+1+2+2}_6\quad\underbrace{1+2+3}_6\\\underbrace{1+1+1+3}_4\quad\underbrace{1+1+4}_3\quad\underbrace{1+5}_2\qquad1+5+6+6+4+3+2=27$$

(The numbers under the brackets count the distinct arrangements of the numbers above the brackets, for example the first $6$ is ${4\choose2}$ while the second $6$ is $3!$.) Consulting the OEIS gave the answer at A099036. It's possible I could have found the general formula without consulting the OEIS if I had thought to subtract the first six terms from the appropriate powers of $2$ corresponding to the relatively simple "unrestricted" decomposition answer, $1,2,4,8,16,32,\ldots$. Doing so leaves $0,1,1,2,3,5,\ldots$, which an experienced eye easily spots as the Fibonacci sequence. My habit, however, is to go straight to the OEIS as soon as I have a sequence in hand.