Search: a193638 -id:a193638
|
|
A114938
|
|
Number of permutations of the multiset {1,1,2,2,...,n,n} with no two consecutive terms equal.
|
|
+10
24
|
|
|
1, 0, 2, 30, 864, 39480, 2631600, 241133760, 29083420800, 4467125013120, 851371260364800, 197158144895712000, 54528028997584665600, 17752366094818747392000, 6720318485119046923315200, 2927066537906697348594432000, 1453437879238150456164433920000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) is also the number of (0,1)-matrices A=(a_ij) of size n X 2n such that each row has exactly two 1's and each column has exactly one 1 and with the restriction that no 1 stands on the line from a_11 to a_22. - Shanzhen Gao, Feb 24 2010
a(n) is the number of permutations of the multiset {1,1,2,2,...,n,n} with no fixed points. - Alexander Burstein, May 16 2020
Also the number of 2-uniform ordered set partitions of {1...2n} containing no two successive vertices in the same block. - Gus Wiseman, Jul 04 2020
|
|
REFERENCES
|
R. P. Stanley, Enumerative Combinatorics Volume I, Cambridge University Press, 1997. Chapter 2, Sieve Methods, Example 2.2.3, page 68.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=0..n} ((binomial(n, k)*(-1)^(n-k)*(n+k)!)/2^k).
a(n) = (-1)^n * (i/e)*sqrt(2/Pi) * n! * BesselK(n+1/2, -1).
a(n) = [n! * (1/x) * p_{n+1}(x)]|_{x= -1} (See A104548 for p_{n}(x)).
E.g.f.: sqrt(Pi/(2*x)) * exp(-(1+x)^2/(2*x)) * erfi((1+x)/sqrt(2*x)).
Sum_{n >= 0} a(n)*x^n/(n!)^2 = exp(sqrt(1-2*x))/sqrt(1-2*x).
Sum_{n >= 0} a(n)*x^n/(n!*(n+1)!) = ( 1 - exp(-1 + sqrt(1-2*x)) )/x. (End)
|
|
EXAMPLE
|
a(2) = 2 because there are two permutations of {1,1,2,2} avoiding equal consecutive terms: 1212 and 2121.
|
|
MATHEMATICA
|
Table[Sum[Binomial[n, i](2n-i)!/2^(n-i) (-1)^i, {i, 0, n}], {n, 0, 20}] (* Geoffrey Critzer, Jan 02 2013, and adapted to the extension by Stefano Spezia, Nov 15 2018 *)
Table[Length[Select[Permutations[Join[Range[n], Range[n]]], !MatchQ[#, {___, x_, x_, ___}]&]], {n, 0, 5}] (* Gus Wiseman, Jul 04 2020 *)
|
|
PROG
|
(PARI) A114938(n)=sum(k=0, n, binomial(n, k)*(-1)^(n-k)*(n+k)!/2^k);
(Magma) [1] cat [n le 2 select 2*(n-1) else n*(2*n-1)*Self(n-1) + (n-1)*n*Self(n-2): n in [1..20]]; // Vincenzo Librandi, Aug 10 2015
(SageMath)
def A114938(n): return (-1)^n*sum(binomial(n, k)*factorial(n+k)//(-2)^k for k in range(n+1))
|
|
CROSSREFS
|
Cf. A114939 = preferred seating arrangements of n couples.
Cf. A007060 = arrangements of n couples with no adjacent spouses; A007060(n) = 2^n * A114938(n) (this sequence).
Cf. A278990 = number of loopless linear chord diagrams with n chords.
Cf. A000806 = Bessel polynomial y_n(-1).
The version for multisets with prescribed multiplicities is A335125.
The version for prime indices is A335452.
Anti-run compositions are counted by A003242.
Anti-run compositions are ranked by A333489.
Inseparable partitions are counted by A325535.
Inseparable partitions are ranked by A335448.
Separable partitions are counted by A325534.
Separable partitions are ranked by A335433.
Other sequences involving the multiset {1,1,2,2,...,n,n}: A001147, A007717, A020555, A094574, A316972.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A322093
|
|
Square array A(n,k), n >= 1, k >= 1, read by antidiagonals, where A(n,k) is the number of permutations of n copies of 1..k with no element equal to another within a distance of 1.
|
|
+10
13
|
|
|
1, 2, 0, 6, 2, 0, 24, 30, 2, 0, 120, 864, 174, 2, 0, 720, 39480, 41304, 1092, 2, 0, 5040, 2631600, 19606320, 2265024, 7188, 2, 0, 40320, 241133760, 16438575600, 11804626080, 134631576, 48852, 2, 0, 362880, 29083420800, 22278418248240, 131402141197200, 7946203275000, 8437796016, 339720, 2, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
Let q_n(x) = Sum_{i=1..n} (-1)^(n-i) * binomial(n-1, n-i) * x^i/i!.
A(n,k) = Integral_{0..infinity} (q_n(x))^k * exp(-x) dx.
|
|
EXAMPLE
|
Square array begins:
1, 2, 6, 24, 120, 720, ...
0, 2, 30, 864, 39480, 2631600, ...
0, 2, 174, 41304, 19606320, 16438575600, ...
0, 2, 1092, 2265024, 11804626080, 131402141197200, ...
0, 2, 7188, 134631576, 7946203275000, 1210527140790855600, ...
|
|
PROG
|
(PARI)
q(n, x) = sum(i=1, n, (-1)^(n-i) * binomial(n-1, n-i) * x^i/i!)
T(n, k) = subst(serlaplace(q(n, x)^k), x, 1) \\ Andrew Howroyd, Feb 03 2024
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A190826
|
|
Number of permutations of 3 copies of 1..n introduced in order 1..n with no element equal to another within a distance of 1.
|
|
+10
10
|
|
|
1, 0, 1, 29, 1721, 163386, 22831355, 4420321081, 1133879136649, 372419001449076, 152466248712342181, 76134462292157828285, 45552714996556390334921, 32173493282909179882613934, 26487410329744429030530295991, 25143126122564855343240882599761, 27260957330891104469298062949026065
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
LINKS
|
|
|
FORMULA
|
a(n) = A193624(n)/(6^n * n!), for n >= 1.
a(n) = A192990(binomial(n+2,3)) / (6^n * n!), for n >= 1.
2*a(n) -3*(3*n^2-3*n+4)*a(n-1) +2*(9*n^2-42*n+47)*a(n-2) +8*(3*n-7)*a(n-3) -8*a(n-4) = 0. - R. J. Mathar, May 23 2014
a(n) = (1/(6^n * n!)) * Sum_{j=0..2*n} Sum_{k=ceiling(j/2)..n} (n+j)! * binomial(2*k, j) * binomial(n, k) * (-3)^(n+k-j). - Jean-François Alcover, Jul 22 2017
a(n) ~ 3^(2*n + 1/2) * n^(2*n) / (2^n * exp(2*n + 2)). - Vaclav Kotesovec, Nov 24 2018
|
|
EXAMPLE
|
Some of the a(3) = 29 solutions for n=3: 123232131, 123121323, 123123213, 123212313, 123213123, 121323132, 123132312, 123123123, 123231213, 121323123, 121321323, 121312323, 121323231, 123231321, 121313232, 123132321, ...
|
|
MATHEMATICA
|
a[n_]:= 1/(6^n*n!)*Sum[(n+j)! Sum[Binomial[n, k] Binomial[2k, j] (-3)^(n+k-j), {k, Ceiling[j/2], n}], {j, 0, 2n}]; Array[a, 16, 0] (* Jean-François Alcover, Jul 22 2017, after Tani Akinari's code for A193638 *)
|
|
PROG
|
(Magma)
B:=Binomial;
f:= func< n, j | (&+[B(n, k)*B(2*k, j)*(-3)^(k-j): k in [Ceiling(j/2)..n]]) >;
A190826:= func< n | (-1/2)^n*(&+[Factorial(j)*B(n+j, j)*f(n, j): j in [0..2*n]]) >;
(SageMath)
b=binomial;
def f(j, n): return sum(b(n, k)*b(2*k, j)*(-3)^(k-j) for k in range((j//2), n+1))
def A190826(n): return (-1/2)^n*sum(factorial(j)*b(n+j, j)*f(j, n) for j in range(2*n+1))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A321633
|
|
Number of permutations of the multiset {1,1,1,1,2,2,2,2,3,3,3,3,...,n,n,n,n} with no two consecutive terms equal.
|
|
+10
5
|
|
|
1, 0, 2, 1092, 2265024, 11804626080, 131402141197200, 2778291737177034960, 102284730928300590754560, 6134232798447803932455457920, 568598490353320413296928514444800, 78076149156802562231395694989534464000, 15336188146163145199585928509793662920345600
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Integral_{0..oo} (-x + 3/2 * x^2 - 1/2 * x^3 + 1/24 * x^4)^n * exp(-x) dx.
|
|
EXAMPLE
|
a(2) = 2 because there are two permutations of {1,1,1,1,2,2,2,2} avoiding equal consecutive terms: 12121212 and 21212121.
|
|
MATHEMATICA
|
a[n_] := Integrate[(-x + 3/2 * x^2 - 1/2 * x^3 + 1/24 * x^4)^n * Exp[-x], {x, 0, Infinity}]; Array[a, 10, 0] (* Stefano Spezia, Nov 27 2018 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A321634
|
|
Number of arrangements of n 1's, n 2's, ..., n n's avoiding equal consecutive terms.
|
|
+10
3
|
|
|
1, 1, 2, 174, 2265024, 7946203275000, 12229789732207993835280, 12202002913678756821228939869239920, 10937192762438008527903830198163831816546577931520, 11655577382287102750765311537460065620507094071664576111302628243840
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
FORMULA
|
a(n) ~ n^(n^2 - n/2 + 1) / ((2*Pi)^((n-1)/2) * exp(n - 5/12)). - Vaclav Kotesovec, Nov 24 2018
|
|
PROG
|
(PARI) {a(n) = sum(i=n, n^2, i!*polcoef(sum(j=1, n, (-1)^(n-j)*binomial(n-1, j-1)*x^j/j!)^n, i))} \\ Seiichi Manyama, May 27 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.010 seconds
|