Displaying 1-10 of 16 results found.
Number of patterns of length n matching the pattern (1,1,1).
+0
5
0, 0, 0, 1, 9, 91, 993, 12013, 160275, 2347141, 37496163, 649660573, 12142311195, 243626199181, 5224710549243, 119294328993853, 2889836999693355, 74037381200415901, 2000383612949821323, 56850708386783835133, 1695491518035158123115, 52949018580275965241821
COMMENTS
We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).
EXAMPLE
The a(3) = 1 through a(4) = 9 patterns:
(1,1,1) (1,1,1,1)
(1,1,1,2)
(1,1,2,1)
(1,2,1,1)
(1,2,2,2)
(2,1,1,1)
(2,1,2,2)
(2,2,1,2)
(2,2,2,1)
MAPLE
b:= proc(n, k) option remember; `if`(n=0, 1, add(
b(n-i, k)*binomial(n, i), i=1..min(n, k)))
end:
a:= n-> b(n$2)-b(n, 2):
MATHEMATICA
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n], MatchQ[#, {___, x_, ___, x_, ___, x_, ___}]&]], {n, 0, 6}]
CROSSREFS
The complement A080599 is the avoiding version. Permutations of prime indices matching this pattern are counted by A335510. Compositions matching this pattern are counted by A335455 and ranked by A335512. Patterns matching the pattern (1,1) are counted by A019472. Combinatory separations are counted by A269134. Patterns matched by standard compositions are counted by A335454. Minimal patterns avoided by a standard composition are counted by A335465. Patterns matching (1,2,3) are counted by A335515. Cf. A034691, A056986, A232464, A238279, A292884, A333175, A333755, A335451, A335456, A335457, A335458.
Number of permutations of the multiset {1,1,2,2,...,n,n} with no two consecutive terms equal.
+0
24
1, 0, 2, 30, 864, 39480, 2631600, 241133760, 29083420800, 4467125013120, 851371260364800, 197158144895712000, 54528028997584665600, 17752366094818747392000, 6720318485119046923315200, 2927066537906697348594432000, 1453437879238150456164433920000
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.
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.
Number of compositions of n if all summand runs are kept together.
+0
109
1, 1, 2, 4, 7, 12, 22, 36, 60, 97, 162, 254, 406, 628, 974, 1514, 2305, 3492, 5254, 7842, 11598, 17292, 25294, 37090, 53866, 78113, 112224, 161092, 230788, 328352, 466040, 658846, 928132, 1302290, 1821770, 2537156, 3536445, 4897310, 6777806, 9341456, 12858960, 17625970, 24133832, 32910898, 44813228, 60922160, 82569722
COMMENTS
Also the number of compositions of n avoiding the patterns (1,2,1) and (2,1,2). - Gus Wiseman, Jul 07 2020
EXAMPLE
If the summand runs are blocked together, there are 22 compositions of a(6): 6; 5+1, 1+5, 4+2, 2+4, (3+3), 4+(1+1), (1+1)+4, 1+2+3, 1+3+2, 2+1+3, 2+3+1, 3+1+2, 3+2+1, (2+2+2), 3+(1+1+1), (1+1+1)+3, (2+2)+(1+1), (1+1)+(2+2), 2+(1+1+1+1), (1+1+1+1)+2, (1+1+1+1+1+1).
a(0)=1; a(1)= 1; a(4) = 7; a(9) = 97; a(16) = 2305; a(25) = 78113 and a(36) = 3536445. - Gregory L. Simay, Jun 23 19
MAPLE
b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
add(b(n-i*j, i-1, p+`if`(j=0, 0, 1)), j=0..n/i)))
end:
a:= n-> b(n$2, 0):
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[Split[#]]==Length[Union[#]]&]], {n, 0, 10}] (* Gus Wiseman, Jul 07 2020 *) b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i < 1, 0,
Sum[b[n - i*j, i - 1, p + If[j == 0, 0, 1]], {j, 0, n/i}]]];
a[n_] := b[n, n, 0];
CROSSREFS
The version for patterns is A001339. The version for prime indices is A333175. The complement (i.e., the matching version) is A335548. (1,2,1)- and (2,1,2)-matching permutations of prime indices are A335462. (1,2,1)-matching compositions are A335470. (1,2,1)-avoiding compositions are A335471. (2,1,2)-matching compositions are A335472. (2,1,2)-avoiding compositions are A335473.
Number of compositions of n with at least one non-contiguous value.
+0
29
0, 0, 0, 0, 1, 4, 10, 28, 68, 159, 350, 770, 1642, 3468, 7218, 14870, 30463, 62044, 125818, 254302, 512690, 1031284, 2071858, 4157214, 8334742, 16699103, 33442208, 66947772, 133986940, 268107104, 536404872, 1073082978, 2146555516, 4293665006, 8588112822
COMMENTS
Also the number of compositions of n matching the pattern (1,2,1) or (2,1,2).
EXAMPLE
The a(4) = 1 through a(6) = 10 compositions:
(121) (131) (141)
(212) (1131)
(1121) (1212)
(1211) (1221)
(1311)
(2112)
(2121)
(11121)
(11211)
(12111)
MAPLE
b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
add(b(n-i*j, i-1, p+`if`(j=0, 0, 1)), j=0..n/i)))
end:
a:= n-> ceil(2^(n-1))-b(n$2, 0):
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[Split[#]]>Length[Union[#]]&]], {n, 0, 10}]
(* Second program: *)
b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i<1, 0,
Sum[b[n-i*j, i-1, p + If[j == 0, 0, 1]], {j, 0, n/i}]]];
a[n_] := Ceiling[2^(n-1)] - b[n, n, 0];
CROSSREFS
The version for prime indices is A335460. (1,2,1) and (2,1,2)-matching permutations of prime indices are A335462. (1,2,1)-matching compositions are A335470. (1,2,1)-avoiding compositions are A335471. (2,1,2)-matching compositions are A335472. (2,1,2)-avoiding compositions are A335473.
Numbers whose prime indices are inseparable.
+0
106
4, 8, 9, 16, 24, 25, 27, 32, 40, 48, 49, 54, 56, 64, 80, 81, 88, 96, 104, 112, 121, 125, 128, 135, 136, 144, 152, 160, 162, 169, 176, 184, 189, 192, 208, 224, 232, 240, 243, 248, 250, 256, 272, 288, 289, 296, 297, 304, 320, 324, 328, 336, 343, 344, 351, 352
COMMENTS
First differs from A212164 in lacking 72. First differs from A293243 in lacking 72. No terms are squarefree.
Also Heinz numbers of inseparable partitions ( A325535). The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. These are also numbers that can be written as a product of prime numbers, each different from the last but not necessarily different from those prior to the last.
A multiset is inseparable iff its maximal multiplicity is greater than one plus the sum of its remaining multiplicities.
EXAMPLE
The sequence of terms together with their prime indices begins:
4: {1,1}
8: {1,1,1}
9: {2,2}
16: {1,1,1,1}
24: {1,1,1,2}
25: {3,3}
27: {2,2,2}
32: {1,1,1,1,1}
40: {1,1,1,3}
48: {1,1,1,1,2}
49: {4,4}
54: {1,2,2,2}
56: {1,1,1,4}
64: {1,1,1,1,1,1}
80: {1,1,1,1,3}
81: {2,2,2,2}
88: {1,1,1,5}
96: {1,1,1,1,1,2}
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[100], Select[Permutations[primeMS[#]], !MatchQ[#, {___, x_, x_, ___}]&]=={}&]
CROSSREFS
Permutations of prime indices are counted by A008480. Inseparable partitions are counted by A325535. Strict permutations of prime indices are counted by A335489.
Numbers k such that there exists a permutation of the prime indices of k matching both (1,2,1) and (2,1,2).
+0
20
36, 72, 90, 100, 108, 126, 144, 180, 196, 198, 200, 216, 225, 234, 252, 270, 288, 300, 306, 324, 342, 350, 360, 378, 392, 396, 400, 414, 432, 441, 450, 468, 484, 500, 504, 522, 525, 540, 550, 558, 576, 588, 594, 600, 612, 630, 648, 650, 666, 675, 676, 684, 700
COMMENTS
A prime index of k is a number m such that prime(m) divides k. The multiset of prime indices of k is row k of A112798. We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).
EXAMPLE
The sequence of terms together with their prime indices begins:
36: {1,1,2,2}
72: {1,1,1,2,2}
90: {1,2,2,3}
100: {1,1,3,3}
108: {1,1,2,2,2}
126: {1,2,2,4}
144: {1,1,1,1,2,2}
180: {1,1,2,2,3}
196: {1,1,4,4}
198: {1,2,2,5}
200: {1,1,1,3,3}
216: {1,1,1,2,2,2}
225: {2,2,3,3}
234: {1,2,2,6}
252: {1,1,2,2,4}
270: {1,2,2,2,3}
288: {1,1,1,1,1,2,2}
300: {1,1,2,3,3}
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[100], Select[Permutations[primeMS[#]], MatchQ[#, {___, x_, ___, y_, ___, x_, ___}/; x<y]&&MatchQ[#, {___, x_, ___, y_, ___, x_, ___}/; x>y]&]!={}&]
CROSSREFS
Replacing "and" with "or" gives A126706. Positions of nonzero terms in A335462. Permutations of prime indices are counted by A008480. Unsorted prime signature is A124010. Sorted prime signature is A118914. STC-numbers of permutations of prime indices are A333221. Patterns matched by standard compositions are counted by A335454.
Number of separations (Carlitz compositions or anti-runs) of the prime indices of n.
+0
58
1, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 1, 1, 2, 2, 0, 1, 1, 1, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 6, 1, 0, 2, 2, 2, 2, 1, 2, 2, 0, 1, 6, 1, 1, 1, 2, 1, 0, 0, 1, 2, 1, 1, 0, 2, 0, 2, 2, 1, 6, 1, 2, 1, 0, 2, 6, 1, 1, 2, 6, 1, 1, 1, 2, 1, 1, 2, 6, 1, 0, 0, 2, 1, 6, 2, 2, 2
COMMENTS
The first term that is not a factorial number is a(180) = 12.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. A separation (or Carlitz composition) of a multiset is a permutation with no adjacent equal parts.
a(n) depends only on the prime signature of n. - Andrew Howroyd, Feb 03 2021
EXAMPLE
The a(n) separations for n = 2, 6, 30, 180:
(1) (12) (123) (12123)
(21) (132) (12132)
(213) (12312)
(231) (12321)
(312) (13212)
(321) (21213)
(21231)
(21312)
(21321)
(23121)
(31212)
(32121)
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Table[Length[Select[Permutations[primeMS[n]], !MatchQ[#, {___, x_, x_, ___}]&]], {n, 100}]
PROG
(PARI)
F(i, j, r, t) = {sum(k=max(0, i-j), min(min(i, t), (i-j+t)\2), binomial(i, k)*binomial(r-i+1, t+i-j-2*k)*binomial(t-1, k-i+j))}
count(sig)={my(s=vecsum(sig), r=0, v=[1]); for(p=1, #sig, my(t=sig[p]); v=vector(s-r-t+1, j, sum(i=1, #v, v[i]*F(i-1, j-1, r, t))); r += t); v[1]}
CROSSREFS
Permutations of prime indices are counted by A008480. Cf. A000961, A005117, A056239, A112798, A181796, A261962, A333221, A335451, A335454, A335465, A335489.
Number of permutations of the prime indices of n with at least one non-singleton run, or non-separations.
+0
12
0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 0, 1, 0, 2, 0, 2, 0, 0, 0, 4, 1, 0, 1, 2, 0, 0, 0, 1, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 2, 2, 0, 0, 5, 1, 2, 0, 2, 0, 4, 0, 4, 0, 0, 0, 6, 0, 0, 2, 1, 0, 0, 0, 2, 0, 0, 0, 9, 0, 0, 2, 2, 0, 0, 0, 5, 1, 0, 0, 6, 0, 0, 0
COMMENTS
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. A separation (or Carlitz composition) of a multiset is a permutation with no adjacent equal parts.
EXAMPLE
The a(n) non-separations for n = 12, 36, 60, 72, 180, 420:
(11) (112) (1122) (1123) (11122) (11223) (11234)
(211) (1221) (1132) (11212) (11232) (11243)
(2112) (2113) (11221) (11322) (11324)
(2211) (2311) (12112) (12213) (11342)
(3112) (12211) (12231) (11423)
(3211) (21112) (13122) (11432)
(21121) (13221) (21134)
(21211) (21123) (21143)
(22111) (21132) (23114)
(22113) (23411)
(22131) (24113)
(22311) (24311)
(23112) (31124)
(23211) (31142)
(31122) (32114)
(31221) (32411)
(32112) (34112)
(32211) (34211)
(41123)
(41132)
(42113)
(42311)
(43112)
(43211)
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Table[Length[Select[Permutations[primeMS[n]], MatchQ[#, {___, x_, x_, ___}]&]], {n, 100}]
If n = Product (p_j^k_j) then a(n) = Sum (a(n/p_j^k_j)), with a(1) = 1.
+0
24
1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 6, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 6, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 6, 1, 2, 2, 1, 2, 6, 1, 2, 2, 6, 1, 2, 1, 2, 2, 2, 2, 6, 1, 2, 1, 2, 1, 6, 2, 2, 2, 2, 1, 6, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2
COMMENTS
Number of ordered prime factorizations of radical of n.
Number of permutations of the prime indices of n (counting multiplicity) avoiding the patterns (1,2,1) and (2,1,2). These are permutations with all equal parts contiguous. Depends only on sorted prime signature ( A118914). - Gus Wiseman, Jun 27 2020
FORMULA
a(1) = 1; a(n) = Sum_{d|n, d < n, gcd(d, n/d) = 1} A069513(n/d) * a(d).
EXAMPLE
The a(n) permutations of prime indices for n = 2, 12, 60:
(1) (112) (1123)
(211) (1132)
(2113)
(2311)
(3112)
(3211)
(End)
MAPLE
f:= n -> nops(numtheory:-factorset(n))!:
MATHEMATICA
a[1] = 1; a[n_] := a[n] = Plus @@ (a[n/#[[1]]^#[[2]]] & /@ FactorInteger[n]); Table[a[n], {n, 1, 100}]
a[1] = 1; a[n_] := a[n] = Sum[If[GCD[n/d, d] == 1 && d < n, Boole[PrimePowerQ[n/d]] a[d], 0], {d, Divisors[n]}]; Table[a[n], {n, 1, 100}]
Table[PrimeNu[n]!, {n, 1, 100}]
CROSSREFS
Permutations of prime indices are A008480. Unsorted prime signature is A124010. Sorted prime signature is A118914. (1,2,1)-avoiding permutations of prime indices are A335449. (2,1,2)-avoiding permutations of prime indices are A335450. (1,2,1) or (2,1,2)-matching permutations of prime indices are A335460. (1,2,1) and (2,1,2)-matching permutations of prime indices are A335462.
Numbers whose multiset of prime indices is separable.
+0
101
1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 26, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 50, 51, 52, 53, 55, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 82, 83
COMMENTS
First differs from A212167 in having 72. Includes all squarefree numbers A005117. A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. Also Heinz numbers of separable partitions ( A325534). The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). Also numbers that cannot be written as a product of prime numbers, each different from the last but not necessarily different from those prior to the last.
EXAMPLE
The sequence of terms together with their prime indices begins:
1: {} 20: {1,1,3} 39: {2,6}
2: {1} 21: {2,4} 41: {13}
3: {2} 22: {1,5} 42: {1,2,4}
5: {3} 23: {9} 43: {14}
6: {1,2} 26: {1,6} 44: {1,1,5}
7: {4} 28: {1,1,4} 45: {2,2,3}
10: {1,3} 29: {10} 46: {1,9}
11: {5} 30: {1,2,3} 47: {15}
12: {1,1,2} 31: {11} 50: {1,3,3}
13: {6} 33: {2,5} 51: {2,7}
14: {1,4} 34: {1,7} 52: {1,1,6}
15: {2,3} 35: {3,4} 53: {16}
17: {7} 36: {1,1,2,2} 55: {3,5}
18: {1,2,2} 37: {12} 57: {2,8}
19: {8} 38: {1,8} 58: {1,10}
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[100], Select[Permutations[primeMS[#]], !MatchQ[#, {___, x_, x_, ___}]&]!={}&]
CROSSREFS
The version for a multiset with prescribed multiplicities is A335127. Separable factorizations are counted by A335434. Permutations of prime indices are counted by A008480. Inseparable partitions are counted by A325535. Strict permutations of prime indices are counted by A335489.
Search completed in 0.012 seconds
|