A032263 -id:A032263 - cp's OEIS frontend

A007582 a(n) = 2^(n-1)*(1+2^n).

1, 3, 10, 36, 136, 528, 2080, 8256, 32896, 131328, 524800, 2098176, 8390656, 33558528, 134225920, 536887296, 2147516416, 8590000128, 34359869440, 137439215616, 549756338176, 2199024304128, 8796095119360, 35184376283136, 140737496743936, 562949970198528

Offset: 0

Simon Plouffe

Let G_n be the elementary Abelian group G_n = (C_2)^n for n >= 1: A006516 is the number of times the number -1 appears in the character table of G_n and A007582 is the number of times the number 1. Together the two sequences cover all the values in the table, i.e., A006516(n) + A007582(n) = 2^(2n). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 01 2001
Number of walks of length 2n+1 between two adjacent vertices in the cycle graph C_8. Example: a(1)=3 because in the cycle ABCDEFGH we have three walks of length 3 between A and B: ABAB, ABCB and AHAB. - Emeric Deutsch, Apr 01 2004
Smallest number containing in its binary representation two equal non-overlapping subwords of length n: A097295(a(n))=n and A097295(m)Reinhard Zumkeller, Aug 04 2004
a(n)^2 + (A006516(n))^2 = a(2n). E.g., a(3) = 36, A006516(3) = 28, a(6) = 2080. 36^2 + 28^2 = 2080. - Gary W. Adamson, Jun 17 2006
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either x equals y or x does not equal y. - Ross La Haye, Jan 02 2008
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A). This is just a simpler statement of my previous comment for this sequence. - Ross La Haye, Jan 10 2008
For n>0: A000120(a(n))=2, A023414(a(n))=2*(n-1), A087117(a(n))=n-1. - Reinhard Zumkeller, Jun 23 2009
a(n+1) written in base 2: 11, 1010, 100100, 10001000, 1000010000, ..., i.e., number 1, n times 0, number 1, n times 0 (A163449(n)). - Jaroslav Krizek, Jul 27 2009
a(n) for n >= 1 is a bisection of A001445(n+1). - Jaroslav Krizek, Aug 14 2009
Related to A102573: letting T(q,r) be the coefficient of n^(r+1) in the polynomial 2^(q-n)/n times sum_{k=0..n} binomial(n,k)*k^q, then A007582(x)= sum_{k=0..x-1} T(x,k)*2^k. - John M. Campbell, Nov 16 2011
a(n) gives the number of pairs (r, s) such that 0 <= r <= s <= (2^n)-1 that satisfy AND(r, s, XOR(r, s)) = 0. - Ramasamy Chandramouli, Aug 30 2012
a(n) = A000217(2^n) = 2^(2n-1) + 2^(n-1) is the nearest triangular number above 2^(2n-1); cf. A006516, A233327. - Antti Karttunen, Feb 26 2014
Consider the quantum spin-1/2 chain with even number of sites L (physics, condensed matter theory). The spectrum of the Hamiltonian can be classified according to symmetries. If the only symmetry of the spin Hamiltonian is Parity, i.e., reflection with respect to the middle of the chain (see e.g. the transverse-field Ising model with open boundary conditions), then the dimension of the p=+1 parity sector is given by a(n) with n=L/2. - Marin Bukov, Mar 11 2016
a(n) is also the total number of words of length n, over an alphabet of four letters, of which one of them appears an even number of times. See the Lekraj Beedassy, Jul 22 2003, comment on A006516 (4-letter odd case), and the Balakrishnan reference there. For the 1- to 11-letter cases, see the crossrefs. - Wolfdieter Lang, Jul 17 2017
a(n) is the number of nonisomorphic spanning trees of the cyclic snake formed with n+1 copies of the cycle on 4 vertices. A cyclic snake is a connected graph whose block-cutpoint is a path and all its n blocks are isomorphic to the cycle C_m. - Christian Barrientos, Sep 05 2024
Also, with offset 1, the cogrowth sequence of the dihedral group with 16 elements, D8 = . - Sean A. Irvine, Nov 06 2024

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

T. D. Noe, Table of n, a(n) for n=0..200
M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
S. Hong and J. H. Kwak, Regular fourfold coverings with respect to the identity automorphism, J. Graph Theory, 17 (1993), 621-627.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 168
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Mircea Merca, A Note on Cosine Power Sums, J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
Index entries for linear recurrences with constant coefficients, signature (6,-8)

Cf. A000217, A049773, A049775.
Cf. A006516.
Cf. A134308.
Cf. A000225, A000392, A032263, A028243, A000079.
Cf. A102573.
The number of words of length n with m letters, one of them appearing an even number of times is for m = 1..11: A000035, A011782,  A007051, A007582, A081186, A081187, A081188, A081189, A081190, A060531, A081192. - Wolfdieter Lang, Jul 17 2017

[Binomial(2^n + 1, 2) : n in [0..30]]; // Wesley Ivan Hurt, Jul 03 2020

seq(binomial(-2^n, 2), n=0..23); # Zerinvary Lajos, Feb 22 2008

Table[ Binomial[2^n + 1, 2], {n, 0, 23}] (* Robert G. Wilson v, Jul 30 2004 *)
LinearRecurrence[{6,-8},{1,3},30] (* Harvey P. Dale, Apr 08 2013 *)

A007582(n):=2^(n-1)*(1+2^n)$ makelist(A007582(n),n,0,30); /* Martin Ettl, Nov 15 2012 */

PARI
```
a(n)=if(n<0,0,2^(n-1)*(1+2^n))
```

a(n)=sum(k=-n\4,n\4,binomial(2*n+1,n+1+4*k))

G.f.: (1-3*x)/((1-2*x)*(1-4*x)). C(1+2^n, 2) where C(n, 2) is n-th triangular number A000217.
Binomial transform of A007051. Inverse binomial transform of A081186. - Paul Barry, Apr 07 2003
E.g.f.: exp(3*x)*cosh(x). - Paul Barry, Apr 07 2003
a(n) = Sum_{k=0..floor(n/2)} C(n, 2*k)*3^(n-2*k). - Paul Barry, May 08 2003
a(n+1) = 4*a(n) - 2^n; see also A049775. a(n) = 2^(n-1)*A000051(n). - Philippe Deléham, Feb 20 2004
a(n) = 6*a(n-1) - 8*a(n-2). - Emeric Deutsch, Apr 01 2004
Row sums of triangle A134308. - Gary W. Adamson, Oct 19 2007
a(n) = StirlingS2(2^n + 1,2^n) = 1 + 2*StirlingS2(n+1,2) + 3*StirlingS2(n+1,3) + 3*StirlingS2(n+1,4) = StirlingS2(n+2,2) + 3(StirlingS2(n+1,3) + StirlingS2(n+1,4)). - Ross La Haye, Mar 01 2008
a(n) = StirlingS2(2^n + 1,2^n) = 1 + 2*StirlingS2(n+1,2) + 3*StirlingS2(n+1,3) + 3*StirlingS2(n+1,4) = StirlingS2(n+2,2) + 3(StirlingS2(n+1,3) + StirlingS2(n+1,4)). - Ross La Haye, Apr 02 2008
a(n) = A000079(n) + A006516(n). - Yosu Yurramendi, Aug 06 2008
a(n) = A028403(n+1) / 4. - Jaroslav Krizek, Jul 27 2009
a(n) = Sum_{k=-floor(n/4)..floor(n/4)} binomial(2*n,n+4*k)/2. - Mircea Merca, Jan 28 2012
G.f.: Q(0)/2 where Q(k) = 1 + 2^k/(1 - 2*x/(2*x + 2^k/Q(k+1) )); (continued fraction ). - Sergei N. Gladkovskii, Apr 10 2013
a(n) = Sum_{k=1..2^n} k. - Joerg Arndt, Sep 01 2013
a(n) = (1/3) * Sum_{k=2^n..2^(n+1)} k. - J. M. Bergot, Jan 26 2015
a(n+1) = 2*a(n) + 4^n. - Yuchun Ji, Mar 10 2017

A016269 Number of monotone Boolean functions of n variables with 2 mincuts. Also number of Sperner systems with 2 blocks.

Original entry on oeis.org

1, 9, 55, 285, 1351, 6069, 26335, 111645, 465751, 1921029, 7859215, 31964205, 129442951, 522538389, 2104469695, 8460859965, 33972448951, 136276954149, 546269553775, 2188563950925, 8764714059751, 35090233104309, 140455067207455, 562102681589085, 2249257981411351

Offset: 0

N. J. A. Sloane

Half the number of 2 X (n+2) binary arrays with both a path of adjacent 1's and a path of adjacent 0's from top row to bottom row. - R. H. Hardin, Mar 21 2002
As (0,0,1,9,55,...) this is the third binomial transform of cosh(x)-1. It is the binomial transform of A000392, when this has two leading zeros. Its e.g.f. is then exp(3x)cosh(x) - exp(3x) and a(n) = (4^n - 2*3^n + 2^n)/2. - Paul Barry, May 13 2003
Let P(A) be the power set of an n-element set A. Then a(n-2) is the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x. - Ross La Haye, Jan 10 2008
a(n) also gives the third column sequence of the Sheffer triangle A143494 (2-restricted Stirling2 numbers). See the e.g.f. given below, and comments on the general case under A193685. - Wolfdieter Lang, Oct 08 2011
a(n) is also the number of even binomial coefficients in rows 0 through 2^(n+1)-1 of Pascal's triangle. - Aaron Meyerowitz, Oct 29 2013

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 292, #8, s(n,2).

G. C. Greubel, Table of n, a(n) for n = 0..1000
K. S. Brown, Dedekind's problem
John Elias, Illustration of Initial Terms: Inverse of the Sierpinski Triangle
Vladeta Jovovic, Illustration for A016269, A047707, A051112-A051118
Goran Kilibarda and Vladeta Jovovic, Antichains of Multisets, J. Integer Seqs., Vol. 7, 2004.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
N. M. Rivière, Recursive formulas on free distributive lattices, J. Combinatorial Theory 5 1968 229--234. MR0231764 (38 #92). - _N. J. A. Sloane_, May 12 2012
Index entries for sequences related to Boolean functions
Index entries for linear recurrences with constant coefficients, signature (9,-26,24).

Equals (1/2) A038721(n+1). First differences of A000453. Partial sums of A027650. Pairwise sums of A099110. Odd part of A019333.

Cf. A000079, A000392, A001047, A006516, A032263, A143494, A193685.

[(2^n)*(2^n-1)/2-3^n+2^n: n in [2..30]]; // Vincenzo Librandi, Oct 06 2017

a:= n-> Stirling2(n+4, 4)-Stirling2(n+3, 4): seq(a(n), n=0..24); # Zerinvary Lajos, Oct 05 2007

CoefficientList[1/((1-2x)(1-3x)(1-4x)) + O[x]^30, x] (* Jean-François Alcover, Nov 28 2015 *)
LinearRecurrence[{9, -26, 24}, {1, 9, 55}, 40] (* Vincenzo Librandi, Oct 06 2017 *)

a(n)=(2^n)*(2^n-1)/2-3^n+2^n \\ Charles R Greathouse IV, Mar 22 2016

G.f.: 1/((1-2*x)*(1-3*x)*(1-4*x)).
a(n-2) = (2^n)*(2^n - 1)/2 - 3^n + 2^n.
From Hieronymus Fischer, Jun 25 2007: (Start)
a(n) = Sum_{0<=i,j,k,<=n, i+j+k=n} 2^i*3^j*4^k.
a(n) = 2^(n+1)*(1+2^(n+2))-3^(n+2). (End)
a(n) = 3*StirlingS2(n+3,4) + StirlingS2(n+3,3). - Ross La Haye, Jan 10 2008
If we define f(m,j,x) = Sum_{k=j..m} binomial(m,k)*Stirling2(k,j)*x^(m-k) then a(n-2) = f(n,2,2), (n >= 2). - Milan Janjic, Apr 26 2009
E.g.f.: (d^2/dx^2) (exp(2*x)*((exp(x)-1)^2)/2!). See the Sheffer comment given above. - Wolfdieter Lang, Oct 08 2011
a(n) = A006516(n+2) - A001047(n+2). - Ross La Haye, Jan 26 2016
a(n) = A006516(n+1) + 3*a(n-1), n>=1, a(0)=1. - Carlos A. Rico A., Jun 22 2019

A036239 Number of 2-element intersecting families of an n-element set; number of 2-way interactions when 2 subsets of power set on {1..n} are chosen at random.

Original entry on oeis.org

0, 2, 15, 80, 375, 1652, 7035, 29360, 120975, 494252, 2007555, 8120840, 32753175, 131818052, 529680075, 2125927520, 8525298975, 34165897052, 136857560595, 548011897400, 2193792030375, 8780400395252, 35137296305115, 140596265198480

Offset: 1

N. J. A. Sloane

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 1) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x. - Ross La Haye, Jan 10 2008

Graph theory formulation. Let P(A) be the power set of an n-element set A. Then a(n) = the number of edges in the intersection graph G of P(A). The vertices of G are the elements of P(A) and the edges of G are the pairs of elements {x,y} of P(A) such that x and y are intersecting (and x <> y). - Ross La Haye, Dec 23 2017

W. W. Kokko, "Interactions", manuscript, 1983.

T. D. Noe, Table of n, a(n) for n = 1..200
Taylor Brysiewicz, Holger Eble, and Lukas Kühne, Enumerating chambers of hyperplane arrangements with symmetry, arXiv:2105.14542 [math.CO], 2021.
V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, in Russian, Diskretnaya Matematika, 11 (1999), no. 4, 127-138.
V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, English translation, in Discrete Mathematics and Applications, 9, (1999), no. 6.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).
Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Cf. A036240, A051180-A051185, A028243, A032263.

Cf. A003462, A006516, A016127, A016129, A016130, A016311, A016316, A016321, A016325. - Zerinvary Lajos, Jun 05 2009

LinearRecurrence[{10,-35,50,-24},{0,2,15,80},40] (* or *) With[{c=1/2!}, Table[ c(4^n-3^n-2^n+1),{n,40}]] (* Harvey P. Dale, May 11 2011 *)

a(n)=(4^n-3^n-2^n+1)/2 \\ Charles R Greathouse IV, Jul 25 2011

[(4^n - 2^n)/2-(3^n - 1)/2 for n in range(1,24)] # Zerinvary Lajos, Jun 05 2009

a(n) = (1/2) * (4^n - 3^n - 2^n + 1).
a(n) = 3*Stirling2(n+1,4) + 2*Stirling2(n+1,3). - Ross La Haye, Jan 10 2008
a(n) = A006516(n) - A003462(n). - Zerinvary Lajos, Jun 05 2009
From Harvey P. Dale, May 11 2011: (Start)
a(n) = 10*a(n-1) - 35*a(n-2) + 50*a(n-3) - 24*a(n-4); a(0)=0, a(1)=2, a(2)=15, a(3)=80.
G.f.: x^2*(2-5*x)/(1 - 10*x + 35*x^2 - 50*x^3 + 24*x^4). (End)
E.g.f.: exp(x)*(exp(x) - 1)^2*(exp(x) + 1)/2. - Stefano Spezia, Jun 26 2022

A037952 a(n) = binomial(n, floor((n-1)/2)).

Original entry on oeis.org

0, 1, 1, 3, 4, 10, 15, 35, 56, 126, 210, 462, 792, 1716, 3003, 6435, 11440, 24310, 43758, 92378, 167960, 352716, 646646, 1352078, 2496144, 5200300, 9657700, 20058300, 37442160, 77558760, 145422675, 300540195, 565722720, 1166803110, 2203961430, 4537567650

Offset: 0

N. J. A. Sloane

nonn

First differences of central binomial coefficients: a(n) = A001405(n+1) - A001405(n).
The maximum size of an intersecting (or proper) antichain on an n-set. - Vladeta Jovovic, Dec 27 2000
Number of ordered trees with n+1 edges, having root of degree at least 2 and nonroot nodes of outdegree 0 or 2. - Emeric Deutsch, Aug 02 2002
a(n)=number of Dyck (n+1)-paths that are symmetric but not prime. A prime Dyck path is one that returns to the x-axis only at its terminal point. For example a(3)=3 counts UDUUDDUD, UUDDUUDD, UDUDUDUD. - David Callan, Dec 09 2004
Number of involutions of [n+2] containing the pattern 132 exactly once. For example, a(3)=3 because we have 1'3'2'45, 42'5'13' and 52'4'3'1 (the entries corresponding to the pattern 132 are "primed"). - Emeric Deutsch, Nov 17 2005
Also number of ways to put n eggs in floor(n/2) baskets where order of the baskets matters and all baskets have at least 1 egg. - Ben Paul Thurston, Sep 30 2006
For n >= 1 the number of standard Young tableaux with shapes corresponding to partitions into at most 2 distinct parts. - Joerg Arndt, Oct 25 2012
It seems that 3, 4, 10, ... are Colbourn's Covering Array Numbers CAN(2,k,2). - Ryan Dougherty, May 27 2015
Essentially the same as A007007. - Georg Fischer, Oct 02 2018
a(n) is the number of subsets of {1,2,...,n} that contain exactly 1 more odd than even elements.  For example, for n = 6, a(6) = 15 and the 15 sets are {1}, {3}, {5}, {1,2,3}, {1,2,5}, {1,3,4}, {1,3,6}, {1,4,5}, {1,5,6}, {2,3,5}, {3,4,5}, {3,5,6}, {1,2,3,4,5}, {1,2,3,5,6}, {1,3,4,5,6}. - Enrique Navarrete, Dec 21 2019
a(n) is the number of lattice paths of n steps taken from the step set {U=(1,1), D=(1,-1)} that start at the origin, never go below the x-axis, and end strictly above the x-axis; more succinctly, proper left factors of Dyck paths. For example, a(3)=3 counts UUU, UUD, UDU, and a(4)=4 counts UUUU, UUUD, UUDU, UDUU. - David Callan and Emeric Deutsch, Jan 25 2021
For n >= 3, a(n) is also the number of pinnacle sets in the (n-2)-Plummer-Toft graph. - Eric W. Weisstein, Sep 11 2024

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Cyril Banderier and Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017.
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Dyck Paths with catastrophes modulo the positions of a given pattern, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.
Jean-Luc Baril and José L. Ramírez, Fibonacci and Catalan paths in a wall, 2023.
Paul Barry, d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths, arXiv:2505.16718 [math.CO], 2025. See p. 25.
C. J. Colbourn, Table of CAN(2, k, 2)
Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees and branch lengths, Discrete Math., 282, 2004, 89-94.
O. Guibert and T. Mansour, Restricted 132-involutions, Sem. Lotharingien de Combinatoire, 48, 2002, Article B48a (Corollary 4.2).
M. Miyakawa, A. Nozaki, G. Pogosyan, and I. G. Rosenberg, A map from the lower-half of the n-Cube onto the (n-1)-Cube which preserves intersecting antichains, Discr. Appl. Math. 92 (2-3) (1999) 223-228.
M. van de Vel, Determination of msd(L^n), J. Algebraic Combin., 9 (1999), 161-171.
Eric Weisstein's World of Mathematics, Pinnacle Set.
Eric Weisstein's World of Mathematics, Plummer-Toft Graph.

Cf. A007007, A032263, A014495 (partial sums), A001405 (partial sums + 1).
Cf. A035951, A035953, A035954, A035955, A035956, A035957.
Cf. A051303, A051304, A051305, A051306, A051307.
Cf. A047171, A036256, A051920.
Cf. A265848.

a037952 n = a037952_list !! n
a037952_list = zipWith (-) (tail a001405_list) a001405_list
-- Reinhard Zumkeller, Mar 04 2012

[Binomial(n, Floor((n-1)/2)): n in [0..40]]; // G. C. Greubel, Jun 21 2022

a:= n-> binomial(n, floor((n-1)/2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 19 2017

Table[ Binomial[n, Floor[n/2]], {n, 0, 35}]//Differences (* Jean-François Alcover, Jun 10 2013 *)
f[n_] := Binomial[n, Floor[(n-1)/2]]; Array[f, 35, 0] (* Robert G. Wilson v, Nov 13 2014 *)

a(n) = binomial(n, (n-1)\2); \\ Altug Alkan, Oct 03 2018

[binomial(n, (n-1)//2) for n in (0..40)] # G. C. Greubel, Jun 21 2022

E.g.f.: BesselI(1, 2*x) + BesselI(2, 2*x). - Vladeta Jovovic, Apr 28 2003
O.g.f.: (1-sqrt(1-4x^2))/(x - 2x^2 + x*sqrt(1-4x^2)).
Convolution of A001405 and A126120 shifted right: g001405(x)*g126120(x) = g037952(x)/x. - Philippe Deléham, Mar 17 2007
D-finite with recurrence: (n+2)*a(n) + (-n-2)*a(n-1) + 2*(-2*n+1)*a(n-2) + 4*(n-2)*a(n-3) = 0. - R. J. Mathar, Jan 25 2013. Proved by Robert Israel, Nov 13 2014
For n > 0: a(n) = A265848(n,0). - Reinhard Zumkeller, Dec 24 2015
a(n) = binomial(n, (n-2)/2) = A001791(n/2), n even; a(n) = binomial(n, (n+1)/2) = A001700((n-1)/2), n odd. - Enrique Navarrete, Dec 21 2019
From R. J. Mathar, Sep 23 2021: (Start)
A001405(n) = a(n) + A000108(n/2), where A(.)=0 for non-integer arguments.
a(n) = Sum_{m=1..n} A053121(n,m) [comment Callan-Deutsch].
a(2n+1) = A000984(n+1)/2. (End)
a(n) = Sum_{k=2..n} A143359(n,k). [Callan's 2004 comment]. - R. J. Mathar, Sep 24 2021
From Amiram Eldar, Sep 27 2024: (Start)
Sum_{n>=1} 1/a(n) = 1 + Pi/sqrt(3).
Sum_{n>=1} (-1)^(n+1)/a(n) = (3 - Pi/sqrt(3))/9. (End)

A028244 a(n) = 4^(n-1) - 33^(n-1) + 32^(n-1) - 1 (essentially Stirling numbers of second kind).

Original entry on oeis.org

0, 0, 0, 6, 60, 390, 2100, 10206, 46620, 204630, 874500, 3669006, 15195180, 62350470, 254135700, 1030793406, 4166023740, 16792841910, 67558001700, 271392695406, 1089054420300, 4366671742950, 17498055448500, 70086339807006

Offset: 1

N. J. A. Sloane, Doug McKenzie (mckfam4(AT)aol.com)

For n>=4, a(n) is equal to the number of functions f: {1,2,...,n-1}->{1,2,3,4} such that Im(f) contains 3 fixed elements. - Aleksandar M. Janjic and Milan Janjic, Feb 27 2007

Seiichi Manyama, Table of n, a(n) for n = 1..1661
K. S. Immink, Coding Schemes for Multi-Level Channels that are Intrinsically Resistant Against Unknown Gain and/or Offset Using Reference Symbols, Electronics Letters ( Volume: 50, Issue: 1, January 2 2014 ).
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Index entries for linear recurrences with constant coefficients, signature (10, -35, 50, -24).

Cf. A000453, A008277, A032263, A163626.

[4^(n-1) - 3*3^(n-1) + 3*2^(n-1) - 1: n in [1..30]]; // G. C. Greubel, Nov 19 2017

Table[4^(n - 1) - 3*3^(n - 1) + 3*2^(n - 1) - 1, {n, 1, 30}] (* Stefan Steinerberger, Apr 13 2006 *)
Table[6*StirlingS2[n,4], {n,1,30}] (* G. C. Greubel, Nov 19 2017 *)

for(n=1,30, print1(6*stirling(n,4,2), ", ")) \\ G. C. Greubel, Nov 19 2017

a(n) = 6*S(n, 4) = 6*A000453(n). - Emeric Deutsch, May 02 2004
G.f.: 6x^4/((1-x)(1-2x)(1-3x)(1-4x)). - R. J. Mathar, Oct 23 2008
E.g.f.: (exp(4*x) - 4*exp(3*x) + 6*exp(2*x) - 4*exp(x) + 1)/4, with a(0) = 0. - Wolfdieter Lang, May 03 2017
a(n) = 2*A032263(n). - Alois P. Heinz, Jan 24 2018

A084869 Number of 2-multiantichains of an n-set.

Original entry on oeis.org

1, 2, 5, 17, 71, 317, 1415, 6197, 26591, 112157, 466775, 1923077, 7863311, 31972397, 129459335, 522571157, 2104535231, 8460991037, 33972711095, 136277478437, 546270602351, 2188566048077, 8764718254055, 35090241492917

Offset: 0

Goran Kilibarda, Vladeta Jovovic, Jun 10 2003

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 2) x = y. - Ross La Haye, Jan 11 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Goran Kilibarda and Vladeta Jovovic, Antichains of Multisets, J. Integer Seqs., Vol. 7, 2004.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Index entries for linear recurrences with constant coefficients, signature (9,-26,24).

Cf. A000079, A000217, A000392, A016269, A032263, A034472, A047707, A051112-A051118, A084870-A084883.

Table[2^(2*n-1) - 3^n + 3*2^(n-1), {n, 0, 20}] (* Vaclav Kotesovec, Oct 30 2015 *)

a(n) = 2^(2*n-1)-3^n+3*2^(n-1); \\ Altug Alkan, Sep 12 2017

a(n) = (1/2!)*(4^n - 2*3^n + 3*2^n).
a(n) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,3) + StirlingS2(n+1,2) + 1. - Ross La Haye, Jan 11 2008
G.f.: -(13*x^2-7*x+1) / ((2*x-1)*(3*x-1)*(4*x-1)). - Colin Barker, Nov 27 2012
a(n) = 9*a(n-1) - 26*a(n-2) + 24*a(n-3). - Vaclav Kotesovec, Oct 30 2015
a(n) = 2^(2n-1) + 2^n + 2^(n-1) - 3^n = A000217(2^n+1) - A034472(n), for n >= 1. - Bob Selcoe, Sep 12 2017

A134057 a(n) = binomial(2^n-1,2).

Original entry on oeis.org

0, 0, 3, 21, 105, 465, 1953, 8001, 32385, 130305, 522753, 2094081, 8382465, 33542145, 134193153, 536821761, 2147385345, 8589737985, 34359345153, 137438167041, 549754241025, 2199020109825, 8796086730753, 35184359505921

Offset: 0

Ross La Haye, Jan 11 2008, Jun 01 2008

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x.
Or: Number of connections between the nodes of the perfect depth n binary tree and the nodes of a perfect depth (n-1) binary tree. - Alex Ratushnyak, Jun 02 2013
a(n) is the number of positive entries in the positive rows and columns of a Walsh matrix of order 2^n. It is also the size of the smallest nontrivial conjugacy class in the general linear group GL(n,2). See the link "3-bit Walsh permutation...". - Tilman Piesk, Sep 15 2022

			a(2) = 3 because for P(A) = {{},{1},{2},{1,2}} we have for case 0 {{1},{2}} and we have for case 2 {{1},{1,2}}, {{2},{1,2}}. There are 0 {x,y} of P(A) in this example that fall under case 1.

Robert Israel, Table of n, a(n) for n = 0..1600
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6. - _Ross La Haye_, Feb 22 2009
Tilman Piesk, 3-bit Walsh permutation; conjugacy class 2+2 (Wikiversity)
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A000217, A000225, A000392, A032263, A028243, A171477.

[Binomial(2^n-1, 2): n in [0..30]]; // Vincenzo Librandi, Nov 30 2015

seq((2^n-1)*(2^(n-1)-1), n=0..100); # Robert Israel, Nov 30 2015

Table[Binomial[2^n - 1, 2], {n, 0, 30}] (* Vincenzo Librandi, Nov 30 2015 *)

a(n) = binomial(2^n-1, 2); \\ Michel Marcus, Nov 30 2015

print([(2**n-1)*(2**(n-1)-1) for n in range(23)])
# Alex Ratushnyak, Jun 02 2013

a(n) = (1/2)*(4^n - 3*2^n + 2) = 3*(Stirling2(n+1,4) + Stirling2(n+1,3)).
a(n) = 3 *A006095(n).
a(n) = (2^n-1)*(2^(n-1)-1). - Alex Ratushnyak, Jun 02 2013
a(n) = Stirling2(2^n - 1,2^n - 2).
G.f.: 3*x^2/(1-x)/(1-2*x)/(1-4*x). - Colin Barker, Feb 22 2012
a(n) = A000225(n)*A000225(n-1). - Michel Marcus, Nov 30 2015
a(n) = A000217(2^n-2). - Michel Marcus, Nov 30 2015
a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3). - Wesley Ivan Hurt, May 17 2021
E.g.f.: exp(x)*(exp(x) - 1)^2*(exp(x) + 2)/2. - Stefano Spezia, Apr 06 2022

A053154 Number of 2-element intersecting families (with not necessarily distinct sets) of an n-element set.

Original entry on oeis.org

0, 1, 5, 22, 95, 406, 1715, 7162, 29615, 121486, 495275, 2009602, 8124935, 32761366, 131834435, 529712842, 2125993055, 8525430046, 34166159195, 136858084882, 548012945975, 2193794127526, 8780404589555, 35137304693722

Offset: 0

Vladeta Jovovic, Goran Kilibarda, Feb 28 2000

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x. - Ross La Haye, Jan 11 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, in Russian, Diskretnaya Matematika, 11 (1999), no. 4, 127-138.
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, English translation, in Discrete Mathematics and Applications, 9, (1999), no. 6.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Cf. A036239, A083324.

Cf. A000225, A032263, A028243.

[(4^n-3^n+2^n-1)/2: n in [0..30]]; // Vincenzo Librandi, Oct 06 2017

Table[(4^n-3^n+2^n-1)/2, {n,1,30}] (* Clark Kimberling, Mar 12 2012 *)
CoefficientList[Series[x (1 - 5 x + 7 x^2) / ((1 - x) (1 - 4 x) (1 - 3 x) (1 - 2 x)), {x, 0, 33}], x] (* Vincenzo Librandi, Oct 06 2017 *)

a(n) = (4^n-3^n+2^n-1)/2; \\ Michel Marcus, Nov 30 2015

a(n) = (A083324(n) - 1)/2.
a(n) = (4^n - 3^n + 2^n - 1)/2.
a(n) = 3*StirlingS2(n+1,4) + 2*StirlingS2(n+1,3) + StirlingS2(n+1,2). - Ross La Haye, Jan 11 2008
From Wolfdieter Lang, Oct 28 2011 (Start)
E.g.f.: Sum_{j=1..4} ((-1)^j*exp(j*x))/2  = exp(x)*(exp(4*x)-1)/(exp(x)+1)/2.
O.g.f.: Sum_{j=1..4} (((-1)^j)/(1-j*x))/2 = x*(1-5*x+7*x^2)/product(1-j*x,j=1..4). See A196847.
(End)
G.f.: x*(1-5*x+7*x^2)/((1-x)*(1-4*x)*(1-3*x)*(1-2*x)). - Vincenzo Librandi, Oct 06 2017

A134169 a(n) = 2^(n-1)*(2^n - 1) + 1.

Original entry on oeis.org

1, 2, 7, 29, 121, 497, 2017, 8129, 32641, 130817, 523777, 2096129, 8386561, 33550337, 134209537, 536854529, 2147450881, 8589869057, 34359607297, 137438691329, 549755289601, 2199022206977, 8796090925057, 35184367894529

Offset: 0

Ross La Haye, Jan 12 2008

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either (Case 0) x and y are disjoint, x is not a subset of y, and y is not a subset of x; or (Case 1) x and y are intersecting, but x is not a subset of y, and y is not a subset of x; or (Case 2) x and y are intersecting, and either x is a proper subset of y, or y is a proper subset of x; or (Case 3) x = y.

			a(2) = 7 because for P(A) = {{},{1},{2},{1,2}} we have for Case 0 {{1},{2}}; we have for Case 2 {{1},{1,2}}, {{2},{1,2}}; and we have for Case 3 {{},{}}, {{1},{1}}, {{2},{2}}, {{1,2},{1,2}}. There are 0 {x,y} of P(A) in this example that fall under Case 1.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A000392, A032263, A028243, A000079, A006516.

Table[EulerE[2,2^n],{n,0,60}]/2+1 (* Vladimir Joseph Stephan Orlovsky, Nov 03 2009 *)
LinearRecurrence[{7,-14,8},{1,2,7},30] (* Harvey P. Dale, Mar 12 2013 *)

a(n) = 2^(n-1)*(2^n - 1) + 1.
a(n) = StirlingS2(2^n,2^n - 1) + 1 = C(2^n,2) + 1 = A006516(n) + 1.
From R. J. Mathar, Feb 15 2010: (Start)
a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3).
G.f.: (1 - 5*x + 7*x^2)/((1-x) * (2*x-1) * (4*x-1)). (End)

More terms from Vladimir Joseph Stephan Orlovsky, Nov 03 2009

Edited by N. J. A. Sloane, Jan 25 2015 at the suggestion of Michel Marcus

A051303 Number of 3-element proper antichains of an n-element set.

Original entry on oeis.org

0, 0, 0, 1, 30, 605, 9030, 110901, 1200150, 11932285, 111885510, 1006471301, 8786447670, 75039565965, 630534185190, 5234341175701, 43059373189590, 351805681631645, 2859550165976070, 23152657123816101, 186907026783617910, 1505512392025329325

Offset: 0

Vladeta Jovovic, Goran Kilibarda, Zoran Maksimovic

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (29,-343,2135,-7504,14756,-14832,5760).

Cf. A032263, A036239, A051112.

[(8^n - 9*6^n + 15*5^n - 4*4^n - 9*3^n + 8*2^n - 2) / Factorial(3) : n in [0..25]]; // G. C. Greubel, Oct 06 2017

A051303:=n->(8^n -9*6^n +15*5^n -4*4^n -9*3^n +8*2^n -2)/3!: seq(A051303(n), n=0..30); # Wesley Ivan Hurt, Oct 06 2017

Table[(8^n -9*6^n +15*5^n -4*4^n -9*3^n +8*2^n -2)/3!, {n,0,25}] (* G. C. Greubel, Oct 06 2017 *)

for(n=0,25, print1((8^n -9*6^n +15*5^n -4*4^n -9*3^n +8*2^n -2 )/3!, ", ")) \\ G. C. Greubel, Oct 06 2017

a(n) = (8^n -9*6^n +15*5^n -4*4^n -9*3^n +8*2^n -2)/3!.
G.f.: x^3*(360*x^3-78*x^2-x-1) / ((x-1)*(2*x-1)*(3*x-1)*(4*x-1)*(5*x-1)*(6*x-1)*(8*x-1)). - Colin Barker, Nov 27 2012
a(n) = 29*a(n-1) - 343*a(n-2) + 2135*a(n-3) - 7504*a(n-4) + 14756*a(n-5) - 14832*a(n-6) + 5760*a(n-7) for n > 6. - Wesley Ivan Hurt, Oct 06 2017
E.g.f.: exp(x)*(exp(x) - 1)^3*(2 - 2*exp(x) - 3*exp(2*x) + 3*exp(3*x) + exp(4*x))/6. - Stefano Spezia, Sep 28 2024

cp's OEIS Frontend

A007582 a(n) = 2^(n-1)*(1+2^n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

PARI

Formula

A016269 Number of monotone Boolean functions of n variables with 2 mincuts. Also number of Sperner systems with 2 blocks.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A036239 Number of 2-element intersecting families of an n-element set; number of 2-way interactions when 2 subsets of power set on {1..n} are chosen at random.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A037952 a(n) = binomial(n, floor((n-1)/2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

A028244 a(n) = 4^(n-1) - 3*3^(n-1) + 3*2^(n-1) - 1 (essentially Stirling numbers of second kind).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A084869 Number of 2-multiantichains of an n-set.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A028244 a(n) = 4^(n-1) - 33^(n-1) + 32^(n-1) - 1 (essentially Stirling numbers of second kind).