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
11 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
1answer
11 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
0answers
10 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 ...
1
vote
1answer
17 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
1answer
31 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
22 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
30 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
60 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 ...
0
votes
1answer
13 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
2answers
19 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 ...
6
votes
1answer
66 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
18 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 ...
0
votes
1answer
40 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
101 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 ...
2
votes
3answers
51 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.
3
votes
5answers
85 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 ...
4
votes
3answers
67 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 ...
3
votes
1answer
55 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 ...
0
votes
1answer
36 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$ ...
1
vote
1answer
32 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
24 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 ...
1
vote
1answer
50 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 ...
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
3answers
47 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
3answers
111 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 ...
2
votes
2answers
43 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
26 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 ...
2
votes
3answers
43 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, ...
0
votes
3answers
61 views

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

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 ?
0
votes
1answer
32 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 ...
-2
votes
3answers
47 views

How many digits… [on hold]

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$ ?
1
vote
1answer
34 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
20 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 ...
-2
votes
1answer
18 views

How many binary strings are there of length n with k ones? [on hold]

For some fixed $n$, how many binary strings are there with $k$ $1$s and $n-k$ $0$s (where $n>k$)?
3
votes
1answer
45 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 & = & ...
-2
votes
1answer
30 views

Expected Value Question Intermediate [on hold]

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 ...
0
votes
0answers
41 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 ...
1
vote
1answer
72 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
43 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
1answer
35 views

Counting overlapping figures

How many four-sided figures appear in the diagram below? I tired counting all the rectangles I could see, but that didn't work. How do I approach this?
0
votes
1answer
46 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$$ ...
1
vote
0answers
51 views

Number of ways to make first move

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
0
votes
0answers
30 views

Since infinity is an element of the extended real line. Possible to count to infinity.? [on hold]

So if I take a subset of the extended real line (1, infinity+). Now can I count to infinity?
0
votes
0answers
56 views

Balls and Boxes [on hold]

How many ways are there to put 6 balls in 3 boxes if: a)the balls are not distinguishable and neither are the boxes? b)the balls are not distinguishable but the boxes are? c)the balls are ...
3
votes
1answer
163 views

What is this myth/legend and origin of related ideas?

There is a story I recently heard but the story teller (who read about it someone on the Internet) have forgotten the majority of the story, so there is little I can work on: my search attempts went ...
1
vote
1answer
51 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
0
votes
0answers
49 views

Sums with k dice

I have n dice, each with k sides, numbered from 1 to k inclusive. I want to find in how many ways I can get a sum of x using those dice. Doing some research, I found that what I am looking for is ...