|
| |
|
|
A002083
|
|
Narayana-Zidek-Capell numbers: a(2n)=2a(2n-1), a(2n+1)=2a(2n)-a(n).
(Formerly M0787 N0297)
|
|
14
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| Number of words beginning with 1, with sum of integers = n, in the sequence 1, 11, 111, 112, 1111, 1112, 1113, 1121, 1122, 1123, 1124, 11111, 11112, 11113, 11114, 11121, 11122, 11123, 11124, 11125, 11131, 11132, 11133, 11134, 11135, 11136, where any positive integer, in any word, is <= the sum of the preceding integers - Claude Lenormand (claude.lenormand(AT)free.fr), Jan 29 2001
a(n) = 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 (callan(AT)stat.wisc.edu), 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(c_i,i=1..r) = 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 (callan(AT)stat.wisc.edu), Feb 04 2006
Further comments from David Callan (callan(AT)stat.wisc.edu), Sep 25 2006: a(n) = # 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
.|.......|....../|\
/ \...../ \...../ \
../\.../\.
First column of A155092. [From Mats Granvik (mats.granvik(AT)abo.fi), Jan 20 2009]
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 15 2009: (Start)
Starting with offset 2 = eigensequence of triangle A101688 and row sums of
triangle A167948 (End)
|
|
|
REFERENCES
| Capell, P.; Narayana, T. V.; On knock-out tournaments. Canad. Math. Bull. 13 1970 105-109.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
Kreweras, G.; Sur quelques problemes relatifs au vote pondere, [ Some problems of weighted voting ] Math. Sci. Humaines No. 84 (1983), 45-63.
Narayana, T. V.; Quelques resultats relatifs aux tournois "knock-out" et leurs applications aux comparaisons aux paires. C. R. Acad. Sci. Paris, Series A-B 267 1968 A32-A33.
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).
M. Torelli, Increasing integer sequences and Goldbach's conjecture, preprint, 1996.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n = 1..200
Index entries for "core" sequences
|
|
|
FORMULA
| a(1)=1, else a(n) is sum of [ n/2 ] previous terms.
Conjecture: lim n->inf a(n)/2^(n-3) = a constant ~ .633368 - Gerald McGarvey (Gerald.McGarvey(AT)comcast.net), Jul 18 2004
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 (callan(AT)stat.wisc.edu), Nov 02 2005
a(n)=sum(K(n-k+1, k)*a(n - k),k=1..n), 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((n - k)!,k!)*a(n - k),k=1..n), where K(n,k) = 1 if 0 <= k <= n and 0 else. See also the comment to a similar formula for A002487.) - Thomas Wieder (thomas.wieder(AT)t-online.de), Jan 13 2008
G.f. satisfies: A(x) = (1-x - x^2*A(x^2))/(1-2x). [From Paul D. Hanna (pauldhanna(AT)juno.com), Mar 17 2010]
|
|
|
MAPLE
| A002083 := proc(n) option remember; if n<=3 then 1 elif n mod 2 = 0 then 2*A002083(n-1) else 2*A002083(n-1)-A002083((n-1)/2); fi; end;
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 (thomas.wieder(AT)t-online.de), 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} ] - from 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] (Callan)
|
|
|
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)} [From Paul D. Hanna (pauldhanna(AT)juno.com), 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
-- Reinhard Zumkeller, Dec 27 2011
|
|
|
CROSSREFS
| Cf. A045690. A058222 gives sums of words.
Cf. A001045, A002487.
Cf. A101688, A167948 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 15 2009]
Sequence in context: A123341 A141072 A043328 * A124973 A043327 A005578
Adjacent sequences: A002080 A002081 A002082 * A002084 A002085 A002086
|
|
|
KEYWORD
| easy,core,nonn,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
