|
|
A091820
|
|
Number of ways to reach a sum of n by a down-only cascade through Pascal's Triangle, starting at C(0,0)=1 at the apex and shifting left or right by exactly one position at each step.
|
|
1
|
|
|
1, 2, 2, 4, 2, 4, 6, 4, 2, 6, 6, 6, 8, 4, 4, 10, 2, 6, 6, 6, 8, 14, 12, 4, 6, 6, 4, 10, 6, 6, 12, 4, 6, 8, 6, 12, 14, 14, 4, 12, 8, 12, 20, 4, 4, 16, 6, 4, 6, 6, 10, 14, 4, 8, 8, 14, 12, 14, 12, 6, 10, 4, 10, 12, 6, 12, 12, 8, 4, 16, 16, 10, 22, 6, 10, 22, 14, 26, 12, 8, 6, 12, 8, 6, 14, 12, 14, 12, 6, 10, 16, 12, 10, 8, 4, 12, 10, 6, 10, 12
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
This always generates a partition of n in increasing order, but we are computing the number of cascades, not the number of distinct partitions.
For n > 1 not of the form 2^n+1, there is always a cascade with 1's and then moving over to the C(n,1) column (and its reversal), so a(n) >= 4 except for these cases. 33 can be generated by 1*4+4+10+15; is there any n > 17 with a(n) = 2? More generally, is lim_{n->infinity) a(n) = infinity?
Computing a(1+2^k) for 11 < k <= 25 finds no additional terms equal to 2.
|
|
LINKS
|
|
|
EXAMPLE
|
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Then we can create 7 by 1+1+1+1+1+1+1 on the left and right and 1+1+2+3 gives 4 more possibilities, giving a(7) = 6. Similarly, 10=10*1 (left & right) = 5*1 + 5 (left & right) = 3*1 + 3 + 4 (left & right), giving a(10)=6.
|
|
MAPLE
|
b:= proc(m, n, k) local h;
if k>n-k then b(m, n, n-k)
else h:= m -binomial(n, k);
if h<0 then 0
elif h=0 or k=0 and h<=n then 1
else b(m, n, k):= b(h, n+1, k) +b(h, n+1, k+1)
fi fi
end:
a:= n-> b(n, 0, 0):
|
|
MATHEMATICA
|
b[m_, n_, k_] := b[m, n, k] = With[{h = m - Binomial[n, k]}, Which[k == 0 && m-1 <= n, 1, k > n-k , b[m, n, n-k], h < 0, 0, h == 0, 1, True, b[h, n+1, k] + b[h, n+1, k+1] ]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Dec 09 2011, after Alois P. Heinz *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|