All Questions
Tagged with combinatorics math
56
questions
12
votes
8answers
481 views
Decorate Pascal's Triangle
Although what is a Pascal's triangle is well-known and we already can generate it, the task is now different:
Output \$n\$ first lines of the Pascal's triangle as colored bricks.
Color number is ...
16
votes
14answers
1k views
Permutations in Disguise
Given a \$n\$-dimensional vector \$v\$ with real entries, find a closest permutation \$p\$ of \$(1,2,...,n)\$ with respect to the \$l_1\$-distance.
Details
If it is more convenient, you can use ...
3
votes
1answer
215 views
Multiplication in the Steenrod Algebra
Here's yet another Steenrod algebra question. Summary of the algorithm: I have a procedure that replaces a list of positive integers with a list of lists of positive integers. You need to repeatedly ...
16
votes
11answers
1k views
Generate basis elements of the Steenrod algebra
The Steenrod algebra is an important algebra that comes up in algebraic topology. The Steenrod algebra is generated by operators called "Steenrod squares," one exists for each positive integer i. ...
35
votes
21answers
5k views
Amount of permutations on an NxNxN Rubik's Cube
Introduction:
A 3x3x3 Rubik's Cube has \$43,252,003,274,489,856,000\$ possible permutations, which is approximately 43 quintillion. You may have heard about this number before, but how is it actually ...
6
votes
5answers
310 views
Generate the k-ary necklaces of length n
The set of necklaces is the set of strings, where two strings are considered to be the same necklace if you can rotate one into the other. Your program will take nonnegative integers ...
0
votes
5answers
481 views
Fastest algorithm to output array containing all integers in range excluding duplicate digits
Input is a single integer in ascending digit order.
The only valid inputs are:
12
123
1234
...
10
votes
22answers
2k views
Cartesian product of a list with itself n times
When given a a list of values and a positive integer n, your code should output the cartesian product of the list with itself n ...
24
votes
34answers
2k views
Sign-Swapping Sums
Given a nonempty list of positive integers \$(x, y, z, \dots)\$, your job is to determine the number of unique values of \$\pm x \pm y \pm z \pm \dots\$
For example, consider the list \$(1, 2, 2)\$. ...
16
votes
1answer
325 views
Permutations such that no k+2 points fall on any polynomial of degree k
Description
Let a permutation of the integers {1, 2, ..., n} be called minimally interpolable if no set of k+2 points (together ...
12
votes
4answers
230 views
Compute number of matrices with appropriate sums
When multiplying monomials in the Milnor basis for the Steenrod algebra, part of the algorithm involves enumerating certain "allowable matrices".
Given two lists of nonnegative integers r1, ... ,rm ...
14
votes
16answers
882 views
Mod 2 Multinomial coefficients
quintopia has posted here a challenge to compute multinomial coefficients (some of the text here is copied from there). There is a fun algorithm to compute multinomial coefficients mod 2.
Given a ...
23
votes
5answers
510 views
Determine How many Wheels There Are
Non-math explanation
This is an explanation that is meant to be approachable regardless of your background. It does unfortunately involve some math, but should be understandable to most people with a ...
4
votes
0answers
194 views
Those annoying grasshoppers [closed]
The problem #6 of IMO 2009 reads:
Let a 1, a 2, a 3, ..., a n, be distinct positive integers and let T be a set of n-1positive integers not containing a 1+a 2+a 3+...+a n, A grasshopper is to ...
8
votes
6answers
364 views
Distinct Reversible Primitive Binary Necklaces
Introduction - What is a necklace?
A necklace is something that OEIS people are obsessed with. The OEIS challenge has like 5 necklace sequences.
A binary necklace of length ...
16
votes
16answers
2k views
How many partitions do I have?
The partition number of a positive integer is defined as the number of ways it can be expressed as a sum of positive integers. In other words, the number of integer partitions it has. For example, the ...
16
votes
7answers
1k views
How many partitions contain only perfect squares?
Given a non-negative integer or a list of digits, determine in how many ways can the number be formed by concatenating square numbers, which may have leading zeroes.
Examples
...
14
votes
12answers
1k views
Finding approximate correlations
Consider a binary string S of length n. Indexing from 1, we can compute the Hamming ...
23
votes
0answers
586 views
Maximal discrepancy-2 sequence with minimal entropy
Background
As noted in the PPCG challenge Compress a maximal discrepancy-2 sequence – which inspired this challenge – the authors of the paper Computer-Aided Proof of Erdős Discrepancy Properties ...
12
votes
1answer
348 views
Stable marriage problem
Background
Suppose that there are 2*n people to be married, and suppose further that each person is attracted to exactly n ...
19
votes
5answers
2k views
Necklace splitting problem
Background
I was inspired by 3Blue1Brown's recent video about the necklace splitting problem (or as he calls it, the stolen necklace problem) and its relationship to the Borsuk-Ulam theorem.
In this ...
28
votes
11answers
3k views
Absolute Sums of Sidi Polynomial Coefficients
Background
The Sidi polynomial of degree n – or the (n + 1)th Sidi polynomial – is defined as follows.
The Sidi polynomials have several interesting properties, but so do their coefficients. The ...
8
votes
15answers
409 views
Evaluate the Binomial Coefficient [duplicate]
Given two nonnegative integers n,k such that 0 <= k <= n, return the binomial coefficient
...
21
votes
20answers
6k views
A penny saved is a penny
...counted!
You will pass your program a variable which represents a quantity of money in dollars and/or cents and an array of coin values. Your challenge is to output the number of possible ...
17
votes
15answers
2k views
Compute the Eulerian number
The Eulerian number A(n, m) is the number of permutations of [1, 2, ..., n] in which exactly ...
26
votes
1answer
2k views
Figure Out the Android Lock Pattern
Lets say you saw your friend enter his or her password into their Android phone. You don't remember how they made the pattern but you remember what the pattern looks like. Being the concerned friend ...
12
votes
3answers
339 views
Verify a ballot triangle
A ballot number, which we'll label B, is the number of ways of arranging the numbers from 1 through B(B+1)/2 into a triangle, such that each row and column is in any increasing order. The first four ...
23
votes
12answers
2k views
Number of cycles of a permutation
Consider a permutation of the integers 1, ..., n, such as this one for n = 6:
...
6
votes
6answers
823 views
Is case sensitivity important? Part II: reality check
In this question Tom learned that, in general, there are many motivations to choose to include case sensitivity in his programming language, because the possible combinations for a variable name are ...
13
votes
11answers
2k views
Is case sensitivity important?
Tom is going to implement a new programming language of his invention. But before actually starting working on it, he wants to know whether his language should be case sensitive or not.
On one hand, ...
22
votes
15answers
1k views
Calculate the partitions of N
Your challenge is simple: GIven an integer N, ouput every list of positive integers that sums to N. For example, if the input was 5, you should output
...
3
votes
29answers
4k views
The handshake problem
The handshake problem is the classic problem that for n people in a room, if they all shake hands, what's the total number of handshakes that occur.
You code should take an input of any number and ...
43
votes
19answers
3k views
Has My Pie Been Bisected?
Write a program or function that takes in a nonempty list of positive integers. You may assume it is input in a reasonable convenient format such as "1 2 3 4" or <...
12
votes
10answers
819 views
Permutations with Indistinguishable Items
Given a list of integers, output the number of permutations of the integers, with indistinguishable permutations counted once. If there are n integers, and each ...
15
votes
1answer
416 views
Same-color arithmetic progressions
Van der Waerden's theorem says that
For any given positive integers r and k, there is some number ...
27
votes
17answers
2k views
Compute the multinomial coefficient
Time for another easy challenge in which all can participate!
The multinomial theorem states:
The expression in parentheses is the multinomial coefficient, defined as:
Allowing the terms ki to ...
23
votes
25answers
5k views
Bernoulli Numbers
The Bernoulli numbers (specifically, the second Bernoulli numbers) are defined by the following recursive definition:
Where denotes a combination.
Given a nonnegative integer ...
45
votes
42answers
3k views
Count sums of two squares
Given a non-negative number n, output the number of ways to express n as the sum of two squares of integers ...
10
votes
4answers
297 views
Rearrangement Inequality
Background
The Rearrangement Inequality is an inequality that is based on rearranging numbers. If I have two lists of numbers of the same length, x0, x1, x2...xn-1 and y0, y1, y2...yn-1 of the same ...
17
votes
6answers
329 views
Enumerating N-Dimensional Vectors
Given a positive integer k > 1 and a non-negative integer i, generate a k-tuple (or ...
0
votes
2answers
149 views
Generate ordered binary combinations without repetitions [closed]
Challenge
Write the shortest program that receives two signed integers n and i and for each ...
27
votes
10answers
1k views
Hook length product
A Young diagram is an arrangement of boxes in left-justified rows and top-justified columns. For each box, all the spaces above it and to its left are occupied.
...
10
votes
3answers
614 views
Supersonic domino tilings
Task
Write a program that reads three integers m, n either from STDIN or as command-line arguments, prints all possible tilings of a rectangle of dimensions m × n by 2 × 1 and 1 × 2 dominos and ...
3
votes
1answer
350 views
Plus one sheep minus one sheep [closed]
Once upon a time long long ago... when there was no money or stocks yet, people were trading sheep. Even before (but close to) the invention of abacus, the great-grandfather of Warren Buffet decided ...
11
votes
3answers
975 views
Matrix property X revisited (or the Joy of X)
This challenge is partly an algorithms challenge, partly an optimization challenge and partly simply a fastest code challenge.
A T matrix is fully specified by its first row ...
12
votes
3answers
627 views
Count the number of Hankelable matrices
Background
A binary Hankel matrix is a matrix with constant skew-diagonals (positive sloping diagonals) containing only 0s and 1...
21
votes
13answers
1k views
Combinatorial products of unique primes
Statement of problem
Given a set of unique, consecutive primes (not necessarily including 2), generate the products of all combinations of first powers of these primes — e.g., no repeats — and also 1....
11
votes
10answers
2k views
Fibonacci domino tiling
There's classic combinatorial result that the number of ways to tile a 2*n strip by 1*2 dominoes is the nth Fibonacci number. ...
9
votes
6answers
802 views
Permutation Numbering
The Challenge
For a given set of n integers, write a program which will output its lexicographic index.
The Rules
The input must only be a set of unique non-negative integers separated by spaces.
...
6
votes
5answers
688 views
Output nth term in Catalan type sequence
Given a number, starting with 1, create new numbers (children) by taking the last digit, n, and concatenating 1 through n+1.
This seems to be a much better explanation of the sequence A071159.
...
