| Displaying 1-8 of 8 results found.
page
1
Number of partitions of an n-set with an odd number of blocks of size 1.
+10
9
1, 0, 4, 4, 31, 86, 449, 1968, 10420, 56582, 333235, 2069772, 13606113, 94065232, 682242552, 5175100432, 40954340995, 337362555010, 2886922399649, 25616738519384, 235313456176512, 2234350827008170, 21899832049913999, 221292603495494488, 2302631998398438321
FORMULA
E.g.f.: sinh(x)*exp(exp(x)-1-x).
More generally, e.g.f. for number of partitions of an n-set with an odd number of blocks of size k is sinh(x^k/k!)*exp(exp(x)-1-x^k/k!).
MAPLE
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, 0):
MATHEMATICA
Rest[ Range[0, 23]! CoefficientList[ Series[ Sinh[x]Exp[Exp[x] - 1 - x], {x, 0, 23}], x]] (* Robert G. Wilson v *)
PROG
(Python)
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, 0)
Number of permutations of n elements with an even number of fixed points.
+10
7
1, 0, 2, 2, 16, 64, 416, 2848, 22912, 205952, 2060032, 22659328, 271913984, 3534877696, 49488295936, 742324422656, 11877190795264, 201912243453952, 3634420382302208, 69053987263479808, 1381079745270120448, 29002674650671480832, 638058842314774675456
COMMENTS
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...
FORMULA
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
MATHEMATICA
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 *)
PROG
(PARI) 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
AUTHOR
Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 04 2001
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).
+10
7
1, 0, 3, 6, 49, 300, 2491, 22890, 239457, 2782584, 35595091, 496577070, 7499663953, 121855323876, 2118793593099, 39245026343250, 771255810671041, 16025261292247920, 350956070419872547, 8078570913162379734, 194969375055353840241, 4922311437793379501340
FORMULA
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
MAPLE
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):
MATHEMATICA
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 *)
PROG
(Python)
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)
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.
+10
7
0, 1, 0, 7, 24, 201, 1560, 14743, 154896, 1813969, 23346000, 327496071, 4970498280, 81121077337, 1416223931304, 26328776843671, 519178407998880, 10821355158998433, 237677397895531296, 5485802780426178439, 132728552830731814200, 3358841601972480225001
FORMULA
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
MAPLE
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):
MATHEMATICA
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 *)
PROG
(Python)
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)
Number of partitions of 2n-set in which number of blocks of size k is even (or zero) for every k.
+10
7
1, 1, 4, 56, 631, 15457, 582374, 18589286, 894499204, 51154344582, 3823359163826, 274722100927166, 25458967562911128, 2569179797929092506, 284554990016509385086, 37830153187190688287522, 5093072752898942262610007, 798814778335473578083666573
FORMULA
E.g.f.: Product_{k>0} cosh(x^k/k!).
EXAMPLE
a(2)=4 because we have ab|cd, ac|bd, ad|bc and a|b|c|d.
MAPLE
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):
MATHEMATICA
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 *)
Number of partitions of n-set in which number of blocks of size k is odd (or zero) for every k.
+10
5
1, 1, 1, 5, 5, 27, 117, 331, 1213, 6579, 47193, 140527, 1213841, 4617927, 48210879, 243443739, 2392565149, 10377087115, 125434781845, 725455816883, 8086277450629, 59694530600595, 614469256831895, 4650128350629285
FORMULA
E.g.f.: Product_{k>0} (1+sinh(x^k/k!)).
EXAMPLE
a(4)=5 because we have abcd, a|bcd, acd|b, abd|c and abc|d.
MAPLE
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):
MATHEMATICA
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 *)
Number of compositions of n with an even number of 1's.
+10
3
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
COMMENTS
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
FORMULA
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
EXAMPLE
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).
MAPLE
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
MATHEMATICA
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 *)
PROG
(PARI) a(n) = n-=2; (n==-2) + 1<<n + if(n>=0, (-1)^n << (n>>1)); \\ Kevin Ryde, May 02 2023
CROSSREFS
Cf. A063376, A006516, A063083, A100818, A092295, A111752, A111753, A111723, A111724, A088336, A088506.
EXTENSIONS
a(0)=1 prepended and formulas corrected by Jason Yuen, Sep 09 2024
Number of compositions of n with an odd number of 1's.
+10
1
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
FORMULA
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.: 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
EXAMPLE
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).
MAPLE
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
MATHEMATICA
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 *)
CROSSREFS
Cf. A020522, A007582, A063083, A100818, A092295, A111752, A111753, A111723, A111724, A088336, A088506.
Search completed in 0.010 seconds
| 