A366120 Number of ways to choose a multiset of values whose sum is n from the first floor(1+log_2(n)) rows of Pascal's triangle.

1, 3, 1, 15, 11, 5, 1, 141, 127, 100, 70, 44, 22, 7, 1, 2453, 2393, 2249, 2035, 1784, 1508, 1222, 948, 694, 472, 302, 182, 95, 37, 9, 1, 84870, 84278, 82769, 80217, 76934, 73302, 69363, 64917, 59951, 54787, 49746, 44826, 39850, 34830, 30018, 25614, 21575, 17777

Offset

1,2

Links

Table of n, a(n) for n=1..49.

Formula

a(n) = [x^n] Product_{k=0..floor(log_2(n))} Product_{j=0..k} (1 + x^binomial(k, j)). - Andrew Howroyd, Oct 28 2023

Example

For n = 5 we use the first 3 rows of Pascal's triangle:
  1;
  1, 1;
  1, 2, 1;
There are C(1,1)*C(5,3) = 10 ways to make the sum 2 + 1 + 1 + 1
and C(5,5) = 1 ways to make the sum 1 + 1 + 1 + 1 + 1,
so a(5) = 10 + 1 = 11.

Prog

(PARI) a(n) = polcoef(prod(k=0, logint(n, 2), prod(j=0, k, 1 + x^binomial(k, j) + O(x*x^n))), n) \\ Andrew Howroyd, Oct 28 2023

Crossrefs

Cf. A007318 (Pascal's triangle).

Sequence in context: A144006 A014621 A193966 * A113378 A365162 A178657

Adjacent sequences: A366117 A366118 A366119 * A366121 A366122 A366123

Keyword

nonn

Author

Guderian Raborg, Sep 30 2023

Extensions

Terms a(16) and beyond from Andrew Howroyd, Oct 28 2023

Status

approved