Number 3 can be expressed by using 1 and 2 in 3 distinct ways I,e, 1+1+1, 1+2, 2+1; number 4 in 5 ways: 1+1+1+1 , 2+1+1, 1+2+1, 1+1+2, and 2+2.
Using the digits 1 and 2 as summands, in how many ways may be 26 expressed?
Bonus: Generalize the process for number N.
There can be only twos or no twos or anything in between so we just add together the ways of arranging each possible number of twos and the number of ones to add up to n.
For 26, there would be 1 way of arranging 13 twos, 25 ways of arranging 1 two and 24 ones, etc. These add up to 196,418 ways.
Broken down by numbers of twos and ones:
twos ones ways
0 26 1
1 24 25
2 22 276
3 20 1771
4 18 7315
5 16 20349
6 14 38760
7 12 50388
8 10 43758
9 8 24310
10 6 8008
11 4 1365
12 2 91
13 0 1
The process is done for up to 50:
for n=1:50
ways=0;
for numTwos=0:floor(n/2)
numOnes=n-2*numTwos;
ways=ways+nchoosek(numTwos+numOnes,numTwos);
end
fprintf('%4d %13d\n',n,ways)
end
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
20 10946
21 17711
22 28657
23 46368
24 75025
25 121393
26 196418
27 317811
28 514229
29 832040
30 1346269
31 2178309
32 3524578
33 5702887
34 9227465
35 14930352
36 24157817
37 39088169
38 63245986
39 102334155
40 165580141
41 267914296
42 433494437
43 701408733
44 1134903170
45 1836311903
46 2971215073
47 4807526976
48 7778742049
49 12586269025
50 20365011074
and it's apparent that each is F(n), the Fibonacci numbers.
|
|
Posted by Charlie
on 2023-05-04 15:36:03 |
computer solution
