login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

From David Callan, Sep 25 2006: (Start)

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)

Starting with offset 2 = eigensequence of triangle A101688 and row sums of triangle A167948. - Gary W. Adamson, Nov 15 2009

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

T. D. Noe and Seiichi Manyama, Table of n, a(n) for n = 1..3325 (first 200 terms from T. D. Noe)

Magnus Aspenberg and Rodrigo Perez, Control of cancellations that restrain the growth of a binomial recursion, arXiv:1006.1340 [math.CO], 2010. Mentions this sequence.

P. Capell and 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 and A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.

J. W. Moon, R. K. Guy and 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

M. A. Stern, 5. Aufgaben., Journal für die reine und angewandte Mathematik (Crelle's journal), volume 18, 1838, p. 100.

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.

Index entries for "core" sequences

FORMULA

a(1)=1, else a(n) is sum of floor(n/2) previous terms.

Conjecture: lim_{n->oo} a(n)/2^(n-3) = a constant ~0.633368 (=2*A242729). - 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 = 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

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 ]

[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*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] = 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

-- Reinhard Zumkeller, Dec 27 2011

(Python)

from functools import lru_cache

@lru_cache(maxsize=None)

def A002083(n): return 1 if n <=3 else (A002083(n-1)<<1)-(A002083(n>>1) if n&1 else 0) # Chai Wah Wu, Nov 07 2022

CROSSREFS

Cf. A045690. A058222 gives sums of words.

Cf. A001045, A002487, A101688, A167948.

Cf. A242729.

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

N. J. A. Sloane

EXTENSIONS

Definition clarified by Chai Wah Wu, Nov 08 2022

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 22:27 EST 2022. Contains 358671 sequences. (Running on oeis4.)