[go: up one dir, main page]

login
Search: a155092 -id:a155092
     Sort: relevance | references | number | modified | created      Format: long | short | data
Third column of A155092.
+20
0
1, 1, 2, 4, 7, 14, 27, 54, 106, 212, 420, 840, 1673, 3346, 6678, 13356, 26685, 53370, 106686, 213372, 426638, 853276, 1706340, 3412680, 6824940, 13649880
OFFSET
1,3
KEYWORD
more,nonn
AUTHOR
Mats Granvik, Jan 20 2009
STATUS
approved
Number of binary words of length n (beginning with 0) whose autocorrelation function is the indicator of a singleton.
+10
29
1, 1, 2, 3, 6, 10, 20, 37, 74, 142, 284, 558, 1116, 2212, 4424, 8811, 17622, 35170, 70340, 140538, 281076, 561868, 1123736, 2246914, 4493828, 8986540, 17973080, 35943948, 71887896, 143771368, 287542736, 575076661, 1150153322, 2300289022, 4600578044, 9201120918
OFFSET
1,3
COMMENTS
The number of binary strings sharing the same autocorrelations.
Appears to be row sums of A155092, beginning from a(2). - Mats Granvik, Jan 20 2009
The number of binary words of length n (beginning with 0) which do not start with an even palindrome (i.e. which are not of the form ss*t where s is a (nonempty) word, s* is its reverse, and t is any (possibly empty) word). - Mamuka Jibladze, Sep 30 2014
From Gus Wiseman, Mar 08 2021: (Start)
This sequence counts each of the following essentially equivalent things:
1. Sets of distinct positive integers with maximum n in which all adjacent elements have quotients > 1/2. For example, the a(1) = 1 through a(6) = 10 sets are:
{1} {2} {3} {4} {5} {6}
{2,3} {3,4} {3,5} {4,6}
{2,3,4} {4,5} {5,6}
{2,3,5} {3,4,6}
{3,4,5} {3,5,6}
{2,3,4,5} {4,5,6}
{2,3,4,6}
{2,3,5,6}
{3,4,5,6}
{2,3,4,5,6}
2. For n > 1, sets of distinct positive integers with maximum n - 1 whose first-differences are term-wise less than their decapitation (remove the maximum). For example, the set q = {2,4,5} has first-differences (2,1), which are not less than (2,4), so q is not counted under a(5). On the other hand, r = {2,3,5,6} has first-differences {1,2,1}, which are less than {2,3,5}, so r is counted under a(6).
3. Compositions of n where each part after the first is less than the sum of all preceding parts. For example, the a(1) = 1 through a(6) = 10 compositions are:
(1) (2) (3) (4) (5) (6)
(21) (31) (41) (51)
(211) (32) (42)
(311) (411)
(212) (321)
(2111) (312)
(3111)
(2121)
(2112)
(21111)
(End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..3324 (first 500 terms from T. D. Noe)
E. H. Rivals, S. Rahmann Combinatorics of Periods in Strings
E. H. Rivals, S. Rahmann, Combinatorics of Periods in Strings, Journal of Combinatorial Theory - Series A, Vol. 104(1) (2003), pp. 95-113.
FORMULA
a(2n) = 2*a(2n-1) - a(n) for n >= 1; a(2n+1) = 2*a(2n) for n >= 1.
a(n) = A342085(2^n). - Gus Wiseman, Mar 08 2021
MAPLE
a:= proc(n) option remember; `if`(n=0, 1/2,
2*a(n-1)-`if`(n::odd, 0, a(n/2)))
end:
seq(a(n), n=1..40); # Alois P. Heinz, Jun 24 2021
MATHEMATICA
a[1] = 1; a[n_] := a[n] = If[EvenQ[n], 2*a[n-1] - a[n/2], 2*a[n-1]]; Array[a, 40] (* Jean-François Alcover, Jul 17 2015 *)
Table[Length[Select[Subsets[Range[n]], MemberQ[#, n]&&Min@@Divide@@@Partition[#, 2, 1]>1/2&]], {n, 8}] (* Gus Wiseman, Mar 08 2021 *)
PROG
(PARI) a(n)=if(n<2, n>0, 2*a(n-1)-(1-n%2)*a(n\2))
CROSSREFS
Cf. A002083, A005434. A003000 = 2*a(n) for n > 0.
Different from, but easily confused with, A007148 and A093371.
The version with quotients <= 1/2 is A018819.
The version with quotients < 1/2 is A040039.
Multiplicative versions are A337135, A342083, A342084, A342085.
A000045 counts sets containing n with all differences > 2.
A000929 counts partitions with no adjacent parts having quotient < 2.
A342094 counts partitions with no adjacent parts having quotient > 2.
KEYWORD
nonn,easy,nice
AUTHOR
Torsten.Sillke(AT)uni-bielefeld.de
EXTENSIONS
More terms from James A. Sellers.
Additional comments from Michael Somos, Jun 09 2000
STATUS
approved
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)
+10
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
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
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
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->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*procname(n-1) else 2*procname(n-1)-procname((n-1)/2); end if; end proc:
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. A242729.
Bisections: A245094, A259858.
KEYWORD
easy,core,nonn,nice
EXTENSIONS
Definition clarified by Chai Wah Wu, Nov 08 2022
STATUS
approved
Triangle read by rows. Signed version of A145362. Main diagonal positive, rest of the nonzero terms negative.
+10
1
1, -1, 1, 0, -1, 1, 0, -1, -1, 1, 0, 0, -1, -1, 1, 0, 0, -1, -1, -1, 1, 0, 0, 0, -1, -1, -1, 1, 0, 0, 0, -1, -1, -1, -1, 1, 0, 0, 0, 0, -1, -1, -1, -1, 1, 0, 0, 0, 0, -1, -1, -1, -1, -1, 1, 0, 0, 0, 0, 0, -1, -1, -1, -1, -1, 1, 0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, 1, 0, 0, 0, 0, 0, 0, -1, -1
OFFSET
1,1
COMMENTS
Matrix inverse of this triangle is A155092.
EXAMPLE
Table begins:
1,
-1,1,
0,-1,1,
0,-1,-1,1,
0,0,-1,-1,1,
0,0,-1,-1,-1,1,
0,0,0,-1,-1,-1,1,
0,0,0,-1,-1,-1,-1,1,
0,0,0,0,-1,-1,-1,-1,1,
0,0,0,0,-1,-1,-1,-1,-1,1,
CROSSREFS
Cf. A145362.
KEYWORD
sign,tabl
AUTHOR
Mats Granvik, Jan 20 2009
STATUS
approved

Search completed in 0.010 seconds