login
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
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?
a(2049) = 2. - Sean A. Irvine, Nov 30 2010
Computing a(1+2^k) for 11 < k <= 25 finds no additional terms equal to 2.
LINKS
EXAMPLE
Pascal's triangle (A007318):
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):
seq(a(n), n=1..100); # Alois P. Heinz, Nov 30 2010
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
Cf. A007318.
Sequence in context: A331118 A260723 A059214 * A171922 A306743 A140821
KEYWORD
nonn,look,nice
AUTHOR
Jon Perry, Mar 08 2004
EXTENSIONS
Extended and edited by John W. Layman, Mar 10 2004
Edited by Franklin T. Adams-Watters, Apr 09 2009
More terms from Sean A. Irvine, Nov 30 2010
STATUS
approved