A091820 - OEIS

%I #42 Aug 26 2024 02:07:43

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

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

%U 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

%N 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.

%C This always generates a partition of n in increasing order, but we are computing the number of cascades, not the number of distinct partitions.

%C 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?

%C a(2049) = 2. - _Sean A. Irvine_, Nov 30 2010

%C Computing a(1+2^k) for 11 < k <= 25 finds no additional terms equal to 2.

%H Alois P. Heinz, <a href="/A091820/b091820.txt">Table of n, a(n) for n = 1..15000</a>

%e Pascal's triangle (A007318):

%e             1

%e           1   1

%e         1   2   1

%e       1   3   3   1

%e     1   4   6   4   1

%e   1   5  10  10   5   1

%e 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.

%p b:= proc(m, n, k) local h;

%p       if k>n-k then b(m, n, n-k)

%p     else h:= m -binomial(n, k);

%p          if h<0 then 0

%p        elif h=0 or k=0 and h<=n then 1

%p        else b(m, n, k):= b(h, n+1, k) +b(h, n+1, k+1)

%p       fi fi

%p     end:

%p a:= n-> b(n, 0, 0):

%p seq(a(n), n=1..100);  # _Alois P. Heinz_, Nov 30 2010

%t 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_ *)

%Y Cf. A007318.

%K nonn,look,nice

%O 1,2

%A _Jon Perry_, Mar 08 2004

%E Extended and edited by _John W. Layman_, Mar 10 2004

%E Edited by _Franklin T. Adams-Watters_, Apr 09 2009

%E More terms from _Sean A. Irvine_, Nov 30 2010