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, 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

Alois P. Heinz, Table of n, a(n) for n = 1..15000

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

Adjacent sequences: A091817 A091818 A091819 * A091821 A091822 A091823

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