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
2answers
25 views

Number of possibilities arranging $k$ balls in $t$ cells.

What is the number of possibilities arranging $k$ balls in $t$ cells, where: More then one ball in a cell is allowed. balls are different (e.g. every ball has a unique color). I understood the ...
4
votes
2answers
158 views

Is it possible to be “too good” at Spider Solitaire?

There was a similar question here: Losing at Spider Solitaire However, what I'm asking is different. The game has a rule that it would not deal the next ten cards, unless there is already a card in ...
2
votes
1answer
37 views

simple combinatorics question - what did I do wrong?

I was asked the following question. I solved it, I thought my solution is correct, but it turns out I was mistaken, I'd like to know why. Question: How many ways are to order 4 sets $(A,B,C,D)$ such ...
4
votes
0answers
321 views

Counting simple quadrilaterals in a rectangular lattice.

I've been trying to make an algorithm to find the number of all possible simple quadrilaterals in a N*M lattice. I already have a brute force solution but since this is a Project Euler problem I ...
1
vote
1answer
55 views

Combinatorics - possibly pigeon hole, 100 by 100 matrix with numbers from 1 to 100

We are given a $100$ by $100$ matrix. Each number from $\{1,2,...,100\}$ appears in the matrix exactly a $100$ times. Show there is a column or a row with at least $10$ different numbers. I'd like a ...
0
votes
1answer
48 views

What kind of formula would I use to get all possible outcomes?

I am into a CCG, and I got a question come to mind "how many possible out comes are there for deck combinations?" The game is broken into three: Main Character (6 cards available, only one deck), ...
1
vote
2answers
79 views

Calculating how many integers are between $0$ to $9999$ that has all of the digits $2,5,8$

Calculate how many integers between $0$ to $9999$ that has the digits $2,5,8$. That is integers that has each of the three numbers at least once. This is similar to How many numbers between $0$ ...
1
vote
4answers
52 views

Subsets and combinatorics

Let $A = \{1,\ldots,n\}$. Also, consider $y$, a subset of $A$ with the size of $k$. What is the number of subsets, such that $x \subset y$ ($x\ne y$). I know the answer is $2^k-1$, but cannot ...
3
votes
2answers
84 views

recursion-consecutive numbers

what is the number of subsets of the set {k∈N|1≤k≤n} with no two consecutive numbers? The answer says: $$a_n=a_{n-1}+a_{n-2}$$ with the starting conditions: $$a_0=1, a_1=2$$1. why does $a_1=2$? $$$$ ...
0
votes
1answer
74 views

Product formula for $\sum_{k=0}^n\frac{(-1)^k}{2k+1}\binom{n}{k}$ [duplicate]

How to prove the following identity: $$\sum_{k=0}^n\frac{(-1)^k}{2k+1}\binom{n}{k}=\prod_{k=1}^n\frac{2k}{2k+1}$$
2
votes
1answer
105 views

Pick balls of unequal weights from a given set of balls

It all started with this Q: There are 8 balls. Four of them weigh X grams each, and the other four weigh Y grams each. Your task is to find two balls having different weights. You have a ...
-1
votes
1answer
98 views

Integer linear combinations of coprime integers

Consider the finite set $S=\{s_1,s_2,\dots,s_n\}$ such that $GCF(s_1,s_2,\dots,s_n)=1$. Show that $\exists n$ such that $n$ cannot be written as $n=c_1s_1+c_2s_2+\dots+c_ns_n \forall c_i,s_i \in ...
-1
votes
1answer
85 views

Proving Big O(1) [closed]

How do I determine if the below is true or false? \begin{equation} 17^{100} + \frac{1}{n} = O(1)? \end{equation} I have tried using the c and No method but still can not come up with a solution.
1
vote
1answer
43 views

Maximum Number Of Points (Combinatorics)

The problem is like the following. Let $n$ blue lines, no two of which are parallel and no three concurrent, be drawn on a plane. An intersection of two blue lines is called a blue point. ...
2
votes
1answer
73 views

Finding the super-mean (NOT the mean) of a set of numbers.

the super-mean is found by grouping pairs of numbers and finding the average successively until there is just one number. For example, $$(1-2-3-4-5) \to ((1+2)/2,(2+3)/2,(3+4)/2,(4+5)/2) \\ ...
3
votes
1answer
52 views

How many six digits numbers are there such that composed by $2,3,9$ and can be divided by $3$

How many six digits numbers are there such that composed by $2,\ 3,\ 9$ and can be divided by $3$ ? Answer: $225$. I know the divisibility rule for $3$ tells: if a number can be divided by $3$ ...
4
votes
0answers
81 views

What do combinations of non-integers actually represent?

I understand that a combination is a way of selecting a finite number of things out of a larger group, in which the order of elements do not matter. That is all fine. But, in my Mathematical Reasoning ...
0
votes
1answer
42 views

Proving Big Θ of summations with exponentials

I have been working on this problem but have had a hard time understanding how to prove it as True, which I believe it is. ...
0
votes
0answers
32 views

Variants of sudoku that require very little give aways

Consider the following generalization of sudoku (it might already exist under a different name, any reference is welcome): Let $n$ be a natural number. By a generalized sudoku I understand a ...
1
vote
1answer
37 views

Largest K-multiple free set out of a fully ordered set

i'm struggling conceptually with this problem, i don´t know how to approach it in a clever way (without a computer, or at least without a brilliant algorithm). Mathematicians defined a k-multiple set ...
2
votes
0answers
82 views

Number of connected bipartite graphs with maximum possible degree

Is there a formula which gives the number of connected bipartite graphs with $n$ vertices such that the degree of every vertex is at most $d$? I can determine the results computationally using nauty, ...
3
votes
1answer
55 views

Coefficients in Pochhammer Expansion

Can anyone tell me if there is a formula for finding the coefficient of $x^3$ in the expansion of $(3x+5)_{6}$, where $(a)_n$ denotes the Pochhammer symbol, i.e. $(a)_{n}=a\cdot(a+1)\cdots(a+n-1)$? ...
2
votes
0answers
32 views

A question regarding binomial coefficient

This question arose during solving an information theory problem. Suppose $l$ is the smallest integer such that $$2^l\geq {n\choose k}$$ define $\rho=\frac{k}{n}$. How we can characterize $\rho$ as a ...
2
votes
2answers
112 views

Collection of independent sets equal to downset?

I have been struggling with the following problem. Every set here is supposed to be finite. If we have a closure $\lambda$ on $X$, we define the collection of independent sets of $X$ as $$ I_\lambda ...
2
votes
3answers
66 views

How many different triangles with at least a $3$ vertex side in a $3 \times 3$ vertex grid?

Say we have $3 \times 3$ vertex grid like so: * * * * * * * * * How many triangles exist so that at least one of their sides passes through 3 ...
0
votes
2answers
28 views

How many combinations are there for $(a,b,c)$ where $a, b, c$ are from the Natural numbers and $a < b < c < N$ for some chosen $N$?

How many combinations are there for $(a,b,c)$ where $a, b, c$ are from the Natural numbers and $a < b < c < N$ for some chosen $N$? I wanted to see what's an elegant counting argument for ...
0
votes
2answers
87 views

Choosing people around a circular table

There are 20 people around a circular table.We have to choose $3$ of them such that at least $2$ of them are sitting together.In how many ways can this be done? Number of ways of choosing 3 people ...
1
vote
3answers
133 views

number of ordered pairs to get a = c mod 3 and b = d mod 5

What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a,b) and (c,d) in the chosen set such that a = c mod 3 and b = d mod 5. ...
5
votes
1answer
192 views

Sequence where the sum of digits of all numbers is 7

BdMO 2014 We define a sequence starting with $a_1=7,a_2=16,\ldots,\,$ such that the sum of digits of all numbers of the sequence is $7$ and if $m>n$,then $a_m>a_n$ i.e. all such numbers are ...
0
votes
2answers
82 views

Permutations versus combinations, order or unordered (problem submitted).

A tourist wants to visit six of America’s ten largest cities. In how many ways can she do this if the order of her visits is (a) important, (b) not important? For part (a), I believe the answer is a ...
2
votes
2answers
117 views

How many $7$ digits number can be made?

How many $7$ digits number can be made with $1,2,3,4,5,6,7$ so that they are divisible by $11$? (Repetition is not allowed.) I know the divisibility rule of $11$, so the main problem is counting.
2
votes
2answers
305 views

How many ways can you order 1,2,3,4,5 without any consecutive numbers touching?

Permutation without consecutive numbers, such as 1,2 or 5,4?
0
votes
1answer
838 views

How many triangle can be drawn with those points? [duplicate]

There are 7 points on the circumference of a circle.How many acute triangle can be drawn with those points. please help me to solve this problem.
2
votes
1answer
37 views

Combinatorics Question - Permutations while fixing cases

Here is the wording of my question: In how many ways can a class with 20 students (12 boys and 8 girls elect a class president, vice president, and secretary if each student is willing to serve in ...
1
vote
1answer
55 views

Number of Contiguous Arrangements of Four Books out of Twelve

Twelve distinct books are lined up on a shelf. If four of the books are blue, how many arrangements of the books, have all four blue books together? I don't know if my answer is right but is it 8 ...
1
vote
3answers
45 views

3Sum problem explanation

I'm working through an Algorithms course online, and they don't explain the below math enough for me to understand. The code is a simple example for calculating the 3sum problem. The part I don't ...
0
votes
2answers
97 views

Perturbation Sums Question

I'm taking a discrete structures class and I would appreciate some help with a homework problem. The problem is Attempt to find a closed form for the sum $\displaystyle \sum_{k=1}^n k^3$ by ...
2
votes
1answer
135 views

Ways to put $5$ balls in $3$ boxes if each box must contain at least $1$ ball.

How many ways can you put $5$ balls in $3$ boxes if each box must contain at least one ball? I've some doubts about this issue, I think the solution is related to the second kind of Stirling ...
2
votes
3answers
110 views

What is the number of ways to represent the $n$ element set as a union of distinct non-empty subsets

edit: I do not mean the number of partitions $B_n$ here. The title says it all. The n element set is $[n]=\{1,2,\dots,n\}$. One representation (the one using the most sets) for example is the union ...
2
votes
1answer
78 views

Maximal number of kings on a chessboard, but this time two can be adjacent.

How many kings can be placed on an $8 \times 8$ chessboard such that every king can capture (is adjacent to) at most one other king? I can do 26, but can not prove that this is optimal.
3
votes
1answer
192 views

The library with 999 books.

In the town of Capibara there is a library with books in 999 themes. Since Capibara is an international town they have books in various languages. We know that for every language we can find exactly ...
0
votes
1answer
218 views

Project Euler #453 confusion

So I decided to give a shot on the #453 project euler problem but there is something that confuses me with the numbers given. I decided to start by calculating the possible arrangements of 4 vertices ...
2
votes
1answer
45 views

Generating Eulerian digraphs/isographs

I would like to be able to quickly generate (all) non-isomorphic isographs (that is, digraphs where each node has the same indegree and outdegree - also called "balanced networks" in the distributed ...
0
votes
1answer
98 views

Prove that the set of all grammatical sentences is denumerable

Prove that the set of all grammatical sentences of English is denumerable(Hint: Every grammatical sentence of English is a finite sequence of English words. First show that the set of all grammatical ...
0
votes
0answers
23 views

Proving that any sufficiently large sequence of vectors has zero-summed subsequence

Given $k,d$ I want to prove that any sufficiently large sequence of vectors over ${\pm 1, 0}$ whose sum is in $[-k,k]^d$ has a nonempty proper subsequence whose sum is $\bar 0$. Using probabilisitic ...
1
vote
1answer
54 views

Variance of Height of Tree

What is the asymptotic variance of the height of rooted plane trees (ie rooted, unlabelled, ordered trees with unbounded node degree) and of ordered binary trees (ie rooted, unlabelled, plane trees, ...
0
votes
1answer
49 views

An old counting problem in combinatorics

W.S.B. Woolhouse in 1844 posed the following problem in the Lady's and Gentlemen's Diary: Determine the number of combinations that can be made out of $n$ symbols, $p$ symbols in each; with this ...
1
vote
1answer
37 views

What is the maximum number of iterations before a sequence is repeated

$A = \{a,b,c,d,e\}$ $B = \{f,g,h\}$ $C = \{i,j\}$ $D = \{0,1,2,3,4,5,6\}$ Suppose a four-tuple is constructed by extracting one element from each set at each successive iteration. The stipulation ...
2
votes
2answers
61 views

Describing the pattern in which iterations make two, cyclic sets equal

$A = \{a,b,c,d,e\}$ $B = \{a,b,c\}$ $C = \{0,1,2,3,4,5,6\}$ The first few iterations are as follows: $1.$ $a,a,0$ $2.$ $b,b,1$ $3.$ $c,c,2$ $4.$ $d,a,4$ $5.$ $e,b,5$ $...$ I'm trying to ...
1
vote
2answers
101 views

In how many ways $3$ different rings can be worn in $4$ fingers with at most one in each finger?

In how many ways 3 different rings can be worn in 4 fingers with at most one in each finger?