A385575
Numbers whose binary indices have the same number of adjacent parts differing by 1 as adjacent parts differing by more than 1.
Original entry on oeis.org
1, 2, 4, 8, 11, 13, 16, 19, 22, 25, 26, 32, 35, 38, 44, 49, 50, 52, 64, 67, 70, 76, 87, 88, 91, 93, 97, 98, 100, 104, 107, 109, 117, 128, 131, 134, 140, 151, 152, 155, 157, 167, 174, 176, 179, 182, 185, 186, 193, 194, 196, 200, 203, 205, 208, 211, 214, 217
Offset: 1
The terms together with their binary expansions and binary indices begin:
1: 1 ~ {1}
2: 10 ~ {2}
4: 100 ~ {3}
8: 1000 ~ {4}
11: 1011 ~ {1,2,4}
13: 1101 ~ {1,3,4}
16: 10000 ~ {5}
19: 10011 ~ {1,2,5}
22: 10110 ~ {2,3,5}
25: 11001 ~ {1,4,5}
26: 11010 ~ {2,4,5}
32: 100000 ~ {6}
35: 100011 ~ {1,2,6}
38: 100110 ~ {2,3,6}
44: 101100 ~ {3,4,6}
49: 110001 ~ {1,5,6}
50: 110010 ~ {2,5,6}
52: 110100 ~ {3,5,6}
64: 1000000 ~ {7}
67: 1000011 ~ {1,2,7}
70: 1000110 ~ {2,3,7}
76: 1001100 ~ {3,4,7}
87: 1010111 ~ {1,2,3,5,7}
88: 1011000 ~ {4,5,7}
91: 1011011 ~ {1,2,4,5,7}
93: 1011101 ~ {1,3,4,5,7}
97: 1100001 ~ {1,6,7}
98: 1100010 ~ {2,6,7}
100: 1100100 ~ {3,6,7}
A384175 counts subsets with all distinct lengths of maximal runs, complement
A384176.
A384877 gives lengths of maximal anti-runs in binary indices, firsts
A384878.
-
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[100],Length[Split[bpe[#],#2==#1+1&]]==Length[Split[bpe[#],#2!=#1+1&]]&]
-
is_ok(n)=hammingweight(n)==2*hammingweight(bitand(n,n>>1))+1 \\ Christian Sievers, Jul 18 2025
A289632
Triangle read by rows: T(n-1,k), where n >= 2 and 1 <= k <= floor(n/2), is the number of permutations of (1, 2, ..., n) having k consecutive pairs but no consecutive sequences of length greater than 2.
Original entry on oeis.org
1, 2, 9, 1, 44, 9, 265, 66, 3, 1854, 530, 44, 14833, 4635, 530, 11, 133496, 44499, 6180, 265, 1334961, 467236, 74165, 4635, 53, 14684570, 5339844, 934472, 74165, 1854, 176214841, 66080565, 12459636, 1168090, 44499, 309, 2290792932, 881074205, 176214840
Offset: 2
The first ten rows of the triangle are:
1;
2;
9, 1;
44, 9;
265, 66, 3;
1854, 530, 44;
14833, 4635, 530, 11;
133496, 44499, 6180, 265;
1334961, 467236, 74165, 4635, 53;
14684570, 5339844, 934472, 74165, 1854;
- Thomas Becker, Table of n, a(n) for n = 2..10001
- Thomas Becker, ConsecutiveSequences (github repository). This repository has JavaScript implementations of some algorithms concerning consecutive sequences in permutations, among them the algorithm that was used to calculate this triangle.
- Thomas Becker, Two General Purpose Algorithms for Counting Permutations with Consecutive Sequences, 2017. This paper has the mathematical description and correctness proofs for the algorithms in the repository above.
- Thomas Becker, Some Mathematics, Algorithms, and Probabilities Concerning Your Music Player's Random Shuffle Mode, 2017. This blog entry has the discussion of random shuffle mode on today's music players that prompted the author's interest in the number of permutations with specified configurations of consecutive sequences.
The first column of the triangle is the number of permutations of n elements that have exactly one consecutive pair. This is known to be the same as the subfactorial or rencontres numbers, or derangements (
A000166).
A010027 has the number of permutations of n elements with k consecutive pairs, without the restriction that the consecutive pairs must not be "linked" to form longer consecutive sequences.
-
/*
* The program below calls into the algorithm package "ConsecutiveSequences" (see link to github repository).
*/
var numberOfPermutationsModule = require("ConsecutiveSequences.min.js");
var mcsSpec = {};
var numPermutations;
var numElements = 42;
var count = 7;
// Calculate the number of permutations that have exactly count many maximal consecutive
// sequences of length 2 and no maximal consecutive sequences of length other than 2.
//
mcsSpec["2"] = count;
numPermutations =
numberOfPermutationsModule.numberOfPermutationsThatMeetAnMcsSpecificationByLengthsAndCounts(
numElements,
mcsSpec
);
A345462
Triangle T(n,k) (n >= 1, 0 <= k <= n-1) read by rows: number of distinct permutations after k steps of the "first transposition" algorithm.
Original entry on oeis.org
1, 2, 1, 6, 3, 1, 24, 13, 4, 1, 120, 67, 23, 5, 1, 720, 411, 146, 36, 6, 1, 5040, 2921, 1067, 272, 52, 7, 1, 40320, 23633, 8800, 2311, 456, 71, 8, 1, 362880, 214551, 81055, 21723, 4419, 709, 93, 9, 1, 3628800, 2160343, 825382, 224650, 46654, 7720, 1042, 118, 10, 1
Offset: 1
Triangle begins:
1;
2, 1;
6, 3, 1;
24, 13, 4, 1;
120, 67, 23, 5, 1;
720, 411, 146, 36, 6, 1;
5040, 2921, 1067, 272, 52, 7, 1;
40320, 23633, 8800, 2311, 456, 71, 8, 1;
...
- D. E. Knuth, The Art of Computer Programming, Vol. 3 / Sorting and Searching, Addison-Wesley, 1973.
Cf.
A107111 a triangle with some common parts.
-
b:= proc(n, k) option remember; (k+1)!*
binomial(n, k)*add((-1)^i/i!, i=0..k+1)/n
end:
T:= proc(n, k) option remember;
`if`(k=0, n!, T(n, k-1)-b(n, n-k+1))
end:
seq(seq(T(n, k), k=0..n-1), n=1..10); # Alois P. Heinz, Aug 11 2021
-
b[n_, k_] := b[n, k] = (k+1)!*Binomial[n, k]*Sum[(-1)^i/i!, {i, 0, k+1}]/n;
T[n_, k_] := T[n, k] = If[k == 0, n!, T[n, k-1] - b[n, n-k+1]];
Table[Table[T[n, k], {k, 0, n - 1}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 06 2022, after Alois P. Heinz *)
A385574
Number of integer partitions of n with the same number of adjacent equal parts as adjacent unequal parts.
Original entry on oeis.org
1, 1, 1, 1, 2, 3, 2, 4, 5, 6, 10, 11, 13, 17, 20, 30, 36, 44, 55, 70, 86, 98, 128, 156, 190, 235, 288, 351, 409, 499, 603, 722, 863, 1025, 1227, 1461, 1757, 2061, 2444, 2892, 3406, 3996, 4708, 5497, 6430, 7595, 8835, 10294, 12027, 13971, 16252, 18887, 21878
Offset: 0
The partition (5,3,2,1,1,1,1) has 4 runs ((5),(3),(2),(1,1,1,1)) and 4 anti-runs ((5,3,2,1),(1),(1),(1)) so is counted under a(14).
The a(1) = 1 through a(10) = 10 reversed partitions (A = 10):
(1) (2) (3) (4) (5) (6) (7) (8) (9) (A)
(112) (113) (114) (115) (116) (117) (118)
(122) (133) (224) (144) (226)
(223) (233) (225) (244)
(11123) (11124) (334)
(11223) (11125)
(11134)
(11224)
(11233)
(12223)
These partitions are ranked by
A385576.
Cf.
A000071,
A003114,
A008284,
A010027,
A047966,
A210034,
A325324,
A325325,
A356606,
A384882,
A384885.
-
Table[Length[Select[Reverse/@IntegerPartitions[n],Length[Union[#]]==Length[Split[#,#2!=#1&]]&]],{n,0,30}]
-
lista(n)=Vec(polcoef((prod(i=1,n,1+x^i/(t*(1-t*x^i))+O(x*x^n))-1)*t+1,0,t)) \\ Christian Sievers, Jul 18 2025
A385214
Number of subsets of {1..n} without all equal lengths of maximal runs of consecutive elements increasing by 1.
Original entry on oeis.org
0, 0, 0, 0, 2, 8, 25, 66, 159, 361, 791, 1688, 3539, 7328, 15040, 30669, 62246, 125896, 253975, 511357, 1028052
Offset: 0
The maximal runs of S = {1,2,4,5,6,8,9} are ((1,2),(4,5,6),(8,9)), with lengths (2,3,2), so S is counted under a(9).
The a(0) = 0 through a(5) = 8 subsets:
. . . . {1,2,4} {1,2,4}
{1,3,4} {1,2,5}
{1,3,4}
{1,4,5}
{2,3,5}
{2,4,5}
{1,2,3,5}
{1,3,4,5}
The complement is counted by
A243815.
For distinct instead of equal lengths we have
A384176, complement
A384175.
For anti-runs instead of runs we have complement of
A384889, for partitions
A384888.
For permutations instead of subsets we have complement of
A384892, distinct
A384891.
For partitions instead of subsets we have complement of
A384904, strict
A384886.
A034839 counts subsets by number of maximal runs, for strict partitions
A116674.
A384177 counts subsets with all distinct lengths of maximal anti-runs, ranks
A384879.
A384887 counts partitions with equal lengths of gapless runs, distinct
A384884.
-
Table[Length[Select[Subsets[Range[n]],!SameQ@@Length/@Split[#,#2==#1+1&]&]],{n,0,10}]
A116855
Triangle read by rows, constructed from binomial transforms of prefixes of A000255 (see Comments for precise definition).
Original entry on oeis.org
1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 6, 4, 1, 1, 2, 6, 13, 5, 1, 1, 2, 6, 24, 23, 6, 1, 1, 2, 6, 24, 67, 36, 7, 1, 1, 2, 6, 24, 120, 146, 52, 8, 1, 1, 2, 6, 24, 120, 411, 272, 71, 9, 1, 1, 2, 6, 24, 120, 720, 1067, 456, 93, 10, 1
Offset: 1
The first few rows of S are
1, 1, 1, 1, ...
1, 2, 3, 4, ...
1, 2, 6, 13, ...
1, 2, 6, 24, ...
...
Read S by antidiagonals to get the desired triangle, which begins
1;
1, 1;
1, 2, 1;
1, 2, 3, 1;
1, 2, 6, 4, 1;
1, 2, 6, 13, 5, 1;
1, 2, 6, 24, 23, 6, 1;
1, 2, 6, 24, 67, 36, 7, 1;
...
Comments