# Combinatoric in Accounting

Prove:
$\displaystyle\sum_{n=2}^{n}{_n}C_r = 2^n-1-n$
$\displaystyle\sum_{n=2}^{n}{_n}C_r 2^r= 3^n-1-2n$
Note:
${_4}C_2=\frac {4.3}{2!}$
Proof:
1.
$\displaystyle\sum_{n=2}^{n}{_n}C_r$ =(1+1)ⁿ -1- $\displaystyle {_n}C_1 =2^n-1-n$
2.
$\displaystyle\sum_{n=2}^{n}{_n}C_r 2^{r}$=(1+2)ⁿ -1 – $\displaystyle {_n}C_1 .2^{1}= 3^n-1-2n$

An accounting transaction = Debit p accounts + Credit q accounts (p, q ≥ 1)

In a company with total n accounts,
Prove: there are $3^n -2^{n+1} + 2$ transactions.

Proof:
Let the Set of all accounts T = {a1, a2, …, an}
aj = account with value ‘+’ (credit), or ‘-‘ (debit), or 0 (nil)
1. Trivial transaction: To= {0, 0,…..0} = 1 way
2. Choose r accounts from n = $\displaystyle {_n}C_r$
3. Slot ‘+’ or ‘-‘ in these r accounts = $2^r$ways
exclude 2 impossible all ‘+’, ‘-‘ transactions = $2^r- 2$ ways
4.
Let T1 = $\displaystyle\sum_{n=2}^{n}{_n}C_r .(2^r-2)$
Total transaction = To + T1
= $\displaystyle 1+ \sum_{n=2}^{n}{_n}C_r .(2^r-2)$
{Apply previous results}
= $\displaystyle 1+ \sum_{n=2}^{n}{_n}C_r .2^r -2.\sum_{n=2}^{n}{_n}C_r$
= $1+3^n-1-2n -2(2^n-1-n)$
= $3^n -2^{n+1} + 2$  [QED]