login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

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

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)

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.

Index entries for "core" sequences

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

Limit is equal to 0.633368347305411640436713144616576659... = 2* Atkinson-Negro-Santoro constant, see Finch's book, chapter 2.28 (Erdos' 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

CROSSREFS

Cf. A045690. A058222 gives sums of words.

Cf. A001045, A002487, A101688, A167948.

Bisections: A245094, A259858.

Sequence in context: A238351 A141072 A043328 * A124973 A318123 A226594

Adjacent sequences:  A002080 A002081 A002082 * A002084 A002085 A002086

KEYWORD

easy,core,nonn,nice

AUTHOR

N. J. A. Sloane

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 23:12 EDT 2018. Contains 316275 sequences. (Running on oeis4.)