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
1answer
43 views

Set Questions? Need someone to help show

I tried doing these and I have the answers, but I can only do A. Can someone show me how to do the rest? I have the answers but don't know how to get to them..
1
vote
2answers
68 views

How to prove this identity [closed]

I would like to prove the following identity without using induction: $$\sum _{ k=1 }^{ n }{ { (-1) }^{ k } {n\choose k} }\cdot k^n=(-1)^n\cdot n!. $$
1
vote
1answer
75 views

A committee requires one accountant, two marketing agents..

A committee requires one accountant, two marketing agents, and four board members. If there are four accountants, three marketing agents, and seven board members available for selection in the ...
2
votes
2answers
2k views

Number of non-decreasing sequences

How do I find the number of non-decreasing sequences of length $N$, such that all number in the sequences lie in the range $[a, b]$. Also, the frequency of the most frequently occurring element should ...
1
vote
0answers
157 views

Parking Functions and the Binomial Theorem

A parking function is a function $f: \{1, \ldots n\} \rightarrow \{1, \ldots n\}$ which has the property that the list $(f(1), f(2), \ldots f(n))$ can be rearranged in some order $(a_{1}, a_{2}, ...
1
vote
1answer
57 views

Number of ordered quadruples

How many ordered tuples $(x_1,x_2,x_3,x_4)$ exist such that $$ \begin{align} L_1\le & x_1\le R_1 \\ L_2\le & x_2\le R_2 \\ L_3\le & x_3\le R_3 \\ L_4\le & x_4\le R_4 \\ x_1 & \neq ...
4
votes
2answers
533 views

simple games with cute winning strategies?

Im thinking of games of two players ($A$ goes first and $B$ second) like the following: There are 35 chips in a table, during each turn a player can remove 1,2,3 or 4 chips. Prove player $B$ can ...
1
vote
2answers
67 views

Is there a standard recurrence relation to solve this?

I have infinite supply of $m\times 1$ and $1\times m$ bricks.I have to find number of ways I can arrange these bricks to construct a wall of dimensions $m\times n$. My problem is how can I approach ...
0
votes
1answer
53 views

Different combinations

I have the following problem : On a digital watch there are only finitely many different times that can be displayed. How many different times can be displayed on a digital watch that shows hours, ...
0
votes
1answer
76 views

Combinatorics: help with the Inclusion-exclusion principle

$A=\{1,2,3,4\}$ $B=\{5,6,7,8,9\}$ $K$ is a relation from $A$ to $B$ ($K\subseteq AXB)$ in how many $K$'s - $1 \notin domain(K)$ ? in how many $K$'s - $\{1,2,3\}\subseteq domain(K)$ (use the ...
0
votes
1answer
92 views

Complex Combinatorics Hexagon/Triangle Contest Problem

The problem is as follows: The six sides of convex hexagon $A_1A_2A_3A_4 A_5A_6 $ are colored red. Each of the diagonals of the hexagon is colored either red or blue. Compute the number of colorings ...
1
vote
2answers
37 views

How to prove that $n$ is prime if an $n$-Venn diagram has $n$-fold rotational symmetry

I was reading this article on "The Search for Simple Symmetric Venn Diagrams" by Frank Ruskey, Carla D. Savage, and Stan Wagon and on the first page page they prove that $n$ is prime if an $n$-Venn ...
2
votes
1answer
44 views

Need help with Combinatorics and change of variables.

I have this very frustrating question that I,ve been trying to solve for the past few hours now and it's killing me here. Basically,I solved the problem, but it's technically not the form we want ...
1
vote
1answer
145 views

Combinatorics pigeonhole principle question.

There are $n$ people at a meeting, each of whom chooses $3$ distinct numbers between $1$ and $11.$ $\quad({\sf a})$ What is the smallest value of $n$ which guarantees that at least two people choose ...
0
votes
1answer
53 views

Distributions of groups of similar objects arranged linearly and circularly

The following question is from this textbook (Section 2.5, p. 185). 8.A child has blocks of $6$ different colors c) if the child selects $4$ blocks of each color, in how many ways can these ...
2
votes
1answer
27 views

Corrective terms for combinations

Take: $12$ people need to be split up into equal teams for a quiz. How many ways can this be done? The answer may initially seem to be $\displaystyle \frac{12!}{6!6!}$. but, since a single grouping ...
0
votes
1answer
40 views

Is this in possible to do in graph theory?

the conditions are that vetex if G lies in the same connected components of G and every vertex has the same degree. The left hand side all have degree three except for two, so is this even ...
0
votes
1answer
109 views

Stirling number of the second kind recurrence relations

I am interested to understand why the following recurrence relations of the Stirling number so the second kind hold using counting arguments ...
2
votes
1answer
132 views

There are more functions from $T$ to $S$ than there are subsets of $T$

Question Let $S$ be the set of stars in our galaxy and let $T$ be the set of cars on earth right now. There are more functions $f:T\rightarrow S$ than there are subsets of $T$ . Solution ...
0
votes
1answer
28 views

Find the no. of edges of a graph G.

Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i,j):1≤ i ≤12 , 1≤ j ≤12}.There is an edge between (ܽa,b) and (ܿc,d) if |ܽa−ܿc| ≤1 and |ܾb−݀d| ≤1. What is ...
0
votes
1answer
44 views

Given a string containing 'a' and 'b', Find all permutations starting with 'a'

Given a string contains only a and b where a comes M times and b comes N times in the string. I need to compute all the permutation of the string starting with a. What is the most efficient way? Can ...
14
votes
2answers
386 views

A question about the minesweeper game

This is just out of curiosity. Suppose the game has $m \times n$ boxes for positive integers $m$ and $n$. How can we make the sum of the numbers on a finished game the most? There are two extreme ...
8
votes
4answers
299 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
93 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
67 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
80 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
39 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
263 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
1k 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?
2
votes
0answers
40 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
115 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
90 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
81 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
64 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
110 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
191 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
154 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
281 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
101 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
48 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
230 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
77 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? ...