In how many ways can n be written as the sum of positive integers with no consecutive 1's?
For example a(4)=5 because we have (4)=(1+3)=(2+2)=(3+1)=(1+2+1)
Prove the sequence defined by a(n).
A given number, n, can be the total that includes up to ceil(n/3) 1's.
So we can start with the ways of making a total of n - ceil(n/3) without any 1's, through a total of n without any 1's, and for each of those along the way, multiply by the ways of sprinkling enough non-consecutive 1's to bring the total to n.
Consider that enough (say k) terms must be used so that the total + k + 1 is at least n.
Here's a program written to find the number of ways of totaling n under the given rules. For purposes of the demonstration, limited to n=10.
clearvars,clc
global n sz way ways remain most1s
for n=10
most1s=ceil(n/3);
ways=0;
for sz=n:-1:n-most1s
way=[];
remain=sz;
addon;
end
way=[];
disp(ways)
disp(' ')
end
function addon
global n sz way ways remain most1s
for chunk=remain:-1:2
if ~isempty(way)
if chunk>way(end)
continue
end
end
if chunk<=remain
way=[way chunk];
remain=remain-chunk;
if remain==0
s=length(way);
if s+sum(way)+1>=n
disp(way)
w1=size(unique(perms(way),'rows'),1);
ones=n-sum(way);
places=s+1;
w2=nchoosek(places,ones);
disp([w1 w2 w1*w2])
ways=ways+w1*w2;
disp(' ');
end
else
addon;
end
remain=remain+chunk;
way=way(1:end-1);
end
end
end
The output for 10 is given below. The first row lists the non-1 addends in descending order and the second row lists first the number of ways of arranging these non-1 integers; second, the number of ways of placing the 1's to complete the value of n; and third, the number of ways that this accounts for.
Note: the first version did not count the case of the number itself as a possible "total", so the count at the bottom is one less than what's wanted.
For example
4 3 2
6 4 24
shows 4+3+2 = 9, needing one 1 to make 10. The three non-1 integers can be arranged 6 ways. For each of those ways there are four places to put the 1. The ways contribute 24 to the overall number of ways.
Another example
2 2 2 2
1 10 10
There's only one way of arrainging the four 2's, but two 1's must be placed in the five possible positions, so the number of ways is multiplied by C(5,2)=10.
and one more
4 4 2
3 1 3
There are three ways of arranging 4+4+2 but no 1's are needed, so the 3 ways are the only ways.
The table:
8 2
2 1 2
7 3
2 1 2
6 4
2 1 2
6 2 2
3 1 3
5 5
1 1 1
5 3 2
6 1 6
4 4 2
3 1 3
4 3 3
3 1 3
4 2 2 2
4 1 4
3 3 2 2
6 1 6
2 2 2 2 2
1 1 1
9
1 2 2
7 2
2 3 6
6 3
2 3 6
5 4
2 3 6
5 2 2
3 4 12
4 3 2
6 4 24
3 3 3
1 4 4
3 2 2 2
4 5 20
8
1 1 1
6 2
2 3 6
5 3
2 3 6
4 4
1 3 3
4 2 2
3 6 18
3 3 2
3 6 18
2 2 2 2
1 10 10
5 2
2 1 2
4 3
2 1 2
3 2 2
3 4 12
2 2 2
1 1 1
192 is the total number of ways for n=10. (not counting the number 10 itself as a total)
With slight modification (and fix to include the number itself) we get a table for various n:
2 1
3 3
4 5
5 9
6 17
7 31
8 57
9 105
10 193
11 355
12 653
13 1201
14 2209
15 4063
16 7473
17 13745
18 25281
19 46499
20 85525
21 157305
For programming reasons we didn't get values for 0 or 1, but from n=5 onward we see the rules of tribonacci's being followed: each new value is the sum of the preceding three values. But this is not the actual tribonacci sequence according to Wolfram MathWorld, which starts off differently: 0,0,1,1,2,4,7,13,..., but (see below), OEIS refers to it as a tribonacci sequence.
Programming note--an aside:
The program wasted time by calculating all the permutations of any given way and then counting how many there were. It's better to add a few extra lines to just calculate the number, by replacing the
w1=size(unique(perms(way),'rows'),1);
with
u=unique(way);
w1=factorial(s);
for i=1:length(u)
p=find(way==u(i));
w1=w1/factorial(length(p));
end
This speeds up the program sufficiently to calculate all the way to 50 in a comfortable amount of time:
21 157305
22 289329
23 532159
24 978793
25 1800281
26 3311233
27 6090307
28 11201821
29 20603361
30 37895489
31 69700671
32 128199521
33 235795681
34 433695873
35 797691075
36 1467182629
37 2698569577
38 4963443281
39 9129195487
40 16791208345
41 30883847113
42 56804250945
43 104479306403
44 192167404461
45 353450961809
46 650097672673
47 1195716038943
48 2199264673425
49 4045078385041
50 7440059097409
a(0)=1; a(1)=1; a(2)=1
a(n)=a(n-3) + a(n-2) + a(n-1)
The sequence is OEIS's A000213, Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=a(1)=a(2)=1.
|
|
Posted by Charlie
on 2022-02-27 10:42:06 |
answer--no proof
