For 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
2answers
2k views

how many different numbers are there with 3 digits and that add up to 19?

Hi I can't figure out if there is a fast way to calculate how many different numbers are there with N(3) digits that add up to M(19) allowing leading 0 (if they add up to 15, 069 is a proper ...
1
vote
1answer
213 views

Combinatorics-Find number of ways we can select cells from a nXn grid such that the number of cells selected from each row and column is odd

Find number of ways we can select cells from a nXn grid such that the number of cells selected from each row and column is odd. Any hints?
0
votes
1answer
24 views

Determining number of chimeras made of three cell types from two individuals

Chimeras are made of three main cell types, A, B and C. Each cell type can come from individual 1 or individual 2. How many different chimeras are there and what formula do you use to figure this out? ...
2
votes
1answer
92 views

Throw dice, what does this mathematical expression mean in real life?

Assuming we have a dice and the event that if we throw dice for the k-th time and get a 6 is given by $A_k$, is there an actual explanation what $A:= \cap_{i=1}^{\infty} \cup_{j=i}^{\infty} A_j$ is?
1
vote
1answer
77 views

2 regular graphs and permutations

I have found this question on MSE before but I didn't find the answer satisfactory and it is so old I doubt anyone is still following it. Let $f_{n}$ be the number of permutations on $[n]$ with no ...
2
votes
2answers
51 views

combinatorics simplie problem

How many ways are there to distribute $18$ different toys among $4$ children? without restrictions if $2$ children get $7$ toys each and $2$ children get $2$ toys each. For $1$ since toys are ...
0
votes
1answer
60 views

Can this famous theorem extended to the weighted undirected graphs?

There is well-known bound on the largest eigenvalue of graphs that says $$\sqrt{d_{max}}\leq \lambda_{max}$$. Is it also true for weighted graphs? (Where as usual, the degree of a vertex in a weighted ...
3
votes
2answers
199 views

Is it possible to prove $\sum_{k=0}^n \binom{n\vphantom{k}}{k} \binom{k}{m} = \binom{n\vphantom{k}}{m} 2^{n-m}$ combinatorially?

$$\sum_{k=0}^n \binom{n}{k} \binom{k}{m} = \binom{n}{m} 2^{n-m}$$ So for the proof, I have to use a real example, such as choosing committees, binary sequences, giving fruit to kids, etc. I have been ...
2
votes
3answers
464 views

Baseball Roster Optimization

I'm trying to programmatically optimize a Fantasy Baseball Roster that requires a fixed number of players at position (2 Catchers, 5 Outfielders, etc.) and has a salary constraint (total draft price ...
1
vote
3answers
232 views

Evaluate the sum of cubes

Evaluate $1^3 + 2^3 + 3^3 + . . . + n^3.$ Can I get a hint? I'm really stuck and don't know how to break this problem down.
2
votes
1answer
154 views

Does the Thue-Morse sequence form a Sturmian Word?

Does the Thue-Morse sequence form a Sturmian Word? The Thue-Morse sequence 011010011001001..., formed by appending the negation of the existing string, yields the ...
0
votes
1answer
199 views

Evaluating a sum with binomial coefficients

I have come across the following sum evoking the binomial theorem: $$\sum_{k=1}^n {n \choose k} \frac{1}{k^r} a^k b^{n-k},$$ where $r > 0$ is a positive real constant and $a,b \in \mathbb{R}$ are ...
3
votes
2answers
160 views

Pigeonhole Principle - numbers between $1$ and $100$

Of the set $A=${$1,2,...,100$}, we will choose $51$ numbers. Prove that, among the $51$ chosen numbers, there are two such that one is multiple of the other My notes: 1) There are $25$ prime numbers ...
0
votes
1answer
30 views

Number of triplet

How many triplet $(a,b,c)$ in $Z_{100}$ for which $ (a+b) \bmod 100 =0, a \neq 1, a\neq 2, a \neq (3+c) \bmod 100, c \neq 98, c \neq 97$? I want to calculate theoretically.
1
vote
2answers
1k views

Probablity a randomised four digit number does not have two specific consecutive numbers

I am trying to work out the probability a four digit number does not have two consecutive numbers, for example two consecutive 5's, not starting with a 0 is assumed. Now I could work out how many ...
1
vote
1answer
229 views

Probability of a 5 card hand from a standard 52 deck containing all 4 suits

The answer to this is $\dfrac{4 {13 \choose 2} {13 \choose 1} {13 \choose 1} {13 \choose 1}}{ {52 \choose 5}}$, but what I'm trying to figure out is why $\dfrac{{13\choose 1}{13\choose 1}{13\choose ...
1
vote
0answers
106 views

Number of ways to decompose the space $\mathbb F^n_2$ into a direct sum of two spaces

How many ways can $\mathbb F^n_2$ be decomposed into a direct sum of two subspaces? Basically how do I find the number of decompositions $\mathbb F^n_2 = \mathbb F^k_2 \bigoplus \mathbb F^{n-k}_2$ ...
6
votes
3answers
914 views

How many 3-subsets of $\{1,2,\ldots,10\}$ contain at least two consecutive integers?

Let A = {1, 2,..., 10}. How many three-element subsets of A contain at least two consecutive integers? I believe there are $\displaystyle \tbinom{10}{3}$ total 3-subsets of A. To find the subsets ...
0
votes
1answer
80 views

Given a lattice path, how do you define it as a subset of some larger set?

So it's clear that the total number of shortest routes in a lattice path given a $mxn$ grid is $\binom{s}{r}$ where $s$ is the total number of steps, and $r$ is the total number of right steps. But ...
0
votes
1answer
495 views

Antichain Proof

Let $S=\{1,2,3,4\}$. Consider the power set $\mathcal P(S)$ as a poset under the usual subset ordering. Prove that the only antichain of $\mathcal P(S)$ of size $6$ is the antichain of all ...
7
votes
1answer
262 views

Finding the $n$th term of a particular sequence

I have a sequence on $\mathbb{N}\times\mathbb{N}$ whose $n$th term I wish to find out. In fact, any information regarding this sequence will be helpful. The sequence is denoted as ...
0
votes
1answer
605 views

basic combinatorics(permutations) question

How many ways are there to seat six different boys and six different girls along one side of a long table with $12$ seats? How many are ways if boys and girls alternate sits? MY try: For first ...
2
votes
3answers
628 views

Project Euler's Problem Number 88

I am tackling Project Euler's problem number 88, which in a nutshell reads: Let $S_n$ be the set of sequences of natural numbers $(s_1,s_2,...,s_n)$ where $s_1\leqslant s_2\leqslant\cdots\leqslant ...
0
votes
1answer
49 views

Selecting elements with constraints

There is the set of potential facilities that we consider to build: $\{H_i|1\leq i\leq m\} \cup$ $\{V_j|1\leq j\leq m\} \cup$ $\{D_{ij}|1\leq i,j\leq m\}$ Due to certain geographic constraints, ...
0
votes
1answer
61 views

Ordinary generating function question

Let $a_1\le a_2\le\cdots\le a_6$ and $b_1\le b_2\le\cdots\le b_6$ be positive integers, not necessarily distinct, such that $a_1+a_2+\cdots+a_6<b_1+b_2+\cdots+b_6$. When the $36$ sums $a_i+b_j$ ...
0
votes
2answers
43 views

Variance problem with probability

Three cards are drawn sequentially from a deck that contains 16 cards numbered 1 to 16 in an arbitrary order. Suppose the first card drawn is a 6. Define the event of interest, A, as the set of all ...
1
vote
2answers
45 views

Ways to give 3 tickets to the cinema to 37 students: $P_{3,37}$ or $C_{3,37}$?

I think I have found a mistake in the task in the book and I am trying to figure out if that is true. There are thirty seven students in the class. Three tickets to the cinema will be given to ...
0
votes
3answers
131 views

Probability and combinations question

Find the probability that a poker hand of 5 cards from a standard deck will contain exactly 2 face cards (i.e. J,Q,K) (event A), given that it contains exactly 1 cards smaller than 8 (i.e. ...
0
votes
1answer
50 views

$(1+x+x^2)^n = \sum_{r=0}^{2n}a_{r}\cdot x^{r}$ and $\sum_{r=0}^{n}(-1)^r\cdot a_{r}\cdot \binom{n}{r} = k\cdot \binom{n}{\frac{n}{3}}$. Then $k=$

If $n$ is a multiple of $3$ and $\displaystyle (1+x+x^2)^n = \sum_{r=0}^{2n}a_{r}\cdot x^{r}$ and $\displaystyle \sum_{r=0}^{n}(-1)^r\cdot a_{r}\cdot \binom{n}{r} = k\cdot \binom{n}{\frac{n}{3}}$. ...
0
votes
1answer
50 views

$\sum_{k=0}^{2n}(-1)^k\cdot (k-2n)\cdot \binom{2n}{k}^2$ in terms of $n$ and $A$, is

If $\displaystyle \sum_{k=0}^{2n}(-1)^k\cdot \binom{2n}{k}^2 = A$, Then value of $\displaystyle\sum_{k=0}^{2n}(-1)^k\cdot (k-2n)\cdot \binom{2n}{k}^2$ in terms of $n$ and $A$, is $\bf{My\;Try}::$ ...
1
vote
2answers
150 views

Combinatorial Bijection?

I have the following problem, which seems pretty easy, but I'm not sure as to what exactly is meant by a combinatorial bijection. I know what a 'normal' bijection is. The problem and my work follows ...
0
votes
1answer
116 views

A few questions relating to counting for midterm practise exam?

I'm doing some questions for my midterm practise exam (multiple choice) for discrete structures and would appreciate some help (My answer is bolded): Using the 26-letter alphabet {a,b,c,...,z}, how ...
4
votes
2answers
125 views

Bound on graph edges

I need some help with the following problem. Suppose I have a graph $G$ of $n$ elements such that each edge $e$ missing from it, is contained in a copy of $K_s$ (complete graph os $s$ vertices) in ...
2
votes
2answers
416 views

Preforming Counting Permutations

Problem: A seven-person committee composed of Alice, Ben, Connie, Dolph, Egbert, Francisco, and Galvin is to select a chairperson, secretary, and treasurer. How many selections are there in which at ...
1
vote
1answer
102 views

Proving there are at least $N$ surjective functions from $A$ to $B$

Let $A = \{1,2,\ldots,m\}$; $B = \{1,2,\ldots,n\}$. I have to prove that there are at least $\frac{m!}{(m-n+1)!}$ surjective functions from $A$ to $B$. I've given it some thought, but I don't know ...
1
vote
1answer
25 views

Combinatorics of possible vectors with length 3 without duplicates

Suppose I have a vector with a length of 3. I have 6 choices. They are: 1a, 2a, 2b, 3a, 3b, 4a. Choices with the same beginning number cannot be on the same vector. For example, a vector with [ 1a, ...
0
votes
1answer
71 views

Partition of circumference into $3k$ arcs

The following problem is from 1982 Russian Mathematical Olympiad. If you go to this link, and scroll down to the section Russian Math Olympiad, then this is Problem 333 in that text-file. Let $k$ ...
1
vote
1answer
86 views

Pigeonhole Principle to solve question straightforward

A store wants to celebrate its anniversary and will give a $200 shopping certi cate to the first customer to enter the store whose birthday is the same as that of two other previously admitted ...
5
votes
1answer
171 views

Find asymptotic for $s(n)=\min\{m\in{\mathbb N}\mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$

I have some strange function: $s(n)=\min\{m\in {\mathbb N} \mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$ and I need to find asymptotics for it. I have a solution for this except one last step, I ...
-1
votes
1answer
80 views

Colouring Graphs

I need some help on this. Assume that we have ten colors to choose from. For each of the following questions, assume that the vertices are distinguishable. Where two adjacent vertices cannot be ...
1
vote
5answers
261 views

I have five eggs to color for Easter. I can color them red, yellow, or blue. How many ways are there to do this?

Not sure if my thinking is correct on this problem. I have five eggs to color for Easter. I can color them red, yellow, or blue. How many ways are there to do this? I was thinking 5 * 5 choose 3 ...
4
votes
0answers
86 views

Selecting k numbers out of N sorted numbers to a minimize a condition/Formula

A sorted list of $\mathbf N$ numbers is given. $X_1$ $\le$ $X_2$ $\le$ $X_3$ $\le$ .... $\le$ $X_N$ Select $\mathbf K$ Numbers - $Y_1$ , $Y_2$ , $Y_3$ , ..... , $Y_K$ - Such that the following ...
1
vote
1answer
275 views

Round robin schedule problem

I run two dart leagues. One with 8 teams and 4 boards and one with 6 teams and 3 boards. I have a perfect schedule for the 8 teams league but the 6 team one gives me a dilemma. I want the teams to: ...
1
vote
2answers
67 views

Probability of drawing 3 balls

A box contains 8 red, 3 white, and 9 blue balls. If 3 balls are drawn at random determine the probability that all 3 balls are red all 3 balls are white 2 are red and 1 is white at least 1 is white ...
2
votes
1answer
32 views

Balancing objects of varying length in a collection of set length while maintaining order

I have an object each with a length associated with it. I can then have multiple of these objects and I want to put them into another collection/array with a certain set count. Order matters and I ...
1
vote
5answers
216 views

When is round-robin scheduling possible and with in minimal time?

Suppose that you have six teams $x_0, x_1, x_2, x_3, x_4, x_5$. Can you schedule round-robin games between them so that if one game is played each day, the series of games can be completed in five ...
3
votes
1answer
86 views

Inverting a binomial sum

Fix $n.$ Suppose I have two sequences of positive integers $a_k$ and $b_k$ that vanish for $k>n$ and satisfy the following relation: $$ a_k = \sum_{i=k}^n (-1)^{i-k} \binom{i}{k} b_{n-i}.$$ I ...
1
vote
1answer
161 views

Number of arrangements for a varying number of Balls in N colors

Let $N\in\mathbb{N}$ be a number of colors. For each of these colors let $a_k$ be the number of indistinguishable Balls in the specific color. How many arrangements of balls can I find, when I am ...
1
vote
1answer
44 views

Combination Beads

There are $4$ beads: white, blue, green, red. I can have at most $8$ beads. Each sequence of up to $8$ beads indicate a different message. It can have repeated elements. A) What are the number of ...
2
votes
1answer
531 views

Number of ways to partition a set with $n$ elements to $k$ subsets where at least one subset has $r$ elements

I'm familiar with Stirling numbers of the second kind to compute the number of ways to partition a set with $n$ elements into $k$ non-empty, disjoint subsets. However, there are combinations which I ...