%I M0787 N0297 #157 Jun 07 2024 04:42:37

%S 1,1,1,2,3,6,11,22,42,84,165,330,654,1308,2605,5210,10398,20796,41550,

%T 83100,166116,332232,664299,1328598,2656866,5313732,10626810,21253620,

%U 42505932,85011864,170021123,340042246,680079282,1360158564

%N Narayana-Zidek-Capell numbers: a(n) = 1 for n <= 2. Otherwise a(2n) = 2a(2n-1), a(2n+1) = 2a(2n) - a(n).

%C 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)

%C 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

%C 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

%C From _David Callan_, Sep 25 2006: (Start)

%C 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.

%C For example, a(4)=2 counts

%C ./\.../\

%C /\...../\,

%C and a(5)=3 counts

%C .|.......|....../|\

%C / \...../ \...../ \

%C ../\.../\.

%C (End)

%C Starting with offset 2 = eigensequence of triangle A101688 and row sums of triangle A167948. - _Gary W. Adamson_, Nov 15 2009

%C 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

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.28.

%D T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Seiichi Manyama, <a href="/A002083/b002083.txt">Table of n, a(n) for n = 1..3325</a> (first 200 terms from T. D. Noe)

%H Magnus Aspenberg and Rodrigo Perez, <a href="https://arxiv.org/abs/1006.1340">Control of cancellations that restrain the growth of a binomial recursion</a>, arXiv:1006.1340 [math.CO], 2010. Mentions this sequence.

%H P. Capell and T. V. Narayana, <a href="http://dx.doi.org/10.4153/CMB-1970-021-1">On knock-out tournaments</a>, Canad. Math. Bull. 13 1970 105-109.

%H Nathaniel D. Emerson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.html">A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.

%H G. Kreweras, <a href="http://www.numdam.org/item?id=MSH_1983__84__45_0">Sur quelques problèmes relatifs au vote pondéré</a>, [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.

%H G. Kreweras, and P. Moszkowski, <a href="http://dx.doi.org/10.1016/0378-3758(86)90011-X">A new enumerative property of the Narayana numbers</a>, Journal of statistical planning and inference 14.1 (1986): 63-67.

%H D. Levin, L. Pudwell, M. Riehl and A. Sandberg, <a href="https://www.etsu.edu/cas/math/documents/riehl.pdf">Pattern Avoidance on k-ary Heaps</a>, Slides of Talk, 2014.

%H J. W. Moon, R. K. Guy and N. J. A. Sloane, <a href="/A002083/a002083.pdf">Correspondence, 1988</a>

%H T. V. Narayana, <a href="http://visualiseur.bnf.fr/Visualiseur?O=NUMM-480295&amp;I=000035&amp;M=tdm">Quelques résultats relatifs aux tournois "knock-out" et leurs applications aux comparaisons aux paires</a>, C. R. Acad. Sci. Paris, Series A-B 267 1968 A32-A33.

%H T. V. Narayana and J. Zidek, <a href="http://www.numdam.org/item?id=BURO_1969__13__3_0">Contributions to the theory of tournaments I</a>, Cahiers du Bur. Univ. de Rech. Oper., 13 (1969), 1-18. [MR 0256734, 41 #1390]

%H John Riordan and N. J. A. Sloane, <a href="/A003471/a003471_1.pdf">Correspondence, 1974</a>

%H M. A. Stern, <a href="https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002141558">5. Aufgaben.</a>, Journal für die reine und angewandte Mathematik (Crelle's journal), volume 18, 1838, p. 100.

%H Mauro Torelli, <a href="http://www.numdam.org/item?id=ITA_2006__40_2_107_0">Increasing integer sequences and Goldbach's conjecture</a>, RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 40:2 (2006), pp. 107-121.

%H B. E. Wynne & N. J. A. Sloane, <a href="/A002083/a002083_1.pdf">Correspondence, 1976-84</a>

%H B. E. Wynne & T. V. Narayana, <a href="/A002083/a002083_2.pdf">Tournament configuration, weighted voting, and partitioned catalans</a>, Preprint.

%H Bayard Edmund Wynne and T. V. Narayana, <a href="http://www.numdam.org/item?id=BURO_1981__36__75_0">Tournament configuration and weighted voting</a>, Cahiers du bureau universitaire de recherche opérationnelle, 36 (1981): 75-78.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

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

%F Conjecture: lim_{n->oo} a(n)/2^(n-3) = a constant ~0.633368 (=2*A242729). - _Gerald McGarvey_, Jul 18 2004

%F First column of A155092. - _Mats Granvik_, Jan 20 2009

%F a(n+2) = A037254(n,1) = A037254(n,floor(n/2)+1). - _Reinhard Zumkeller_, Nov 18 2012

%F 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

%F 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

%F 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

%F G.f. satisfies: A(x) = (1-x - x^2*A(x^2))/(1-2x). - _Paul D. Hanna_, Mar 17 2010

%e From _Joerg Arndt_, Feb 01 2013: (Start)

%e 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

%e [ 1] [ 1 1 1 1 1 1 1 ]

%e [ 2] [ 1 1 1 1 1 2 ]

%e [ 3] [ 1 1 1 1 2 1 ]

%e [ 4] [ 1 1 1 1 3 ]

%e [ 5] [ 1 1 1 2 1 1 ]

%e [ 6] [ 1 1 1 2 2 ]

%e [ 7] [ 1 1 1 3 1 ]

%e [ 8] [ 1 1 2 1 1 1 ]

%e [ 9] [ 1 1 2 1 2 ]

%e [10] [ 1 1 2 2 1 ]

%e [11] [ 1 1 2 3 ]

%e (End)

%p 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:

%p 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

%t 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 *)

%t bSequences[1]={ {1} }; bSequences[n_]/;n>=2 := bSequences[n] = Flatten[Table[Map[Join[ #, {i}]&, bSequences[n-i]], {i, Ceiling[n/2]}], 1] (* _David Callan_ *)

%t 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 *)

%o (PARI) a(n)=if(n<3,n>0,2*a(n-1)-(n%2)*a(n\2))

%o (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

%o (Haskell)

%o a002083 n = a002083_list !! (n-1)

%o a002083_list = 1 : f [1] where

%o f xs = x : f (x:xs) where x = sum $ take (div (1 + length xs) 2) xs

%o -- _Reinhard Zumkeller_, Dec 27 2011

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o 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

%Y Cf. A045690. A058222 gives sums of words.

%Y Cf. A001045, A002487, A101688, A167948.

%Y Cf. A242729.

%Y Bisections: A245094, A259858.

%K easy,core,nonn,nice

%O 1,4

%A _N. J. A. Sloane_

%E Definition clarified by _Chai Wah Wu_, Nov 08 2022