This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

1
vote
1answer
10 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ...
2
votes
1answer
27 views

Permutation Partition Counting

Consider the number $n!$ for some integer $n$ In how many ways can $n!$ be expressed as $$a_1!a_2!\cdots a_n!$$ for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as ...
8
votes
2answers
139 views

Tricky (extremal?) combinatorics problem

Apologies for being unsure the best way to express this problem. I have 9 tables with 4 students at each table. I want to re-seat all students so no two students who have sat together ever sit ...
6
votes
3answers
507 views

$\tbinom{2p}{p}-2$ is divisible by $p^3$

The problem is as follows: Let $p>3$ be a prime. Show that $\tbinom{2p}{p}-2$ is divisible by $p^3$. The only thing I can think of is that $(2p)!-2(p!)^2$ is divisible by $p^2$ which doesn't help ...
0
votes
2answers
22 views

How to find a pointset with unique distances

Is there a way to arrange N number of 2D points within a box so that the distances between the points are unique? I have an application where I can measure the distances between points with some ...
0
votes
1answer
219 views

Combinatorics and Inversion Sequences

Determine the inversion sequence of the following permutation of $ \{ 1,\ 2, \cdots , 8 \}$. $$ 83476215 $$ I just don't understand how that is converted into a series of numbers 0, 1, and 2 and ...
5
votes
1answer
106 views

Combinations mod $n$ property

So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense): $\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n ...
0
votes
3answers
68 views

how many words can be formed using all letters in the word EXAMINATION

Assuming any sequence of letters is a word, how many words can we form in such a way that the first two letters are different consonants while the last two letters are vowels?
7
votes
2answers
2k views

Calculating heavy numbers in a given range?

I had an interview question a couple days ago involving the calculation of the amount of heavy numbers between in a given range. I came up with a basic solution, which was to iterate over the entire ...
23
votes
3answers
1k views

Guaranteed Checkmate with Rooks in High-Dimensional Chess

Given an infinite (in all directions), $n$-dimensional chess board $\mathbb Z^n$, and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite ...
1
vote
2answers
29 views

Number of $n$ letter words from letters a,b that contain exactly $m$ substrings “ab”

I want to prove the number of $n$ letter words that just have letters a,b that exactly have $m$ "ab" expression is $n+1 \choose ...
0
votes
0answers
17 views

What is the number of sign patterns in $\frac n2$ of columns (or rows) of Hadamard matrices?

Given a Hadamard matrix of size $n$, I want to know what is the number of unique sign patterns in any $\frac n2$ columns (or rows). I count a sign pattern and its negation to be the same. My guess ...
0
votes
1answer
22 views

Combination with repition, Representation techniques.

Consider the following Question:A bagel shop has onion bagels, poppy seed bagels, egg bagels, salty bagels, pumpernick bagels, sesame seed bagels, raisin bagels, and plain bagels. How many ways are ...
0
votes
2answers
1k views

Coin Toss Probablities and Outcomes

I'm having a hard time with this question, but I did the best that I could. I would appreciate any help to correctly solve it. Suppose that a coin is tossed three times and the side that ...
2
votes
1answer
19 views

number of ways to put 4 black,4 white,4 red balls in 6 different boxes

The question says:in how many ways we could put 4 black,4 white,4 red balls in 6 different boxes? boxes are distinguishable,black balls are identical,red balls are identical,and white balls are ...
8
votes
1answer
80 views
+150

Blocking lines of length $5$ in a $7 \times 8$ matrix; how can we know the solutions have a specific form?

A friend shared with me the following puzzle he encountered in a Chinese math competition: In a $7 \times 8$ matrix, we place tokens so that any straight line of length $5$ (horizontal, vertical, ...
0
votes
3answers
72 views

Math Problem on Probability

In the SmallState Lottery, three white balls are drawn (at random) from twenty balls numbered 1 through 20, and a blue SuperBall is drawn (at random) from ten balls numbered 21 through 30. When you ...
0
votes
0answers
65 views

Question about Combinatorics

I understand that for a problem such as 59C5 there are 5,006,386 possible combinations. Is there a way mathematically to determine exactly how many of the 5,006,386 5-digit combinations will sum to a ...
2
votes
0answers
45 views

Number of faces of a polytopal subdivision

Let $\mathcal{P}$ be a (bounded) polytope in $\mathbb{R}^d$ and let $\mathcal{C}$ be a polytopal subdivision of $\mathcal{P}$ [1]. Is there a known tight upper bound in the number of polytopes in ...
-2
votes
3answers
30 views

How can I calculate the total number of possible anagrams for a set of letters?

How can I calculate the total number of possible anagrams for a set of letters? For example: "Math" : 24 possible combinations. ...
1
vote
1answer
29 views

Total number of unique n-element sets from a base of unique elements

I have searched for the answer for this on the site (and on the Internet) and have not found the answer. I do apologize if this is answered and I do not have the vocabulary to ask or search for the ...
2
votes
0answers
23 views

Rotation Algorithim

I have a series of 7 tables and 73 participants in a roundtable discussion. My challenge is to rotate all 73 participants to each of the 7 tables while minimizing the times in which they sit with the ...
2
votes
1answer
32 views

Subjectivity in combinatorics

I found some questions in combinatorics very subjective for example: With the digits $1,2,3,4,5,6$, how many 4-uplas exists (order matters) where the digit 1 is before 4? The solution of this ...
0
votes
0answers
30 views

Evaluate $S=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$

How to find the value (if possible) of this formula? $$S_{n,m}=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$$ where $P=\min\{m,n\}$ et $Q=\max\{m,n\}$.
6
votes
0answers
50 views

Graph partition that span a third of edges

Given a graph G is easy to see that we have a partition $V=V_1 \cup V_2$ so that $$e(G[V_1])+e(G[V_2])\leq e(G)/2$$. How can we improve this result showing that we can choose $V_i$ such that ...
4
votes
2answers
65 views

A game with checkers

Alice puts checkers in some cells of a $8 \times 8$ board such that : There is at least one checker in any $1\times 2$ or $2\times 1$ rectangle. There are at least two adjacent checkers in any ...
2
votes
3answers
52 views

Distinguishability problem /

How many ways are there to put 6 balls in 3 boxes if the balls are distinguishable but the boxes are not? I'm not quite sure how to approach it, $\frac{3^6}{3!}$ is not an integer. Thanks.
4
votes
1answer
2k views

How many triangles with integral side lengths are possible, provided their perimeter is $36$ units?

How many triangles with integral side lengths are possible, provided their perimeter is $36$ units? My approach: Let the side lengths be $a, b, c$; now, $$a + b + c = 36$$ Now, $1 \leq a, b, c ...
0
votes
2answers
22 views

Permutations on the leading diagonal of a matrix

I have an $n\times n$ matrix with only diagonal components which are $\pm 1$. How many of these matrices can I construct? I know this is a basic combinatorics, but I would appreciate some help ...
0
votes
1answer
39 views

Combination with restriction

The problem I am trying to solve is the kinds as below. $l,m,n\in\mathbb{N}$ with $n\leq m\leq l$ (fixed numbers) $S$: a set of size $l$ $H_i$:sets of subsets of $S$ of size $m$ ...
4
votes
3answers
71 views

Transforming a latin square into a sudoku

Can any $9\times 9$ - Latin Square be transformed into a sudoku by just exchanging rows and columns (it is allowed to mix row- and column-exchanges arbitarily and there is no limit for the number of ...
6
votes
1answer
68 views

Is it possible to cover a $70\times70$ square with $24$ squares with side length $1,2,3\ldots24$?

Is it possible to cover a $70\times70$ square with $24$ squares with side length $1,2,3\ldots24$?
0
votes
0answers
44 views
+50

Traverse resultant 2d array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when N is equal to 6: $$\begin{bmatrix} 1 ...
3
votes
5answers
90 views

Classic Counting Problems

Does anyone have some good, classic, counting problems? I want things that are interesting, as well as instructive- more than just compute the number of way to get a flush, etc. (Not that those aren't ...
1
vote
0answers
20 views

Rational Series VS Algebraic Series

I am reading a paper on combinatorics. It mentions some generating functions are rational series and others are algebraic series. I do not understand the difference, can someone help? EDIT $1$: The ...
14
votes
1answer
221 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemples. How to calculate the number of circuits that ...
4
votes
1answer
255 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
0
votes
1answer
41 views

How to calculate the sum of combinatorial numbers

For my work on an almost completely unrelated field I came across the following formula. I know that I have learned that all in high school. But since this is more than 15 years ago in which I never ...
6
votes
5answers
102 views

Finding $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $

Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$ I got a hunch that it will depend on whether $n$ is a multiple of $6$ and equals to $\frac{2^n+2}{3}$ when $n$ is a ...
7
votes
1answer
112 views

Strange factorial identity

The following appears to be true. \begin{align*} n! &= \sum_{k=0}^n \sum_{j=0}^{\lfloor\frac{k}{3}\rfloor}\sum_{i=0}^{k-3j} (-1)^{i+j}\binom{k-2j}{i,j,k-i-3j}\frac{(n-i-2j)!}{(n-k)!}\\ &\qquad ...
3
votes
1answer
57 views

Chess Knight problem

Which is the number of all possible combinations of the knights, which are not mutually attack? The black knight may move to any of eight squares (black dots). The white knight in this case is ...
3
votes
3answers
117 views

Filling a 40 x 40 grid with 3x3 squares

I'm supposed to find out the minimum number of 3x3 squares that will completely fill up this 40x40 grid where overlapping squares is acceptable. Each 3x3 square also has to coincide with the grid ...
1
vote
1answer
33 views

Counting squares in a given k by k square..

So the question is : The solution to this problem according to the book is to first count the number of squares whose sides are parallel to the sides of this 10 by 10 square and then to count the ...
1
vote
1answer
26 views

permutations with a given condition!

What will be the number of permutations of n different things, taken r at a time,when p particular things is to be always included in each arrangement? I know the answer to this question but could not ...
1
vote
1answer
51 views

Calculate single “battle” outcome odds for RISK

I am trying to reproduce the values in this odds ratio table from Wikipedia. For all those unfamiliar with RISK, this is a game where units fight against each other via the roll of the dice: The ...
0
votes
0answers
31 views

In how many ways can you make change for a dollar? [duplicate]

I know there are questions related to this on the site but they are not in the context I am looking for (basic statistics). This problem is at the end of the section introducing combinations and ...
0
votes
1answer
33 views

How to deduce number of unordered distinct pairs using set operations and bijections

In (b) of the example, we are ask to calculate the number of ordered pairs of distinct positive integers. I like the first method's answer (using bijections, set operations) because it clearly shows ...
1
vote
1answer
34 views

Longest path in a grid

I recently saw a computer programming question that asked for the longest path that one can build in a $3\times3$ unit grid connecting the vertexes, with the following rules(the same rules of a ...
1
vote
1answer
54 views

total number of combinations?

Patient Age ---> Avg Visits / Year <1 year ---> 7.5 1-4 years ---> 3.0 5-14 years ---> 1.8 15-24 years ---> 1.7 25-44 years ...
3
votes
1answer
47 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...