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: MEDIUM_HARD
Tags: Number theory

Combinatorics

Ad-hoc

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):
	return factorial(n + k - 1) / factorial(k) / factorial(n - 1)

def num_increasing(x):
	return num_multicombinations(x + 1, 8)

def num_decreasing(x):
	return num_multicombinations(x + 1, 9) - 1

def num_non_bouncy(x):
	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


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]