The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A002083 Narayana-Zidek-Capell numbers: 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) = 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) = # 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   .|.......|....../|\   / \...../ \...../ \   ../\.../\.   - David Callan, Sep 25 2006 Starting with offset 2 = eigensequence of triangle A101688 and row sums of triangle A167948. - Gary W. Adamson, Nov 15 2009 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 T. D. Noe and Seiichi Manyama, Table of n, a(n) for n = 1..3325 (first 200 terms from T. D. Noe) Magnus Aspenberg, Rodrigo Perez, Control of cancellations that restrain the growth of a binomial recursion, arXiv:1006.1340 [math.CO], 2010. Mentions this sequence. P. Capell, T. V. Narayana, 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. G. Kreweras, Sur quelques problèmes relatifs au vote pondéré, [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63. G. Kreweras, and P. Moszkowski, A new enumerative property of the Narayana numbers, Journal of statistical planning and inference 14.1 (1986): 63-67. D. Levin, L. Pudwell, M. Riehl, A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014. J. W. Moon, R. K. Guy, N. J. A. Sloane, Correspondence, 1988 T. V. Narayana, Quelques résultats 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 and J. Zidek, Contributions to the theory of tournaments I, Cahiers du Bur. Univ. de Rech. Oper., 13 (1969), 1-18. [MR 0256734, 41 #1390] John Riordan and N. J. A. Sloane, Correspondence, 1974 Mauro Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 40:2 (2006), pp. 107-121. B. E. Wynne & N. J. A. Sloane, Correspondence, 1976-84 B. E. Wynne & T. V. Narayana, Tournament configuration, weighted voting, and partitioned catalans, Preprint. Bayard Edmund Wynne, and T. V. Narayana, Tournament configuration and weighted voting, Cahiers du bureau universitaire de recherche opérationnelle, 36 (1981): 75-78. FORMULA a(1)=1, else a(n) is sum of floor(n/2) previous terms. Conjecture: lim_{n->inf} a(n)/2^(n-3) = a constant ~ 0.633368 - Gerald McGarvey, Jul 18 2004 First column of A155092. - Mats Granvik, Jan 20 2009 a(n+2) = A037254(n,1) = A037254(n,floor(n/2)+1). - Reinhard Zumkeller, Nov 18 2012 Limit is equal to 0.633368347305411640436713144616576659... = 2* Atkinson-Negro-Santoro constant, 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 From Joerg Arndt, Feb 01 2013: (Start) 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 ]   [ 1 1 2 2 1 ]   [ 1 1 2 3 ] (End) 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, Jan 13 2008 MATHEMATICA a = 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} }; 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; a[]=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  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, A101688, A167948. Bisections: A245094, A259858. Sequence in context: A238351 A043328 A141072 * A124973 A318123 A226594 Adjacent sequences:  A002080 A002081 A002082 * A002084 A002085 A002086 KEYWORD easy,core,nonn,nice AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 18 02:38 EDT 2021. Contains 343072 sequences. (Running on oeis4.)