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)

8
votes
4answers
293 views

Does $\sum_{k=0}^{k=n} {n \choose k} k!$ have a closed form for integers $k,n$?

While doing research in computer system, I came across the following summation: $$S_n = \sum_{k=0}^{n} {n \choose k} k! = \sum_{k=0}^{n} \frac{n!}{(n-k)!}$$ where both $n$ and $k$ are integers. $S_n$ ...
2
votes
1answer
91 views

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014.
0
votes
0answers
61 views

Number of combinations in a matrix

Given the size of a matrix is $N \times N$, how many unique matrices are there given the following restrictions: Matrix entries can only contain numbers $\left[0,b\right]$ A valid matrix cannot have ...
0
votes
1answer
75 views

Need help explaining vandermonde's identity combinatorially.

So I am trying to solve this identity, and I have found multiple answers to this, but all the answers are just copy/paste from wikipedia and no explanations are provided as to how to go from one step ...
1
vote
1answer
38 views

Show that a set defines a simplicial complex

Let $A_n := \left\{-n,\cdots,-1,1,\cdots,n\right\}$ $\Delta_n := \left\{ B \subseteq A \; \big\vert \; \#(\{-i,i\}\cap B)\leq 1 \; \forall 1 \leq i \leq n \right\}$ Show that ...
0
votes
2answers
45 views

Prove the following (Generating function)$\sum^{\infty}_{k=0}\sum^{\ell}_{i=n}\binom{2i}{k}=\frac{2^{2\ell +2}-2^{2n}}3.$

Prove the following: (use generating functions) n < L $$\sum^{\displaystyle\infty}_{k=0}\sum^{\displaystyle\ell}_{i=n}\binom{2i}{k}=\dfrac{2^{\displaystyle2\ell +2}-2^{2n}}3.$$
1
vote
2answers
258 views

if $f_{n}(x)=f(f_{n-1}(x))$then $f_{10}(x)=x,x\in [0,1]$

Define the function $f:[0,1]\to[0,1]$ by the following. $$f(x)=\begin{cases} x+\dfrac{1}{2},&0\le x\le\dfrac{1}{2}\\ 2(1-x),&\dfrac{1}{2}<x\le 1. \end{cases}$$ Let $f_1(x)=f(x)$ and ...
2
votes
0answers
59 views

Prove the following : [duplicate]

Prove the following : $$ {{n}\choose{7}}-\left \lfloor{\frac{n}{7}}\right \rfloor $$ is divisible by 7.
0
votes
5answers
871 views

How many different ways can these letters be arranged?

In how many different ways can the letters A, A, B, B, B, C, D, E be arranged if the letter C must be to the right of the letter D?
1
vote
0answers
36 views

Big-Oh for size of a Sperner family

I'm developing an algorithm that will generate a collection of subsets of a ground set having the property that no subset in the collection is a subset of any other, and I'd like to give a Big-Oh ...
0
votes
0answers
104 views

Find maximum combination between elements in multiple sets

Here is my problem: I have multiple ordered sets of different length and I want to find the maximum sum that conforms to a constraint (upper or lower bounded) using zero or one element from each set. ...
4
votes
2answers
87 views

Find a chance that intersection of power set entries is an empty set

We are given set $A = \{1,2, ...n\}$. $k$ entries picked from the power set of $A$. Task is to find probability that $A_1 \cap A_2 \space \cap \space... \cap \space A_k = \emptyset$. I came up with ...
0
votes
1answer
65 views

Generating function counting quaternary sequence.

I have the following problems: $1.$ Calculate the number of the n-digits Quaternary sequence containing even $"2"$ and $"1"$ and at least one $"3"$. (When a sequence is made by the digits $1,2,3,4$) ...
0
votes
1answer
35 views

Combinatorics: calcaulating number of sections of an hesse diagrem, (help with sigma).

in this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$ it has 12 sections. for the set $A$ with $k$ elements, $k>0$ find the numbers of sections in the hesse diagrem ...
1
vote
2answers
63 views

Combinations in discrete math help please

I have a question that needs some explaining and it has to do with two sentences that are supposedly asking different things, but to me I can't seem to find out why both sentences are different ...
1
vote
1answer
100 views

What is the probability distribution of Total Score if a dice is rolled n-times.

Assume dice is fair, and throws are independent. What are these distributions called? What is this branch of mathematics called? Details and background below More info: Playing with Maths after a ...
0
votes
1answer
31 views

Combinatorics question simple

If I have 100 people in a tennis tournament. I want to find the total number of combinations of matches of doubles. So P1&P2 on Team 1 vs P97&P98 on Team 2 count as ONE combination of matches ...
1
vote
2answers
24 views

Choosing Groups And Deleting Some

There will be 8 women and 6 men, we shell build a board including 3 women and 3 men, but there are 2 men that refuse to be on the board together. What I have thought that there are 2 options: 1. not ...
1
vote
4answers
181 views

Sum of $x^x$ final 10 digits

warning/spoiler alert this problem occurs in the euler project. I want to find the last ten digits of the following sum: $$ S = 1^1 + 2^2 + 3^3 + 4^4 + \cdots + 1000^{1000} $$ Finding this ...
0
votes
1answer
140 views

Stirling Number of the Second Kind (intuition for formula)

The Stirling number of the second kind is the way of putting $n$ objects into $k$ nonempty boxes. I would like to understand the right hand side of this equation by a counting argument $$S(n,k) = ...
2
votes
2answers
280 views

what is the probability that the selected function maps prime numbers to prime numbers?

Let $X = {1, 2, 3, . . . , 25}$. If a student selects a function randomly from the set of all functions from X onto X, then what is the probability that the selected function maps prime numbers to ...
3
votes
1answer
39 views

How many ways exist to group n ordered elements?

I am currently thinking about on-line handwriting recognition of mathematical formulas. On-line means that I get the information how the user writes. Assuming that the user writes one symbol after ...
3
votes
1answer
92 views

What is the smallest positive integer $ n $ for which $\frac{50!}{24^n}$ is not an integer?

We can go for a direct check! But it is too tedious! Is there any result that can be applied to find the answer.
1
vote
1answer
44 views

Find the rule of a sequence

I have a sequence $\{x(n), n=0,1,2,\ldots\}$ as follows: $x(0) = 1$ $x(1) = 1- e^{-a}$ $x(2) = \dfrac 12(1 - 4e^{-a} + 3e^{-2a})$ $x(3) = \dfrac{1}{6}(1-12e^{-a}+27e^{-2a}-16e^{-3a}) $ $x(4) = ...
1
vote
0answers
46 views

Counting problem (Combinatorics/Discrete math)

A restaurant has a menu containing 12 starters, 22 main courses. a) 7 friends visit. 5 have a starter, all 7 have a main course. How many ways to do this? - My answer: (12)5 x (22)7 (i.e. 12x11x...x8 ...
0
votes
1answer
205 views

Combinatorics: calcaulating options of valid password of length 5 or 6 from letters and numbers

I did the following excercise using the Inclusion–exclusion principle, that's how we should do that excercise, but the answer does not match my regular calcaulation, why? The user is required to ...
2
votes
2answers
73 views

Maximal subset $\{1,\dots,256\}$ with no pairs $x = 2y$

Let $A=\{1,\dots,256\}$. Find subset $A'\subset A$ with maximal elements s. t. there are no pairs $x=2y$. My attempt is kind "including excluding formula": $256-128+64-\dots$ First take only odd ...
0
votes
1answer
41 views

Fundamental principles of Counting help

So basically I need a kind mathematician to confirm something. Here is the question I failed at solving. Q: If there are two positive summands for 7, how many number of integer solutions are there? ...
1
vote
1answer
32 views

A general answer to the number of solutions to an inequality

Given the following inequality: $x_1 + x_2 + x_3 + .... + x_N < r$ we are asked to solve the number of non-negative integer solutions could the solution be described as: $\displaystyle ...
1
vote
3answers
98 views

How do I solve this Discrete Math problem in the picture? [duplicate]

I am basically stuck at the part where it says w1 + w2 = 7 is equal to the number of integer solutions of x1 + x2 = 5. After that I am not sure how the book got n = 2 and r = 5. I am mainly confused ...
2
votes
1answer
47 views

A bound on the balanced equipartition of a multi-set of integers

A balanced equipartition of a multi-set of $2n$ integers is a partition into two multi-sets $S_1$ and $S_2$ of size $n$ such that the sum of the integers in $S_1$ is as close as possible as the sum of ...
1
vote
1answer
45 views

Hanging pictures in the rooms

How many ways to hang 13 different pictures in 7 numbered rooms are there so that there is at least 1 picture in each room? So I tried to look at this from, say, each picture's perspective. So ...
0
votes
2answers
43 views

Given set of numbers, find what is x

hi can anybody help how to solve this 30, 32, 36 , X , 60, 92 what is X
1
vote
2answers
71 views

Probability: What is wrong with my approaches?

$4$ out of $20$ balls are black. The others are white. If I pick $2$ balls out of those $20$ randomly, what is the probability that at least one of them is white? I could do this using a ...
0
votes
1answer
41 views

How many $A \rightarrow B$ relation there is?

I have the following combinatorics problem I don't understand: $A$ is a set of size 2 and $B$ is a set of size 3. How many $A \rightarrow B$ relation there is? The answer is: 9 Why? Shouldn't it ...
9
votes
1answer
287 views

One-Line Proof for $n! \geq (\frac n e)^n$

I was told to find a one-line proof for $n! \geq (\frac n e)^n$. I'm advised that Stirling's formula is not helpful. I've spent a little bit of time on it, but the solution is not coming to me. I feel ...
6
votes
1answer
89 views

maximize a function which contains factorials

Suppose I have a function $$ f(k) = \binom{500}{k} \binom{500}{1100-3k}$$ where $k$ is an integer from $200$ to $366$. How can I find the maximum analytically?
1
vote
1answer
43 views

Discrete and Combinatorial Mathematics question

Can someone explain to me the area boxed below? I am particularly very interested in the explanation of how the book got (1 + 8)^50 because I have NO IDEA how to figure out that x = 1 and y = ...
12
votes
3answers
383 views

middle school olympiad combinatorics has me stuck

Michael has 2 spider-man toys,2 iron-man toys, 2 Thor toys and 2 Hulk toys. The toys representing the same characters are identical. In how many ways can he place his toys in a row so the number of ...
6
votes
2answers
2k views

A fair coin is flipped 2k times. What is the probability that it comes up tails more often than it comes up heads? [duplicate]

I'm studying for a probability exam and came across this question. I watched the video solution to it but I don't really understand it. I was hoping someone could explain this problem to me. Are there ...
5
votes
1answer
137 views

True? $\sum_{n=1}^\infty {n+m-1 \choose m}^{-1} = 1 + \frac {1}{m-1} $

Prove (or disprove) that for all positive integers $m>1$, $ \displaystyle \sum_{n=1}^\infty {n+m-1 \choose m}^{-1} = 1 + \frac {1}{m-1} $
-1
votes
2answers
62 views

How do I solve this Discrete Math problem?

With "$n$" being a positive integer, evaluate the sum : $C(n,0)+2C(n,1)+2^2C(n,2)+...+2^kC(n,k)+...+2^nC(n,n)$ Can someone teach me how to evaluate that using the binomial theorem? The ANSWER is $(1 ...
5
votes
2answers
247 views

Rooks in 3D chess board

How many rooks are needed for a 3D chess board of size NxNxN so that every empty cube on the board can be reached by a rook in a single move?
2
votes
1answer
295 views

Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states: [...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of ...
0
votes
1answer
33 views

Lotto question: 2 weeks with same numbers or 1 week with 2 different numbers

We are playing $90$ number lotto, where they draw $5$ number out of $90$. Is it better to play two different combination for one week or play same combination for $2$ weeks to win the lottery? My ...
4
votes
1answer
355 views

Different ways of Arranging balls in boxes

This question is generalization of different cases of combinatorics problems that are generally asked. We will find general way of arranging $n$ balls in $r$ boxes. Cases : Identical Balls. ...
0
votes
1answer
36 views

Choosing Couples From A Group

The is a Ballet group with 22 people 10 are women and 12 are men. we take 5 women and 5 men, and arrange them as couples how many options there are? What I did is ${ 12 \choose 5}+ { 10 \choose 5}$ ...
0
votes
1answer
59 views

Have to find the best possible combination

I'm trying to create a problem. I have two grades of tiles Medium Grade tiles at 180 cash each. Low Grade tiles at 150 cash each. I have with me 28000 in cash and I have to buy at least 160 ...
0
votes
1answer
23 views

Calculating number of functions

$f$ is a map defined on the set $\mathbf{F}_p$={0,1,2...p-1} to itself. The properties of $f$ are as follows: $f(x)\ne x$ for all non-zero $x$ from $\mathbf{F}_p$. There is exactly only one ...
1
vote
1answer
46 views

Granting Different Rewards For 30 People

If there are 30 people and 5 different rewards, how many possibilities are there if There are no limitations to the number of rewards per one Only one prize a person as for 2) we need to choose 5 ...