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)

0
votes
0answers
91 views

Question about Combinatorics [duplicate]

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
53 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
34 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
43 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
28 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
36 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 ...
4
votes
2answers
69 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
56 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
24 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
40 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
78 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
69 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$?
1
vote
0answers
58 views

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 ...
14
votes
1answer
224 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
42 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
108 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
121 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
62 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
127 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
37 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 ...
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
60 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
48 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 & = & ...
3
votes
2answers
45 views

How is this exactly equal to $N_1+N_2+\dots+N_r$?

There are $N$ boxes, each containing at most $r$ balls. If the number of boxes containing at least $i$ balls is $N_i$ for $i=1,2,\dots,r,$ then the total number of balls contained in these $N$ ...
3
votes
3answers
49 views

Counting the factors of $2^4 \cdot 3^5 \cdot 4^6 \cdot 6^7$

Let $n = 2^4 \cdot 3^5 \cdot 4^6 \cdot 6^7$. How many natural-number factors does $n$ have? I'm not quite sure how to go about solving this problem; there seems to be a lot of overcounting involved.
3
votes
1answer
173 views

How many natural numbers less than $10^8$ are there, whose sum of digits equals $7$?

How many natural numbers less than $10^8$ are there, whose sum of digits equals $7$? I got it here.But is there any more effecient and easier way to solve than the link shows?
0
votes
3answers
80 views

How to show that $A_k=(-1)^k\binom nk$?

In the identity $$\frac{n!}{x(x+1)(x+2)\cdots(x+n)}=\sum_{k=0}^n\frac{A_k}{x+k},$$prove that $$A_k=(-1)^k\binom nk.$$ My try: The given identity implies $$\frac{1\cdot2\cdots ...
2
votes
2answers
45 views

Estimate the number of ants in a colony

A friend of mine gave me this weird problem I cannot solve. To estimate the number of ants in a colony an entomologist draws 5500 ants randomly from the colony, labels them with a radioactive isotope ...
0
votes
1answer
31 views

The number of ways of going up 7 steps …

The number of ways of going up 7 steps if we take one or two steps at a time is ? So its essentially asking in how many ways can we make use of numbers of (1,2) to get a sum of 7. Am I wrong up till ...
-1
votes
3answers
64 views

In how many ways can you choose three distinct numbers … [closed]

In how many ways can you choose three distinct numbers from the set of {1,2,3,...,19,20} such that their product is divisible by 4 ?
2
votes
3answers
45 views

Combinatorics question: Boys and Girls around table

In how many ways can 4 boys and 4 girls sit around a circle table if each boy sits between two girls? (Rotations of the same arrangement are still considered the same. Each boy and girl is unique, ...
1
vote
1answer
42 views

How to calculate the number of lattice points in the interior and on the boundary of these figures with vertices as lattice points?

We define a point $(x,y)$ in the plane to be a lattice point if both $x$ and $y$ are integers. Now let $$S\colon= \{ (x,y) \ | \ 0 \leq x \leq m, \ 0 \leq y \leq \frac{nx}{m} \}, $$ where $m$ and ...
-2
votes
3answers
50 views

How many digits… [closed]

How many $3$ digit numbers of distinct digits can be formed by using the digits $1,2,3,4,5,9$ such that the sum of the digits is at least $12$ ?
0
votes
2answers
41 views

Find how many of these $4$-digit numbers are even. [closed]

(a) (i) Find how many different $4$-digit numbers can be formed from the digits $1, 3, 5, 6, 8$ and $9$ if each digit may be used only once. I did this; the answer is $360$; I used ...
1
vote
1answer
36 views

Maps preserving roots of a polynomial function over finite fields

Let $P(x_{1},\ldots,x_{n}):\mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}$ be a polynomial function with degree $d$ and with variables $x_{1},\ldots,x_{n} \in \mathbb{F}_{2}$. Let $S(P)=\{ ...
1
vote
1answer
14 views

Eccentricity of vertices in a graph when eccentricity of one vertex is given

I have a very basic doubt. If a vertex in any graph has the eccentricity two, then what can be concluded about eccentricities of other vertices in graph. Is the eccentricity of every vertex is less ...
1
vote
1answer
21 views

Number of arrangement

Problem: What is the formula of number of arrangements? More specifically I need to avoid repeated elements and the order of the sequence does not matter. For lucidity I show an example: For 3 ...
0
votes
1answer
49 views

Sort of Binomial Expansion

I was trying to find a general formula for expanding the product: $$\prod_{i=1}^k (a+ib)$$ where $a, b \in \mathbb{R}$. The first few expansions are as follows: $$\prod_{i=1}^1 (a+ib) = a + b$$ ...
-2
votes
1answer
39 views

Expected Value Question Intermediate [closed]

Mila has four ropes. She chooses two of the eight loose ends at random (possibly from the same rope) and ties them together, leaving six loose ends. She again chooses two of these six ends at random ...
7
votes
2answers
186 views

Rearrangement of dinner guests

A dinner host wants his guests to move, between main course and dessert, so that everyone gets a complete set of new neighbours. Guests are seated either side of a long table. Most guests have five ...
0
votes
1answer
55 views

Find the number of sets $X$ which can be formed by the number $n$

Find the number of sets $X$ which can be formed by the number $n$ where $X=\{a,b,c\}$ and $a+b+c=n$. $a,b,c$ are natural numbers and so obviously $n$ is also a natural number. $n>2$
1
vote
1answer
83 views

Looking for a bijection between this set and natural numbers

I am a computer programmer, and I am struggling with this mathematical problem without finding a consistent and efficient solution. Let $A_{k, M}$ be the set of all the possible assignments for $n_1, ...
-1
votes
0answers
44 views

Count suggestions to be send

A site currently has N registered users. As in any social network two users can be friends. We wants the world to be as connected as possible, so we want to suggest friendship to some pairs of users. ...
2
votes
2answers
112 views

seventeen tiles on a torus

The torus $\mathbb{R}^2 \mod((4,1),(1,-4))$ has area 17. Can it be covered by seventeen labelled tiles in two different ways so that any pair of tiles is neighbours of each other (at an edge or a ...
1
vote
1answer
133 views

What is the count of the strict partitions of n in k parts not exceeding m?

Lets say we had a $k,m,n \in \mathbb{N}$ where $k < m \le n$. How many different sets $X_1,..,X_m$ with $|X_i|=k$ for $i=1,..,m$, where the sets do not include duplicates, for which the sum of ...