Displaying 1-10 of 50 results found.
Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.
+10
157
1, 1, 1, 3, 4, 7, 12, 19, 29, 48, 75, 118, 186, 293, 460, 725, 1139, 1789, 2814, 4422, 6949, 10924, 17168, 26979, 42404, 66644, 104737, 164610, 258707, 406588, 639009, 1004287, 1578363, 2480606, 3898599, 6127152, 9629623, 15134213, 23785388, 37381849, 58750468
COMMENTS
Original name: Wiggly sums: number of sums adding to n in which terms alternately increase and decrease or vice versa.
FORMULA
a(n) = A025048(n) + A025049(n) - 1 = sum_k[ A059881(n, k)] = sum_k[S(n, k) + T(n, k)] - 1 where if n>k>0 S(n, k) = sum_j[T(n - k, j)] over j>k and T(n, k) = sum_j[S(n - k, j)] over k>j (note reversal) and if n>0 S(n, n) = T(n, n) = 1; S(n, k) = A059882(n, k), T(n, k) = A059883(n, k). - Henry Bottomley, Feb 05 2001 a(n) ~ c * d^n, where d = 1.571630806607064114100138865739690782401305155950789062725..., c = 0.82222360450823867604750473815253345888526601460811483897... . - Vaclav Kotesovec, Sep 12 2014
EXAMPLE
There are a(7)=19 such compositions of 7:
[ 1] + [ 1 2 1 2 1 ]
[ 2] + [ 1 2 1 3 ]
[ 3] + [ 1 3 1 2 ]
[ 4] + [ 1 4 2 ]
[ 5] + [ 1 5 1 ]
[ 6] + [ 1 6 ]
[ 7] - [ 2 1 3 1 ]
[ 8] - [ 2 1 4 ]
[ 9] + [ 2 3 2 ]
[10] + [ 2 4 1 ]
[11] + [ 2 5 ]
[12] - [ 3 1 2 1 ]
[13] - [ 3 1 3 ]
[14] + [ 3 4 ]
[15] - [ 4 1 2 ]
[16] - [ 4 3 ]
[17] - [ 5 2 ]
[18] - [ 6 1 ]
[19] 0 [ 7 ]
For A025048(7)-1=10 of these the first two parts are increasing (marked by '+'), and for A025049(7)-1=8 the first two parts are decreasing (marked by '-'). (End)
MAPLE
b:= proc(n, l, t) option remember; `if`(n=0, 1, add(
b(n-j, j, 1-t), j=`if`(t=1, 1..min(l-1, n), l+1..n)))
end:
a:= n-> 1+add(add(b(n-j, j, i), i=0..1), j=1..n-1):
MATHEMATICA
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], wigQ]], {n, 0, 15}] (* Gus Wiseman, Jun 17 2021 *)
PROG
(PARI)
D(n, f)={my(M=matrix(n, n, j, k, k>=j), s=M[, n]); for(b=1, n, f=!f; M=matrix(n, n, j, k, if(k<j, if(f, if(k>1, M[j-k, k-1]), M[j-k, n]-M[j-k, k] ))); for(k=2, n, M[, k]+=M[, k-1]); s+=M[, n]); s~}
seq(n) = concat([1], D(n, 0) + D(n, 1) - vector(n, j, 1)) \\ Andrew Howroyd, Jan 31 2024
CROSSREFS
The version allowing pairs (x,x) is A344604. A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A345164 counts alternating permutations of prime indices.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
Cf. A000070, A008965, A238279, A333755, A344606, A344614, A344653, A344740, A345163, A345166, A345169.
Number of alternating permutations of order n.
(Formerly M1235 N0472)
+10
122
1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, 707584, 5405530, 44736512, 398721962, 3807514624, 38783024290, 419730685952, 4809759350882, 58177770225664, 740742376475050, 9902996106248192, 138697748786275802, 2030847773013704704, 31029068327114173810
COMMENTS
For n>1, a(n) is the number of permutations of order n with the length of longest run equal 2.
Number of inversion sequences of length n where all consecutive subsequences i,j,k satisfy i >= j < k or i < j >= k. a(4) = 10: 0010, 0011, 0020, 0021, 0022, 0101, 0102, 0103, 0112, 0113. - Alois P. Heinz, Oct 16 2019
REFERENCES
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
C. Davis, Problem 4755, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534. Chandler Davis, Problem 4755: A Permutation Problem, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534. [Denoted by P_n in solution.] [Annotated scanned copy]
FORMULA
a(n) = coefficient of x^(n-1)/(n-1)! in power series expansion of (tan(x) + sec(x))^2 = (tan(x)+1/cos(x))^2.
a(n) = coefficient of x^n/n! in power series expansion of 2*(tan(x) + sec(x)) - 2 - x. - Michael Somos, Feb 05 2011 a(n) = 4*|Li_{-n}(i)| - [n=1] = Sum_{m=0..n/2} (-1)^m*2^(1-k)*Sum_{j=0..k} binomial(k,j)*(-1)^j*(k-2*j)^(n+1)/k - [n=1], where k = k(m) = n+1-2*m and [n=1] equals 1 if n=1 and zero else; Li denotes the polylogarithm (and i^2 = -1). - M. F. Hasler, May 20 2012 Let E(x) = 2/(1-sin(x))-1 (essentially the e.g.f.), then
E(x) = -1 + 2*(-1/x + 1/(1-x)/x - x^3/((1-x)*((1-x)*G(0) + x^2))) where G(k) = (2*k+2)*(2*k+3)-x^2+(2*k+2)*(2*k+3)*x^2/G(k+1); (continued fraction, Euler's 1st kind, 1-step).
E(x) = -1 + 2*(-1/x + 1/(1-x)/x - x^3/((1-x)*((1-x)*G(0) + x^2))) where G(k) = 8*k + 6 - x^2/(1 + (2*k+2)*(2*k+3)/G(k+1)); (continued fraction, Euler's 2nd kind, 2-step).
E(x) = (tan(x) + sec(x))^2 = -1 + 2/(1-x*G(0)) where G(k) = 1 - x^2/(2*(2*k+1)*(4*k+3) - 2*x^2*(2*k+1)*(4*k+3)/(x^2 - 4*(k+1)*(4*k+5)/G(k+1))); (continued fraction, 3rd kind, 3-step).
(End)
G.f.: conjecture: 2*T(0)/(1-x) -1, where T(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - 2*(1-x*(k+1))*(1-x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 19 2013
EXAMPLE
1 + x + 2*x^2 + 4*x^3 + 10*x^4 + 32*x^5 + 122*x^6 + 544*x^7 + 2770*x^8 + ...
The a(0) = 1 through a(4) = 10 permutations:
() (1) (1,2) (1,3,2) (1,3,2,4)
(2,1) (2,1,3) (1,4,2,3)
(2,3,1) (2,1,4,3)
(3,1,2) (2,3,1,4)
(2,4,1,3)
(3,1,4,2)
(3,2,4,1)
(3,4,1,2)
(4,1,3,2)
(4,2,3,1)
(End)
MAPLE
# With Eulerian polynomials:
A := (n, x) -> `if`(n<2, 1/2/(1+I)^(1-n), add(add((-1)^j*binomial(n+1, j)*(m+1-j)^n, j=0..m)*x^m, m=0..n-1)):
A001250 := n -> 2*(I-1)^(1-n)*exp(I*(n-1)*Pi/2)*A(n, I);
# second Maple program:
b:= proc(u, o) option remember;
`if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
end:
a:= n-> `if`(n<2, 1, 2)*b(n, 0):
MATHEMATICA
Table[Length[Select[Permutations[Range[n]], And@@(!(OrderedQ[#]||OrderedQ[Reverse[#]])&/@Partition[#, 3, 1])&]], {n, 8}] (* Gus Wiseman, Jun 21 2021 *) a[0]:=1; a[1]:=1; a[n_]:=a[n]=1/(n (n-1)) Sum[a[n-1-k] a[k] k, {k, 1, n-1}]; Join[{a[0], a[1]}, Map[2 #! a[#]&, Range[2, 24]]] (* Oliver Seipel, May 27 2024 *)
PROG
(PARI) {a(n) = local(v=[1], t); if( n<0, 0, for( k=2, n+3, t=0; v = vector( k, i, if( i>1, t += v[k+1 - i]))); v[3])} /* Michael Somos, Feb 03 2004 */ (PARI) {a(n) = if( n<0, 0, n! * polcoeff( (tan(x + x * O(x^n)) + 1 / cos(x + x * O(x^n)))^2, n))} /* Michael Somos, Feb 05 2011 */ (PARI) A001250(n)=sum(m=0, n\2, my(k); (-1)^m*sum(j=0, k=n+1-2*m, binomial(k, j)*(-1)^j*(k-2*j)^(n+1))/k>>k)*2-(n==1) \\ M. F. Hasler, May 19 2012 (Sage) # Algorithm of L. Seidel (1877)
R = [1]; A = {-1:0, 0:2}; k = 0; e = 1
for i in (0..n) :
Am = 0; A[k + e] = 0; e = -e
for j in (0..i) : Am += A[k]; A[k] = Am; k += e
if i > 1 : R.append(A[-i//2] if i%2 == 0 else A[i//2])
return R
(PARI)
x='x+O('x^66);
egf=2*(tan(x)+1/cos(x))-2-x;
Vec(serlaplace(egf))
(Haskell)
a001250 n = if n == 1 then 1 else 2 * a000111 n
(Python)
from itertools import accumulate, islice
def A001250_gen(): # generator of terms yield from (1, 1)
blist = (0, 2)
while True:
yield (blist := tuple(accumulate(reversed(blist), initial=0)))[-1]
(Python)
from sympy import bernoulli, euler
def A001250(n): return 1 if n<2 else abs(((1<<n+1)-1<<n+1)*bernoulli(n+1)//(n+1) if n&1 else euler(n))<<1 # Chai Wah Wu, Nov 13 2024
CROSSREFS
The version for permutations of prime indices is A345164. The version for patterns is A345194. A049774 counts permutations avoiding adjacent (1,2,3).
A344614 counts compositions avoiding adjacent (1,2,3) and (3,2,1).
A344615 counts compositions avoiding the weak adjacent pattern (1,2,3).
A344654 counts partitions without a wiggly permutation, ranked by A344653.
A345170 counts partitions with a wiggly permutation, ranked by A345172.
Cf. A000041, A003242, A032020, A056986, A261962, A325534, A325535, A335452, A344652, A344740, A345165.
Numbers k such that the k-th composition in standard order is alternating.
+10
75
0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 16, 17, 18, 20, 22, 24, 25, 32, 33, 34, 38, 40, 41, 44, 45, 48, 49, 50, 54, 64, 65, 66, 68, 70, 72, 76, 77, 80, 81, 82, 88, 89, 96, 97, 98, 102, 108, 109, 128, 129, 130, 132, 134, 140, 141, 144, 145, 148, 152, 153, 160, 161, 162
COMMENTS
The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).
EXAMPLE
The terms together with their binary indices begin:
1: (1) 25: (1,3,1) 66: (5,2)
2: (2) 32: (6) 68: (4,3)
4: (3) 33: (5,1) 70: (4,1,2)
5: (2,1) 34: (4,2) 72: (3,4)
6: (1,2) 38: (3,1,2) 76: (3,1,3)
8: (4) 40: (2,4) 77: (3,1,2,1)
9: (3,1) 41: (2,3,1) 80: (2,5)
12: (1,3) 44: (2,1,3) 81: (2,4,1)
13: (1,2,1) 45: (2,1,2,1) 82: (2,3,2)
16: (5) 48: (1,5) 88: (2,1,4)
17: (4,1) 49: (1,4,1) 89: (2,1,3,1)
18: (3,2) 50: (1,3,2) 96: (1,6)
20: (2,3) 54: (1,2,1,2) 97: (1,5,1)
22: (2,1,2) 64: (7) 98: (1,4,2)
24: (1,4) 65: (6,1) 102: (1,3,1,2)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@Position[ Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]] ==Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Select[Range[0, 100], wigQ@*stc]
CROSSREFS
Partitions with a permutation of this type: A345170, complement A345165. Factorizations with a permutation of this type: A348379. A003242 counts anti-run compositions.
A345164 counts alternating permutations of prime indices.
Statistics of standard compositions:
- Number of maximal anti-runs is A333381. - Number of distinct parts is A334028. Classes of standard compositions:
- Weakly decreasing compositions (partitions) are A114994. - Weakly increasing compositions (multisets) are A225620. - Non-alternating anti-runs are A345169. Cf. A025048, A025049, A059893, A106356, A238279, A335448, A344604, A344615, A344653, A344742, A345163, A348377.
Number of non-alternating compositions of n.
+10
59
0, 0, 1, 1, 4, 9, 20, 45, 99, 208, 437, 906, 1862, 3803, 7732, 15659, 31629, 63747, 128258, 257722, 517339, 1037652, 2079984, 4167325, 8346204, 16710572, 33449695, 66944254, 133959021, 268028868, 536231903, 1072737537, 2145905285, 4292486690, 8586035993, 17173742032, 34350108745, 68704342523, 137415168084
COMMENTS
A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).
EXAMPLE
The a(2) = 1 through a(6) = 20 compositions:
(11) (111) (22) (113) (33)
(112) (122) (114)
(211) (221) (123)
(1111) (311) (222)
(1112) (321)
(1121) (411)
(1211) (1113)
(2111) (1122)
(11111) (1131)
(1221)
(1311)
(2112)
(2211)
(3111)
(11112)
(11121)
(11211)
(12111)
(21111)
(111111)
MATHEMATICA
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !wigQ[#]&]], {n, 0, 15}]
CROSSREFS
The version for factorizations is A348613. A003242 counts anti-run compositions.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A344604 counts alternating compositions with twins.
A344605 counts alternating patterns with twins.
A344654 counts non-twin partitions with no alternating permutation.
A345162 counts normal partitions with no alternating permutation.
A345164 counts alternating permutations of prime indices.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
Patterns:
- A128761 avoiding (1,2,3) adjacent. - A344614 avoiding (1,2,3) and (3,2,1) adjacent. - A344615 weakly avoiding (1,2,3) adjacent. Cf. A000070, A008965, A178470, A238279, A333755, A335126, A344606, A344653, A344740, A345163, A345166, A345169, A345173, A348380.
Number of integer partitions of n with an alternating permutation.
+10
58
1, 1, 1, 2, 3, 5, 6, 10, 14, 19, 25, 36, 48, 64, 84, 111, 146, 191, 244, 315, 404, 515, 651, 823, 1035, 1295, 1616, 2011, 2492, 3076, 3787, 4650, 5695, 6952, 8463, 10280, 12460, 15059, 18162, 21858, 26254, 31463, 37641, 44933, 53554, 63704, 75653, 89683, 106162, 125445, 148020
COMMENTS
First differs from A325534 at a(10) = 25, A325534(10) = 26. The first separable partition without an alternating permutation is (3,2,2,2,1). A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,3,2,2,2,2,1) has no alternating permutations, even though it has the anti-run permutations (2,3,2,3,2,1,2), (2,3,2,1,2,3,2), and (2,1,2,3,2,3,2).
EXAMPLE
The a(1) = 1 through a(8) = 14 partitions:
(1) (2) (3) (4) (5) (6) (7) (8)
(21) (31) (32) (42) (43) (53)
(211) (41) (51) (52) (62)
(221) (321) (61) (71)
(311) (411) (322) (332)
(2211) (331) (422)
(421) (431)
(511) (521)
(3211) (611)
(22111) (3221)
(3311)
(4211)
(22211)
(32111)
MATHEMATICA
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[IntegerPartitions[n], Select[Permutations[#], wigQ]!={}&]], {n, 0, 15}]
CROSSREFS
Includes all strict partitions A000009. Including twins (x,x) gives A344740. The Heinz numbers of these partitions are A345172. The version for factorizations is A348379. A001250 counts alternating permutations.
A003242 counts anti-run compositions.
A344604 counts alternating compositions with twins.
Cf. A000070, A103919, A335126, A344605, A344653, A344654, A344742, A345164, A345166, A345167, A345168, A345195.
Number of integer partitions of n of which every permutation has a consecutive monotone triple, i.e., a triple (..., x, y, z, ...) such that either x <= y <= z or x >= y >= z.
+10
53
0, 0, 0, 1, 1, 2, 4, 5, 7, 11, 16, 20, 28, 37, 50, 65, 84, 106, 140, 175, 222, 277, 350, 432, 539, 663, 819, 999, 1225, 1489, 1816, 2192, 2653, 3191, 3846, 4603, 5516, 6578, 7852, 9327, 11083, 13120, 15532, 18328, 21620, 25430, 29904, 35071, 41110, 48080
COMMENTS
Such a permutation is characterized by being neither a twin (x,x) nor wiggly ( A025047, A345192). A sequence is wiggly if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,3,2,2,2,2,1) has no wiggly permutations, even though it has the anti-run permutations (2,3,2,3,2,1,2), (2,3,2,1,2,3,2), and (2,1,2,3,2,3,2).
EXAMPLE
The a(3) = 1 through a(9) = 11 partitions:
(111) (1111) (2111) (222) (2221) (2222) (333)
(11111) (3111) (4111) (5111) (3222)
(21111) (31111) (41111) (6111)
(111111) (211111) (221111) (22221)
(1111111) (311111) (51111)
(2111111) (321111)
(11111111) (411111)
(2211111)
(3111111)
(21111111)
(111111111)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], Select[Permutations[#], !MatchQ[#, {___, x_, y_, z_, ___}/; x<=y<=z||x>=y>=z]&]=={}&]], {n, 15}]
CROSSREFS
The Heinz numbers of these partitions are A344653, complement A344742. The complement is counted by A344740. The normal case starts 0, 0, 0, then becomes A345162, complement A345163. A001250 counts wiggly permutations.
A003242 counts anti-run compositions.
A344604 counts wiggly compositions with twins.
A344605 counts wiggly patterns with twins.
A344606 counts wiggly permutations of prime indices with twins.
A344614 counts compositions with no consecutive strictly monotone triple.
A345164 counts wiggly permutations of prime indices.
A345170 counts partitions with a wiggly permutation, ranked by A345172.
A345192 counts non-wiggly compositions.
Cf. A000041, A000070, A102726, A103919, A333489, A335126, A344607, A344615, A345166, A345168, A345169.
Every permutation of the prime factors of n has a consecutive monotone triple, i.e., a triple (..., x, y, z, ...) such that either x <= y <= z or x >= y >= z.
+10
52
8, 16, 24, 27, 32, 40, 48, 54, 56, 64, 80, 81, 88, 96, 104, 112, 125, 128, 135, 136, 144, 152, 160, 162, 176, 184, 189, 192, 208, 224, 232, 240, 243, 248, 250, 256, 270, 272, 288, 296, 297, 304, 320, 324, 328, 336, 343, 344, 351, 352, 368, 375, 376, 378, 384
COMMENTS
Differs from A335448 in lacking squares and having 270 etc. First differs from A345193 in having 270. Such a permutation is characterized by being neither a twin (x,x) nor wiggly ( A025047, A345192). A sequence is wiggly if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no wiggly permutations, even though it has anti-run permutations (2,3,2,1,2) and (2,1,2,3,2). The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.
EXAMPLE
The sequence of terms together with their prime indices begins:
8: {1,1,1}
16: {1,1,1,1}
24: {1,1,1,2}
27: {2,2,2}
32: {1,1,1,1,1}
40: {1,1,1,3}
48: {1,1,1,1,2}
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}
For example, 36 has prime indices (1,1,2,2), which has the two wiggly permutations (1,2,1,2) and (2,1,2,1), so 36 is not in the sequence.
MATHEMATICA
Select[Range[100], Select[Permutations[Flatten[ConstantArray@@@FactorInteger[#]]], !MatchQ[#, {___, x_, y_, z_, ___}/; x<=y<=z||x>=y>=z]&]=={}&]
CROSSREFS
These partitions are counted by A344654. A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A001250 counts wiggly permutations.
A003242 counts anti-run compositions.
A344604 counts wiggly compositions with twins.
A345164 counts wiggly permutations of prime indices.
A345165 counts partitions without a wiggly permutation, ranked by A345171.
A345170 counts partitions with a wiggly permutation, ranked by A345172.
A345192 counts non-wiggly compositions.
Cf. A001222, A071321, A071322, A316523, A316524, A335126, A344614, A344615, A344616, A344652, A345163, A345168, A345193.
Numbers k such that the k-th composition in standard order is not alternating.
+10
48
3, 7, 10, 11, 14, 15, 19, 21, 23, 26, 27, 28, 29, 30, 31, 35, 36, 37, 39, 42, 43, 46, 47, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 67, 69, 71, 73, 74, 75, 78, 79, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95, 99, 100, 101, 103, 104, 105, 106, 107, 110
COMMENTS
The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).
EXAMPLE
The sequence of terms together with their binary indices begins:
3: (1,1) 35: (4,1,1) 59: (1,1,2,1,1)
7: (1,1,1) 36: (3,3) 60: (1,1,1,3)
10: (2,2) 37: (3,2,1) 61: (1,1,1,2,1)
11: (2,1,1) 39: (3,1,1,1) 62: (1,1,1,1,2)
14: (1,1,2) 42: (2,2,2) 63: (1,1,1,1,1,1)
15: (1,1,1,1) 43: (2,2,1,1) 67: (5,1,1)
19: (3,1,1) 46: (2,1,1,2) 69: (4,2,1)
21: (2,2,1) 47: (2,1,1,1,1) 71: (4,1,1,1)
23: (2,1,1,1) 51: (1,3,1,1) 73: (3,3,1)
26: (1,2,2) 52: (1,2,3) 74: (3,2,2)
27: (1,2,1,1) 53: (1,2,2,1) 75: (3,2,1,1)
28: (1,1,3) 55: (1,2,1,1,1) 78: (3,1,1,2)
29: (1,1,2,1) 56: (1,1,4) 79: (3,1,1,1,1)
30: (1,1,1,2) 57: (1,1,3,1) 83: (2,3,1,1)
31: (1,1,1,1,1) 58: (1,1,2,2) 84: (2,2,3)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]==Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Select[Range[0, 100], Not@*wigQ@*stc]
CROSSREFS
These compositions are counted by A345192. A003242 counts anti-run compositions.
A344604 counts alternating compositions with twins.
A345164 counts alternating permutations of prime indices (with twins: A344606).
A345165 counts partitions without a alternating permutation, ranked by A345171.
A345170 counts partitions with a alternating permutation, ranked by A345172.
A348610 counts alternating ordered factorizations, complement A348613.
Statistics of standard compositions:
- Number of maximal anti-runs is A333381. - Number of distinct parts is A334028. Classes of standard compositions:
- Weakly decreasing compositions (partitions) are A114994. - Weakly increasing compositions (multisets) are A225620. - Constant compositions are A272919. - Anti-run compositions are A333489. - Non-anti-run compositions are A348612. Cf. A001222, A005649, A008965, A059893, A106356, A238279, A344615, A345162, A345163, A345166, A345169, A348377, A348380.
Number of non-alternating permutations of {1...n}.
+10
48
0, 0, 0, 2, 14, 88, 598, 4496, 37550, 347008, 3527758, 39209216, 473596070, 6182284288, 86779569238, 1303866853376, 20884006863710, 355267697410048, 6397563946377118, 121586922638606336, 2432161265800164950, 51081039175603191808, 1123862030028821404198
COMMENTS
A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either.
Also permutations of {1...n} matching the consecutive patterns (1,2,3) or (3,2,1). Matching only one of these gives A065429.
EXAMPLE
The a(4) = 14 permutations:
(1,2,3,4) (3,1,2,4)
(1,2,4,3) (3,2,1,4)
(1,3,4,2) (3,4,2,1)
(1,4,3,2) (4,1,2,3)
(2,1,3,4) (4,2,1,3)
(2,3,4,1) (4,3,1,2)
(2,4,3,1) (4,3,2,1)
MAPLE
b:= proc(u, o) option remember;
`if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
end:
a:= n-> n!-`if`(n<2, 1, 2)*b(n, 0):
MATHEMATICA
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]] ==Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Permutations[Range[n]], !wigQ[#]&]], {n, 0, 6}]
PROG
(Python)
from itertools import accumulate, count, islice
def A348615_gen(): # generator of terms yield from (0, 0)
blist, f = (0, 2), 1
for n in count(2):
f *= n
yield f - (blist := tuple(accumulate(reversed(blist), initial=0)))[-1]
CROSSREFS
The complementary version for compositions is A025047, ranked by A345167. The version for ordered factorizations is A348613, complement A348610. A345165 counts partitions w/o an alternating permutation, ranked by A345171.
A345170 counts partitions w/ an alternating permutation, ranked by A345172.
A348379 counts factorizations with an alternating permutation.
A348380 counts factorizations without an alternating permutation.
Cf. A056986, A102726, A325534, A325535, A344614, A344653, A344654, A347050, A347706, A348377, A348609.
Numbers whose multiset of prime factors has an alternating permutation.
+10
45
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 containing 72. First differs from A335433 in lacking 270, corresponding to the partition (3,2,2,2,1). A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,3,2,2,2,2,1) has no alternating permutations, even though it has the anti-run permutations (2,3,2,3,2,1,2), (2,3,2,1,2,3,2), and (2,1,2,3,2,3,2).
The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.
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
wigQ[y_]:=Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1;
Select[Range[100], Select[Permutations[ Flatten[ConstantArray@@@FactorInteger[#]]], wigQ[#]&]!={}&]
CROSSREFS
Positions of nonzero terms in A345164. The partitions with these Heinz numbers are counted by A345170. A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A001250 counts alternating permutations.
A003242 counts anti-run compositions.
A344604 counts alternating compositions with twins.
A344606 counts alternating permutations of prime indices with twins.
A345192 counts non-alternating compositions.
Cf. A001222, A071321, A071322, A316523, A316524, A335126, A344605, A344614, A344616, A344653, A344654, A345163, A345167, A347706, A348379.
Search completed in 0.059 seconds
|