A111723 -id:A111723 - cp's OEIS frontend

A111724 Number of partitions of an n-set with an even number of blocks of size 1.

0, 2, 1, 11, 21, 117, 428, 2172, 10727, 59393, 345335, 2143825, 14038324, 96834090, 700715993, 5305041715, 41910528809, 344714251149, 2945819805408, 26107419715988, 239556359980239, 2272364911439153, 22252173805170347, 224666265799310801, 2335958333831561032

Offset: 1

Vladeta Jovovic, Nov 17 2005

Alois P. Heinz, Table of n, a(n) for n = 1..576

Cf. A097514, A113235, A063083, A062282, A111723, A111752, A111753.

b:= proc(n, t) option remember; `if`(n=0, t, add(b(n-j,
      `if`(j=1, 1-t, t))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=1..30);  # Alois P. Heinz, May 10 2016

Rest[ Range[0, 24]! CoefficientList[ Series[ Cosh[x]Exp[Exp[x] - 1 - x], {x, 0, 23}], x]] (* Robert G. Wilson v *)

from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def b(n, t): return t if n==0 else sum(b(n - j, (1 - t if j==1 else t))*binomial(n - 1, j - 1) for j in range(1, n + 1))
def a(n): return b(n, 1)
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Aug 10 2017

E.g.f.: cosh(x)*exp(exp(x)-1-x).

More generally, e.g.f. for number of partitions of an n-set with an even number of blocks of size k is cosh(x^k/k!)*exp(exp(x)-1-x^k/k!).

More terms from Robert G. Wilson v, Nov 22 2005

A062282 Number of permutations of n elements with an even number of fixed points.

Original entry on oeis.org

1, 0, 2, 2, 16, 64, 416, 2848, 22912, 205952, 2060032, 22659328, 271913984, 3534877696, 49488295936, 742324422656, 11877190795264, 201912243453952, 3634420382302208, 69053987263479808, 1381079745270120448, 29002674650671480832, 638058842314774675456

Offset: 0

Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 04 2001

nonn

Let d(n) be the number of derangements of n elements (sequence A000166) then a(n) has the recursion: a(n) = d(n) + C(n,2)*d(n-2) + C(n,4)*d(n-4) + C(n,6)*d(n-6)... = A000166(n) + A000387(n) + A000475(n) + C(n,6)*d(n-6)... The E.g.f. for a(n) is: cosh(x) * exp(-x)/(1-x) and the asymptotic expression for a(n) is: a(n) ~ n! * (1 + 1/e^2)/2 i.e., as n goes to infinity the fraction of permutations that has an even number of fixed points is about (1 + 1/e^2)/2 = 0.567667...

G. C. Greubel, Table of n, a(n) for n = 0..445

Cf. A000166, A000387, A000475.

Cf. A063083, A100818, A092295, A111752, A111753, A111723, A111724, A088336, A088506.

nn = 20; d = Exp[-x]/(1 - x); Range[0, nn]! CoefficientList[Series[Cosh[x] d, {x, 0, nn}], x] (* Geoffrey Critzer, Jan 14 2012 *)
Table[Sum[Sum[(-1)^j * n!/(j!*(2*k)!), {j, 0, n - 2*k}], {k, 0, Floor[n/2]}], {n,0,50}] (* G. C. Greubel, Aug 21 2017 *)

for(n=0,50, print1(sum(k=0,n\2, sum(j=0,n-2*k, (-1)^j*n!/(j!*(2*k)!))), ", ")) \\ G. C. Greubel, Aug 21 2017

a(n) = Sum_{k=0..[n/2]} Sum_{l=0..(n-2*k)} (-1)^l * n!/((2*k)! * l!).
More generally, e.g.f. for number of degree-n permutations with an even number of k-cycles is cosh(x^k/k)*exp(-x^k/k)/(1-x). - Vladeta Jovovic, Jan 31 2006
E.g.f.: 1/(1-x)/(x*E(0)+1), where E(k) = 1 - x^2/( x^2 + (2*k+1)*(2*k+3)/E(k+1) ); (continued fraction ). - Sergei N. Gladkovskii, Dec 29 2013
Conjecture: a(n) = Sum_{k=0..n} A008290(n, k)*A059841(k). - John Keith, Jun 30 2020

More terms from Vladeta Jovovic, Jul 05 2001

A111752 Number of partitions of {1,..,n} into lists with an even number of lists of size 1, where a list means an ordered subset (cf. A000262).

Original entry on oeis.org

1, 0, 3, 6, 49, 300, 2491, 22890, 239457, 2782584, 35595091, 496577070, 7499663953, 121855323876, 2118793593099, 39245026343250, 771255810671041, 16025261292247920, 350956070419872547, 8078570913162379734, 194969375055353840241, 4922311437793379501340

Offset: 0

Vladeta Jovovic, Nov 19 2005; corrected Jun 06 2006

a(n) + A111753(n) = A000262(n). - David Wasserman, Feb 11 2009

Alois P. Heinz, Table of n, a(n) for n = 0..444

Cf. A000262, A113235, A063083, A062282, A111723, A111724, A111753.

b:= proc(n, t) option remember; `if`(n=0, t, add(b(n-j,
     `if`(j=1, 1-t, t))*binomial(n-1, j-1)*j!, j=1..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..30);  # Alois P. Heinz, May 10 2016

b[n_, t_] := b[n, t] = If[n == 0, t, Sum[b[n-j, If[j == 1, 1-t, t]] * Binomial[n-1, j-1]*j!, {j, 1, n}]]; a[n_] := b[n, 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 21 2017, after Alois P. Heinz *)

from sympy.core.cache import cacheit
from sympy import binomial, factorial as f
@cacheit
def b(n, t): return t if n==0 else sum(b(n - j, (1 - t if j==1 else t))*binomial(n - 1, j - 1)*f(j) for j in range(1, n + 1))
def a(n): return b(n, 1)
print([a(n) for n in range(51)]) # Indranil Ghosh, Aug 10 2017

E.g.f.: cosh(x)*exp(x^2/(1-x)). More generally, e.g.f. for number of partitions of {1, 2, ...n} into lists with an even number of lists of size k is cosh(x^k)*exp(x/(1-x)-x^k).
E.g.f.: cosh(x)*exp(x^2/(1-x)) = 1/2*Q(0); Q(k) = 1+((2*x-1)^k)/(1-x/(x+((2*x-1)^k)*(k+1)*(1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 17 2011
a(n) ~ (exp(1)+exp(-1)) * 2^(-3/2) * exp(2*sqrt(n)-n-3/2) * n^(n-1/4) * (1 + (2/(1 + exp(2)) - 5/48)/sqrt(n)). - Vaclav Kotesovec, Jan 21 2017, extended Dec 01 2021

More terms from David Wasserman, Feb 11 2009

a(0)=1 prepended by Alois P. Heinz, May 10 2016

A111753 Number of partitions of {1,..,n} into lists with an odd number of lists of size 1, where a list means an ordered subset, cf. A000262.

Original entry on oeis.org

0, 1, 0, 7, 24, 201, 1560, 14743, 154896, 1813969, 23346000, 327496071, 4970498280, 81121077337, 1416223931304, 26328776843671, 519178407998880, 10821355158998433, 237677397895531296, 5485802780426178439, 132728552830731814200, 3358841601972480225001

Offset: 0

Vladeta Jovovic, Nov 19 2005; corrected Jun 06 2006

a(n) + A111752(n) = A000262(n). - David Wasserman, Feb 11 2009

Alois P. Heinz, Table of n, a(n) for n = 0..444

Cf. A113235, A063083, A062282, A111723, A111724, A111752.

b:= proc(n, t) option remember; `if`(n=0, t, add(b(n-j,
     `if`(j=1, 1-t, t))*binomial(n-1, j-1)*j!, j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, May 10 2016

b[n_, t_] := b[n, t] = If[n==0, t, Sum[b[n-j, If[j==1, 1-t, t]]*Binomial[ n-1, j-1]*j!, {j, 1, n}]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 03 2017, after Alois P. Heinz *)

from sympy.core.cache import cacheit
from sympy import binomial, factorial as f
@cacheit
def b(n, t): return t if n==0 else sum([b(n - j, (1 - t if j==1 else t))*binomial(n - 1, j - 1)*f(j) for j in range(1, n + 1)])
def a(n): return b(n, 0)
print([a(n) for n in range(51)]) # Indranil Ghosh, Aug 10 2017

E.g.f.: sinh(x)*exp(x^2/(1-x)). More generally, e.g.f. for number of partitions of {1, 2, ...n} into lists with an odd number of lists of size k is sinh(x^k)*exp(x/(1-x)-x^k).
E.g.f.: sinh(x)*exp(x^2/(1-x))=1/2*Q(0);   Q(k)=1-((2x-1)^k)/( 1-x/(x-((2x-1)^k)*(k+1)*(1-x)/Q(k+1)));  (continued fraction). - Sergei N. Gladkovskii, Nov 17 2011
a(n) ~ (exp(1)-exp(-1)) * 2^(-3/2) * exp(2*sqrt(n)-n-3/2) * n^(n-1/4) * (1 + (43/48 - coth(1))/sqrt(n)). - Vaclav Kotesovec, Dec 01 2021

More terms from David Wasserman, Feb 11 2009

a(0)=0 prepended by Alois P. Heinz, May 10 2016

A130219 Number of partitions of 2n-set in which number of blocks of size k is even (or zero) for every k.

Original entry on oeis.org

1, 1, 4, 56, 631, 15457, 582374, 18589286, 894499204, 51154344582, 3823359163826, 274722100927166, 25458967562911128, 2569179797929092506, 284554990016509385086, 37830153187190688287522, 5093072752898942262610007, 798814778335473578083666573

Offset: 0

Vladeta Jovovic, Aug 04 2007, Aug 05 2007

			a(2)=4 because we have ab|cd, ac|bd, ad|bc and a|b|c|d.

Alois P. Heinz, Table of n, a(n) for n = 0..250

Cf. A055922, A102759, A111723, A111724.

g:=product(cosh(x^k/factorial(k)),k=1..35): gser:=series(g,x=0,32): seq(factorial(2*n)*coeff(gser,x,2*n),n=0..14); # Emeric Deutsch, Sep 01 2007
# second Maple program:
g:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0, add(
     `if`(irem(j, 2)=0, g(n-i*j, i-1, p+j*i)/j!/i!^j, 0), j=0..n/i)))
    end:
a:= n-> g(2*n$2, 0):
seq(a(n), n=0..20);  # Alois P. Heinz, Mar 06 2015

g[n_, i_, p_] := g[n, i, p] = If[n == 0, p!, If[i<1, 0, Sum[If[Mod[j, 2] == 0, g[n - i*j, i-1, p + j*i]/j!/i!^j, 0], {j, 0, n/i}]]]; a[n_] := g[2*n, 2*n, 0]; Table[ a[n], {n, 0, 20}] (* Jean-François Alcover, May 12 2015, after Alois P. Heinz *)

E.g.f.: Product_{k>0} cosh(x^k/k!).

More terms from Emeric Deutsch, Sep 01 2007

A130220 Number of partitions of n-set in which number of blocks of size k is odd (or zero) for every k.

Original entry on oeis.org

1, 1, 1, 5, 5, 27, 117, 331, 1213, 6579, 47193, 140527, 1213841, 4617927, 48210879, 243443739, 2392565149, 10377087115, 125434781845, 725455816883, 8086277450629, 59694530600595, 614469256831895, 4650128350629285, 52385811781286769, 467607504075929863

Offset: 0

Vladeta Jovovic, Aug 04 2007, Aug 05 2007

			a(4)=5 because we have abcd, a|bcd, acd|b, abd|c and abc|d.

Alois P. Heinz, Table of n, a(n) for n = 0..500

Cf. A055922, A102759, A111723, A111724.

g:=product(1+sinh(x^k/factorial(k)),k=1..30): gser:=series(g,x=0,28): seq(factorial(n)*coeff(gser,x,n),n=0..24); # Emeric Deutsch, Sep 01 2007
# second Maple program:
with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(j=0 or irem(j, 2)=1, multinomial(n, n-i*j, i$j)
       /j!*b(n-i*j, i-1), 0), j=0..n/i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 08 2015

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[If[j == 0 || Mod[j, 2] == 1, multinomial[n, Join[{n - i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1], 0], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 11 2015, after Alois P. Heinz *)

E.g.f.: Product_{k>0} (1+sinh(x^k/k!)).

More terms from Emeric Deutsch, Sep 01 2007

A113979 Number of compositions of n with an even number of 1's.

Original entry on oeis.org

1, 0, 2, 1, 6, 6, 20, 28, 72, 120, 272, 496, 1056, 2016, 4160, 8128, 16512, 32640, 65792, 130816, 262656, 523776, 1049600, 2096128, 4196352, 8386560, 16781312, 33550336, 67117056, 134209536, 268451840, 536854528, 1073774592, 2147450880

Offset: 0

Vladeta Jovovic, Jan 31 2006

More generally, the g.f. for the number of compositions such that part m occurs with even multiplicity is (1-x)/(1-2*x)*(1-2*x+x^m-x^(m+1))/(1-2*x+2*x^m-2*x^(m+1)). - Vladeta Jovovic, Sep 01 2007

			a(4)=6 because the compositions of 4 having an even number of 1's are 4,22,211,121,112 and 1111 (the other compositions of 4 are 31 and 13).

Index entries for linear recurrences with constant coefficients, signature (2,2,-4).

Cf. A063376, A006516, A063083, A100818, A092295, A111752, A111753, A111723, A111724, A088336, A088506.

Cf. A105422, A113980.

a:=proc(n) if n mod 2 = 0 then 2^(n-2)+2^((n-2)/2) else 2^(n-2)-2^((n-3)/2) fi end: seq(a(n),n=1..38); # Emeric Deutsch, Feb 01 2006

f[n_] := If[ EvenQ[n], 2^(n - 2) + 2^((n - 2)/2), 2^(n - 2) - 2^((n - 3)/2)]; Array[f, 34] (* Robert G. Wilson v, Feb 01 2006 *)

a(n) = n-=2; (n==-2) + 1<=0, (-1)^n << (n>>1)); \\ Kevin Ryde, May 02 2023

a(0) = 1, a(n) = 2^(n-2) + 2^((n-2)/2) if n is positive and even, otherwise a(n) = 2^(n-2) - 2^((n-3)/2).
G.f.: (1-z)*(1-z-z^2)/((1-2*z)*(1-2*z^2)). - Emeric Deutsch, Feb 03 2006
E.g.f.: (1 + exp(2*x) - sqrt(2)*sinh(x*sqrt(2)) + 2*cosh(x*sqrt(2)))/4. - Sergei N. Gladkovskii, Nov 18 2011
a(k) = (1/4)*0^k + (1/4)*2^k + (1/8)*(2-sqrt(2))*(sqrt(2))^k + (1/8)*(2+sqrt(2))*(-sqrt(2))^k. - Sergei N. Gladkovskii, Nov 18 2011

More terms from Robert G. Wilson v and Emeric Deutsch, Feb 01 2006

a(0)=1 prepended and formulas corrected by Jason Yuen, Sep 09 2024

A113980 Number of compositions of n with an odd number of 1's.

Original entry on oeis.org

1, 0, 3, 2, 10, 12, 36, 56, 136, 240, 528, 992, 2080, 4032, 8256, 16256, 32896, 65280, 131328, 261632, 524800, 1047552, 2098176, 4192256, 8390656, 16773120, 33558528, 67100672, 134225920, 268419072, 536887296, 1073709056, 2147516416

Offset: 1

Vladeta Jovovic, Jan 31 2006

			a(4)=2 because only the compositions 31 and 13 of 4 have an odd number of 1's (the other compositions are 4,22,211,121,112 and 1111).

Index entries for linear recurrences with constant coefficients, signature (2,2,-4).

Cf. A020522, A007582, A063083, A100818, A092295, A111752, A111753, A111723, A111724, A088336, A088506.

Cf. A105422.

a:=proc(n) if n mod 2 = 0 then 2^(n-2)-2^((n-2)/2) else 2^(n-2)+2^((n-3)/2) fi end: seq(a(n),n=1..38); # Emeric Deutsch, Feb 01 2006

f[n_] := If[EvenQ[n], 2^(n - 2) - 2^((n - 2)/2), 2^(n - 2) + 2^((n - 3)/2)]; Array[f, 34] (* Robert G. Wilson v, Feb 01 2006 *)

a(n) = 2^(n-2)-2^((n-2)/2) if n is even, else a(n) = 2^(n-2)+2^((n-3)/2).
G.f.: z(1-z)^2/[(1-2z)(1-2z^2)]. - Emeric Deutsch, Feb 03 2006
G.f.: 1 + x + Q(0), where Q(k)= 1 - 1/(2^k - 2*x*2^(2*k)/(2*x*2^k - 1/(1 + 1/(2*2^k - 8*x*2^(2*k)/(4*x*2^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 22 2013

More terms from Robert G. Wilson v and Emeric Deutsch, Feb 01 2006

cp's OEIS Frontend

A111724 Number of partitions of an n-set with an even number of blocks of size 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A062282 Number of permutations of n elements with an even number of fixed points.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A111752 Number of partitions of {1,..,n} into lists with an even number of lists of size 1, where a list means an ordered subset (cf. A000262).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A111753 Number of partitions of {1,..,n} into lists with an odd number of lists of size 1, where a list means an ordered subset, cf. A000262.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A130219 Number of partitions of 2n-set in which number of blocks of size k is even (or zero) for every k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A130220 Number of partitions of n-set in which number of blocks of size k is odd (or zero) for every k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A113979 Number of compositions of n with an even number of 1's.

Views

Author

Keywords

Comments