|
|
A023359
|
|
Number of compositions (ordered partitions) of n into powers of 2.
|
|
37
|
|
|
1, 1, 2, 3, 6, 10, 18, 31, 56, 98, 174, 306, 542, 956, 1690, 2983, 5272, 9310, 16448, 29050, 51318, 90644, 160118, 282826, 499590, 882468, 1558798, 2753448, 4863696, 8591212, 15175514, 26805983, 47350056, 83639030, 147739848, 260967362
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) is the number of partitions of 2n into n parts, with each partition realized into non-symmetric permutations ignoring 1's. For example a(6): the partitions of 12 into 6 are: 111117 (1), 111126 (1), 111135 (1), 111144 (1), 111225 (2), 111234 (3), 111333 (1), 112233 (3), 112224 (2), 122223 (2), 222222 (1), where the number in brackets is the number of non-symmetric permutations ignoring 1's (e.g., 111234, ignore 1's -> 234 and we can also have 243 and 324, 112233->2233 or 2323 or 2332). The sum of the bracketed numbers is a(6)=18. - Jon Perry, Jun 22 2003
a(n) is an eigensequence for the sequence array of the Fredholm-Rueppel sequence A036987. - Paul Barry, Nov 03 2010
a(n) is the number of ways to express n in Napier's location numerals (see Wikipedia). - P. Christopher Staecker, Jul 04 2024
|
|
LINKS
|
|
|
FORMULA
|
G.f.: 1 / (1 - Sum_{k>=0} x^(2^k)). - Joerg Arndt, Oct 21 2012
a(n) = [n=0] + Sum_{k>=0} a(n-2^k). - Len Smiley, May 07 2001
INVERT transform of characteristic function of powers of 2, i.e., A036987 interpreted with an offset 1 instead of 0. - Antti Karttunen, Dec 12 2003
a(n) seems to be asymptotic to A*B^n where A=0.332198..., B=1.766398... - Benoit Cloitre, Dec 17 2002. More accurately: B=1.76639811455017359722848839244009973023206928795707277527828507440838434..., A=0.58679374529351144845013208294162259198824401250194713608555348278359775... - Vaclav Kotesovec, Apr 30 2014
Satisfies A(x) = 1 + A(x) * Sum_{k>=0} x^(2^k). a(m) == 1 (mod 2) when m=2^n-1, otherwise a(m) == 0 (mod 2). - Paul D. Hanna, Aug 27 2003
|
|
EXAMPLE
|
A(x) = A(x^2) + x*A(x^2)^2 + x^2*A(x^2)^3 + x^3*A(x^2)^4 + ... = 1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + 18x^6 + 31x^7 + ....
There are a(6)=18 compositions of 6 into powers of 2:
[ 1] [ 1 1 1 1 1 1 ]
[ 2] [ 1 1 1 1 2 ]
[ 3] [ 1 1 1 2 1 ]
[ 4] [ 1 1 2 1 1 ]
[ 5] [ 1 1 2 2 ]
[ 6] [ 1 1 4 ]
[ 7] [ 1 2 1 1 1 ]
[ 8] [ 1 2 1 2 ]
[ 9] [ 1 2 2 1 ]
[10] [ 1 4 1 ]
[11] [ 2 1 1 1 1 ]
[12] [ 2 1 1 2 ]
[13] [ 2 1 2 1 ]
[14] [ 2 2 1 1 ]
[15] [ 2 2 2 ]
[16] [ 2 4 ]
[17] [ 4 1 1 ]
[18] [ 4 2 ]
(End)
|
|
MAPLE
|
a:= proc(n) option remember;
`if`(n=0, 1, add(a(n-2^i), i=0..ilog2(n)))
end:
|
|
MATHEMATICA
|
CoefficientList[Series[1/(1 - Sum[x^(2^i), {i, 0, 20}]), {x, 0, 20}], x]
|
|
PROG
|
(PARI) {a(n) = local(A, m); if( n<0, 0, m=1; A = 1 + O(x); while( m<=n, m*=2; A = 1 /(1 / subst(A, x, x^2) - x)); polcoeff(A, n))}; /* Michael Somos, Dec 20 2002 */
(PARI)
N=66; x='x+O('x^N);
Vec( 1/(1-sum(k=0, ceil(log(N)/log(2)), x^(2^k) ) ) )
|
|
CROSSREFS
|
The column sums of the table A073265.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|