|
|
A002083
|
|
Narayana-Zidek-Capell numbers: a(n) = 1 for n <= 2. Otherwise a(2n) = 2a(2n-1), a(2n+1) = 2a(2n) - a(n).
(Formerly M0787 N0297)
|
|
24
|
|
|
1, 1, 1, 2, 3, 6, 11, 22, 42, 84, 165, 330, 654, 1308, 2605, 5210, 10398, 20796, 41550, 83100, 166116, 332232, 664299, 1328598, 2656866, 5313732, 10626810, 21253620, 42505932, 85011864, 170021123, 340042246, 680079282, 1360158564
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Number of compositions p(1) + p(2) + ... + p(k) = n of n into positive parts p(i) with p(1)=1 and p(k) <= Sum_{j=1..k-1} p(j), see example - Claude Lenormand (claude.lenormand(AT)free.fr), Jan 29 2001 (clarified by Joerg Arndt, Feb 01 2013)
a(n) is the number of sequences (b(1),b(2),...) of unspecified length satisfying b(1) = 1, 1 <= b(i) <= 1 + Sum[b(j),{j,i-1}] for i>=2, Sum[b(i)] = n-1. For example, a(5) = 3 counts (1, 1, 1, 1), (1, 2, 1), (1, 1, 2). These sequences are generated by the Mathematica code below. - David Callan, Nov 02 2005
a(n+1) is the number of padded compositions (d_1,d_2,...,d_n) of n satisfying d_i <= i for all i. A padded composition of n is obtained from an ordinary composition (c_1,c_2,...,c_r) of n (r >= 1, each c_i >= 1, Sum_{i=1..r} c_i = n) by inserting c_i - 1 zeros immediately after each c_i. Thus (3,1,2) -> (3,0,0,1,2,0) is a padded composition of 6 and a padded composition of n has length n. For example, with n=4, a(5) counts (1,1,1,1), (1,1,2,0), (1,2,0,1). - David Callan, Feb 04 2006
a(n) is the number of ordered trees on n edges in which (i) every node (= non-root non-leaf vertex) has at least 2 children and (ii) each leaf is either the leftmost or rightmost child of its parent.
For example, a(4)=2 counts
./\.../\
/\...../\,
and a(5)=3 counts
.|.......|....../|\
/ \...../ \...../ \
../\.../\.
(End)
If we remove the condition that a(2) = 1, then the resulting sequence is A045690 minus the first term. - Chai Wah Wu, Nov 08 2022
|
|
REFERENCES
|
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.28.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
M. A. Stern, 5. Aufgaben., Journal für die reine und angewandte Mathematik (Crelle's journal), volume 18, 1838, p. 100.
|
|
FORMULA
|
a(1)=1, else a(n) is sum of floor(n/2) previous terms.
Limit is equal to 0.633368347305411640436713144616576659... = 2*Atkinson-Negro-Santoro constant = 2*A242729, see Finch's book, chapter 2.28 (Erdős' Sum-Distinct Set Constant), pp. 189, 552. - Vaclav Kotesovec, Nov 19 2012
a(n) is the permanent of the (n-1) X (n-1) matrix with (i, j) entry = 1 if i-1 <= j <= 2*i-1 and = 0 otherwise. - David Callan, Nov 02 2005
a(n) = Sum_{k=1..n} K(n-k+1, k)*a(n-k), where K(n,k) = 1 if 0 <= k AND k <= n and K(n,k)=0 else. (Several arguments to the K-coefficient K(n,k) can lead to the same sequence. For example, we get A002083 also from a(n) = Sum_{k=1..n} K((n-k)!,k!)*a(n-k), where K(n,k) = 1 if 0 <= k <= n and 0 else. See also the comment to a similar formula for A002487.) - Thomas Wieder, Jan 13 2008
G.f. satisfies: A(x) = (1-x - x^2*A(x^2))/(1-2x). - Paul D. Hanna, Mar 17 2010
|
|
EXAMPLE
|
The a(7) = 11 compositions p(1) + p(2) + ... + p(k) = 7 of 7 into positive parts p(i) with p(1)=1 and p(k) <= Sum_{j=1..k-1} p(j) are
[ 1] [ 1 1 1 1 1 1 1 ]
[ 2] [ 1 1 1 1 1 2 ]
[ 3] [ 1 1 1 1 2 1 ]
[ 4] [ 1 1 1 1 3 ]
[ 5] [ 1 1 1 2 1 1 ]
[ 6] [ 1 1 1 2 2 ]
[ 7] [ 1 1 1 3 1 ]
[ 8] [ 1 1 2 1 1 1 ]
[ 9] [ 1 1 2 1 2 ]
[10] [ 1 1 2 2 1 ]
[11] [ 1 1 2 3 ]
(End)
|
|
MAPLE
|
A002083 := proc(n) option remember; if n<=3 then 1 elif n mod 2 = 0 then 2*procname(n-1) else 2*procname(n-1)-procname((n-1)/2); end if; end proc:
a := proc(n::integer) # A002083 Narayana-Zidek-Capell numbers: a(2n)=2a(2n-1), a(2n+1)=2a(2n)-a(n). local k; option remember; if n = 0 then 1 else add(K(n-k+1, k)*procname(n - k), k = 1 .. n); #else add(K((n-k)!, k!)*procname(n - k), k = 1 .. n); end if end proc; K := proc(n::integer, k::integer) local KC; if 0 <= k and k <= n then KC := 1 else KC := 0 end if; end proc; # Thomas Wieder, Jan 13 2008
|
|
MATHEMATICA
|
a[1] = 1; a[n_] := a[n] = Sum[a[k], {k, n/2, n-1} ]; Table[ a[n], {n, 2, 70, 2} ] (* Robert G. Wilson v, Apr 22 2001 *)
bSequences[1]={ {1} }; bSequences[n_]/; n>=2 := bSequences[n] = Flatten[Table[Map[Join[ #, {i}]&, bSequences[n-i]], {i, Ceiling[n/2]}], 1] (* David Callan *)
a=ConstantArray[0, 20]; a[[1]]=1; a[[2]]=1; Do[If[EvenQ[n], a[[n]]=2a[[n-1]], a[[n]]=2a[[n-1]]-a[[(n-1)/2]]]; , {n, 3, 20}]; a (* Vaclav Kotesovec, Nov 19 2012 *)
|
|
PROG
|
(PARI) a(n)=if(n<3, n>0, 2*a(n-1)-(n%2)*a(n\2))
(PARI) a(n)=local(A=1+x); for(i=1, n, A=(1-x-x^2*subst(A, x, x^2+O(x^n)))/(1-2*x)); polcoeff(A, n) \\ Paul D. Hanna, Mar 17 2010
(Haskell)
a002083 n = a002083_list !! (n-1)
a002083_list = 1 : f [1] where
f xs = x : f (x:xs) where x = sum $ take (div (1 + length xs) 2) xs
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,core,nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|