Let's define `increasing` numbers as the numbers whose digits, read from left to right, are never less than the previous ones: 234559 is an example of increasing number.

Conversely, `decreasing` numbers have all the digits read from left to right so that no digits is bigger than the previous one: 97732 is an example of decreasing number.

You do not need to be the next Gauss to figure that all numbers with 1 or 2 digits are either increasing or decreasing: 00, 01, 02, ..., 98, 99 are all belonging to one of this categories (if not both, like 22 or 55): 101 is indeed the first number which does NOT fall into either of the categories. Same goes for all the numbers up to 109, while 110 is again a decreasing number.

Now your task is rather easy to declare (a bit less to perform): you have to build a function to return the total occurrences of all the increasing or decreasing numbers *below* 10 raised to the xth power (x will always be >= 0).

To give you a starting point, there are a grand total of increasing and decreasing numbers as shown in the table:

|Total  | Below
|---------------
|1      | 1
|10     | 10
|100    | 100
|475    | 1000
|1675   | 10000
|4954   | 100000
|12952  | 1000000

This means that your function will have to behave like this:
```python
total_inc_dec(0)==1
total_inc_dec(1)==10
total_inc_dec(2)==100
total_inc_dec(3)==475
total_inc_dec(4)==1675
total_inc_dec(5)==4954
total_inc_dec(6)==12952
```

**Tips:** efficiency and trying to figure out how it works are essential: with a brute force approach, some tests with larger numbers may take more than the total computing power currently on Earth to be finished in the short allotted time.

To make it even clearer, the increasing or decreasing numbers between in the range 101-200 are: [110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, 123, 124, 125, 126, 127, 128, 129, 133, 134, 135, 136, 137, 138, 139, 144, 145, 146, 147, 148, 149, 155, 156, 157, 158, 159, 166, 167, 168, 169, 177, 178, 179, 188, 189, 199, 200], that is 47 of them. In the following range, 201-300, there are 41 of them and so on, getting rarer and rarer.

**Trivia:** just for the sake of your own curiosity, a number which is neither decreasing of increasing is called a `bouncy` number, like, say, 3848 or 37294; also, usually 0 is not considered being increasing, decreasing or bouncy, but it will be for the purpose of this kata

Difficulty: interview

Starter code:

def total_inc_dec(x):
	

Solutions:
from math import factorial as fac

def xCy(x, y):
    return fac(x) // fac(y) // fac(x - y)
    
def total_inc_dec(x):
    return 1+sum([xCy(8+i,i) + xCy(9+i,i) - 10 for i in range(1,x+1)])


inc = {}
dec = {}


def total_inc(n, a):
    if n not in inc:
        inc[n] = {}
    if a not in inc[n]:
        inc[n][a] = total_inc(n, a+1) + total_inc(n-1, a) if a < 9 and n > 0 else 1
    return inc[n][a]


def total_dec(n, a):
    if n not in dec:
        dec[n] = {}
    if a not in dec[n]:
        dec[n][a] = total_dec(n, a-1) + total_dec(n-1, a)if a > 0 and n > 0 else 1
    return dec[n][a]


def total_inc_dec(n):
    return total_inc(n, 0) + sum([total_dec(m, 9) for m in range(n+1)]) - (10*n + 1)

from math import factorial

def total_inc_dec(x):
    return comb(x + 10, 10) + comb(x + 9, 9) - 1 - (10 * x)  
    
def comb(n, k):
    f = factorial
    return f(n) // f(k) // f(n-k)

def total_inc_dec(x):
    n = 1
    for i in range(1,10):
        n = n*(x+i)//i
    return n*(20+x)//10 - 10*x - 1

from math import factorial

def num_multicombinations(n, k):
    """
    Calculates number of muticombinations of size k from a set of
    size n.
    """
    return factorial(n+k-1)/factorial(k)/factorial(n-1)


def num_increasing(x):
    """
    Returns the number of increasing numbers with x digits
    We need to put 8 'increases' into x+1 positions.
    e.g. for 2 digit numbers: 
      ||||d|||d| = 58. four increases before first digit: 1+4 = 5
                       three increases before second digit: 5+3 = 8
    This is equivalent to the number of multicombinations of size 8
    from a set of size x + 1.
    """
    return num_multicombinations(x+1, 8)

def num_decreasing(x):
    """
    Returns the number of decreasing numbers with x digits
    Similar to num_increasing, but we now have 9 'decreases' to fit
    into x+1 positions. We need to subtract 1 because 000...0000 is
    not an x-digit number.
    """
    return num_multicombinations(x+1, 9) - 1
    
def num_non_bouncy(x):
    """
    Returns the number of non-bouncy numbers with x digits
    Add the number of x-digit increasing and decreasing numbers, then
    subtract 9 so that we don't count the 9 numbers which are both increasing
    and decreasing (one repeated digit e.g. 11111, 22222, ...).
     """
    return num_increasing(x) + num_decreasing(x) - 9


def total_inc_dec(x):
    if x==0: return 1
    return sum(num_non_bouncy(a) for a in range(1,x+1)) + 1
        
    #count = 0
    #for i in xrange(10**x):
    #    s = str(i)
    #    if len(s)==1:
    #        count += 1
    #        continue
    #    elif all(map(lambda x: x[0]==x[1], zip(s, s[1:]))):
    #        count += 1
    #        continue
    #    elif all(map(lambda x: x[0]>=x[1], zip(s, s[1:]))):
    #        if s[-1] == '0':
    #            count += 1
    #        else:
    #            count += 2
    #return count
        
    #your code here


def f(n, s=0):
    c, li = 10+s, list(range(1+s,10+s))
    for i in range(n-1):
        c += sum(li)
        li = [sum(li[:k + 1]) + s for k in range(len(li))]
    return c - s
total_inc_dec=lambda n:(f(n)+f(n,1)-(10+9*(n-1))) if n else 1

def total_inc_dec(x):   
    if x < 3:   return 1 if x < 1 else 10**x
    a = list(reversed(range(1,10)))
    b = list(reversed(range(1,11)))
    ttl = 10*(2 - x)
    for _ in range(x - 1):
        p, q = a[0], b[0] = sum(a), sum(b)
        for i in range(1,9):
            a[i], b[i] = sum(a[i:]), sum(b[i:])
        ttl += p + q
    return ttl

def total_inc_dec(x):
    def combination(n, m):
        if m == 0:
            return 1
        else:
            a = b = 1
            for i in range(0, m):
                a *= n - i
                b *= i + 1
            return int(a / b)

    def coefficientList(x):
        if x == 1:
            return [2]
        elif x == 2:
            return [2, 5]
        else:
            List1 = coefficientList(x - 1)
            List = [2] * x
            for i in range(0, x - 2):
                List[i + 1] = List1[i] + \
                    List1[i + 1]
            List[-1] = List1[-1] + x + 1
            return List


    if x == 0:
        return 1
    else:
        List = coefficientList(x)
        a = 0
        for i in range(0, len(List)):
            a += List[i] * combination(9, x - i)
        a = 1 + a - x * combination(9, 1)
        return a 

total_inc_dec=lambda n:[1, 10, 100, 475, 1675, 4954, 12952, 30817, 67987, 140907, 277033, 520565, 940455, 1641355, 2778305, 4576113, 7354549, 11560664, 17809754, 26936719, 40059819, 58659104, 84672094, 120609609, 169694999, 236030401, 324794055, 442473145, 597137095, 798756745, 1059575359, 1394537977, 1821786217, 2363226262, 3045178432, 3899117443, 4962513195, 6279782710, 7903364660, 9894928785, 12326733403, 15283145159, 18862336149, 23178174589, 28362326279, 34566585239, 41965453069, 50758987809, 61175944349, 73477229764, 87959698326, 104960312375, 124860696715, 148092115740, 175140904090, 206554383289, 242947298527, 285008811517, 333510087187, 389312513857, 453376598503, 526771580725, 610685811115, 706437941865, 815488979665, 939455253218, 1080122350044, 1239460079659, 1419638522699, 1623045228114, 1852303623184, 2110292703809, 2400168075299, 2725384416739, 3089719444929, 3497299456901, 3952626533095, 4460607486435, 5026584645785, 5656368565585, 6356272756869, 7133150538352, 7994434109842, 8948175953887, 10003092675307, 11168611392088, 12454918795030, 13873012997545, 15434758301095, 17152943005945, 19041340401183, 21114773072329, 23389180669319, 25881691282209, 28610696576599, 31595930845529, 34858554139449, 38421239640814, 42308265454904, 46545610993619, 51161058134251, 56184297340590, 61647038939180, 67583129749105, 74028675269355, 81022167633599, 88604619548077, 96819704434317, 105713903004487, 115336656503407, 125740526857573, 136981363977985, 149118480470125, 162214834011100, 176337217660750, 191556458380423, 207947624040139, 225590239202004, 244568509974994, 264971558243609, 286893665580399, 310434527159989, 335699515999979, 362799957861969, 391853417153959, 422983994183501, 456322634119235, 492007448026825, 530184046353825, 571005885246650, 614634626091604, 661240508680827, 711002738413067, 764109887948362, 820760313745032, 881162587916833, 945535945857715, 1014110750091355, 1087128970812505, 1164844683597205, 1247524584769063, 1335448524919099, 1428910061087089, 1528217028122929, 1633692129757269, 1745673549921544, 1864515584868554, 1990589296655919, 2124283188566059, 2266003903047824, 2416176942776526, 2575247415440905, 2743680802877495, 2921963755184945, 3110604910463095, 3310135740834009, 3521111425414727, 3744111750924217, 3979742040619887, 4228634112272057, 4491447265897993, 4768869301990470, 5061617570989360, 5370440054758435, 5696116480843435, 6039459470301478, 6401315719906084, 6782567219546449, 7184132505654139, 7606967951505079, 8052069095259589, 8520472006618269, 9013254692986759, 9531538546057799, 10076489829734589, 10649321210335201, 11251293330033725, 11883716424509940, 12547951985795590, 13245414471321815, 13977573060188939, 14745953457696652, 15552139749189642, 16397776304290937, 17284569732612607, 18214290892051053, 19188776950791875, 20209933504167265, 21279736747527015, 22400235706302565, 23573554524462043, 24801894812572969, 26087538056708209, 27432848089449874, 28840273624265164, 30312350854547659, 31851706118637259, 33461058632151874, 35143223288984064, 36901113532336129, 38737744297187651][n]