Tagged Questions

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 (5)

0
votes
1answer
8 views

Number of Distinct Elements in Set of Products of 2 Matrices

Let $X=\begin{pmatrix}\cos\frac{2\pi}{5} & -\sin\frac{2\pi}{5}\\\sin\frac{2\pi}{5} & \cos\frac{2\pi}{5}\end{pmatrix}$ and $Y=\begin{pmatrix}1 & 0\\0 & -1\end{pmatrix}$. Find the ...
1
vote
1answer
39 views

Counting and probability gift exchange problem

There are 50 people (numbered 1 to 50) and 50 identically wrapped presents around a table at a party. Each present contains an integer dollar amount from $1 to $50, and no two presents contain the ...
0
votes
2answers
75 views

Number of Ways to Break a Chocolate Bar

In how many ways can you break a off a rectangular piece of chocolate from a chocolate bar with m x n squares. [We must respect the structure of the chocolate bar, that is break only along horizontal ...
0
votes
2answers
31 views

Probability, why is this wrong? (Combinations and Permuations)

Why is this the wrong approach to solve this problem? "There are 65 students. 20 of them are sophomores, 20 are freshmen, 15 are juniors and 10 are seniors. When picking a 4 student committee, ...
1
vote
1answer
29 views

Ways in which 2k indices can be assigned so that every index is equal to at least one other

In trying to approximate a certain power of a sum, I wound up with this issue: There are 2k indices, $i_1, i_2, ..., i_{2k}$, each of which can take on any of the values {$1, 2, ..., n$}. I need to ...
-1
votes
2answers
37 views

Number of Pairs of Subsets

Find the number of Pairs(A,B) of subsets of[n] such that A ⊆ B? I just need clarification in my thought process. My professor's wording at times can through me off. I just want to know if i am on the ...
5
votes
1answer
89 views

Show that $n!^{n+1}$ divides $(n^2)!$

My attempt so far is by induction. Let $f(n) = \frac{(n^2)!}{n!^{n+1}}$, I will try showing that $f(n)$ is a positive integer for all $n$. We have $f(0) = \frac{0!}{0!^{n+1}} = 1$. Now assume for ...
3
votes
3answers
47 views

Probability 4 different numbers $ a, b, c , d$ are solution of $a+b=c+d$

Let $N=\{1,\ldots,n\}$ We choose $a$, $b$, $c$, $d$ - different random numbers from $N$. What is probability of $a+b=c+d$?
1
vote
0answers
38 views

Showing that the number of ways to cut a 200 x 3 board into 1 x 2 dominoes is divisible by 3.

Showing that the number of ways to cut a 200 x 3 board into 1 x 2 dominoes is divisible by 3. My only idea is to assume the opposite, make some needed arrangement, and to show that changing the ...
1
vote
1answer
24 views

N Boxes and M babies question.

There are N boxes placed in a straight line. Adjacent boxes are separated by 1 unit. The Babies which are a total of M in number decide to play in this arena of boxes by moving from one box to ...
1
vote
2answers
75 views

Selecting books on a shelf so that there are at least 3 unselected between any two selected books

How many ways are there to select $k$ out of $n$ books on a shelf so that there are always at least $3$ unselected books between selected books? (Assume $n$ is large enough for this to be possible.) ...
1
vote
1answer
18 views

distributing r distinct objects into n-distinct boxes when repetition is allowed

Suppose there are 5 students and we are trying to create 3 distinct commissions which every student must be in at least one commission and every commission must have at least 2 members. what is the ...
0
votes
1answer
23 views

combination tricky question

A sports team consists of $5$ bowlers (or pitchers), $9$ batsman and $2$ keepers (or back-stops). How many different teams of $11$ players can be chosen from the above squad if the team consists of ...
1
vote
2answers
55 views

Two hundred balls into one hundred boxes

We have distributed two hundred balls into one hundred boxes with the restrictions that no box got more than one hundred balls, and each box got at least one. Prove that it is possible to find some ...
2
votes
1answer
39 views

Help in finding $\lim_{n\to \infty}\left ( \sum_{k=1}^{n} \frac{1}{\binom{n}{k} } \right )^n$.

I am not able to get a solution for this problem . Of finding the limit $$\lim_{n\to \infty}\left ( \sum_{k=1}^{n} \frac{1}{\binom{n}{k} } \right )^n$$ I have tried using Mathematica and that ...
0
votes
2answers
34 views

What is the number of nonnegative solutions of a linear equation?

What is the number of solutions of a linear equation? for example look at this equation: $X_1+X_2+...+X_n=r$ The number of solutions is the following formula, because the way of choosing $r$ objects ...
-2
votes
0answers
27 views

Ways of representing the product of N numbers as sum of two squares [on hold]

Given N numbers, we need to tell the number of ways of representing the product of these N numbers as sum of two squares. Example : Let $N=3$ and numbers be $[2,1,2]$ then as $2*1*2=4$ There are 4 ...
0
votes
0answers
17 views

A question involving Partial Steiner Triple Systems

I've been given the following question, which I think I've completed, but I just wanted to check whether what I've said is valid. Suppose that a PSTS(23) with a $K_5$ leave is constructed using ...
0
votes
0answers
20 views

persons in group- combinatorical proof

Prove that in any group containing at least 10 people there are such four persons that they are familiar with each other or three persons such that, none of them doesnt know another.
0
votes
1answer
30 views

Element matrix multiplication representation

Matrix element by element multiplication defined : $C=A*B$ $c_{ij}=a_{ij}b_{ij}$ Is this multiplication can be represented with stardant matrix multiplication or Kronecker product ?
0
votes
0answers
28 views

Number of strings of length n generated using m different characters.

We need to find the number of sequences that can be made from m different characters (X0, X1, ...., X(m-1)). An array arr[m] of size m is given, ith element tells that character Xi should be used ...
0
votes
1answer
38 views

Positive Integer Solutions to an Equation with Individual Variable Constraints

Find the number of positive integer solutions to $ x_1 + x_2 + x_3 + x_4 + x_5 = 100 $ if $x_1 \le 30$, $x_2\le40$, $x_3\le50$, $x_4\le60$, and $x_5\le70$.
0
votes
0answers
23 views

Distribute Chocolates among m children Non Uniformly

Suppose person B has N chocolates,He has to distribute these chocolates non-uniformly among M children. Suppose child mi has weight Wi and the total weight is Wt. One way to do so is to distribute ...
1
vote
3answers
32 views

What is the formula for the sum of $^{n}C_{k}$ for fixed $k$ and varying $n$?

I am searching for a formula of sum of binomial coefficients $^{n}C_{k}$ where $k$ is fixed but $n$ varies in a given range? Does any such formula exist?
0
votes
1answer
44 views

The existence of two couples of dancers that did not exchange partners

At a homecoming dance, no boy dances with every girl, but each girl dances with at least one boy. Prove that there are two couples, gb and g'b', who dance, such that g doesn't dance with b' and g' ...
0
votes
1answer
8 views

Evaluating the $L_2[-1, 1]$ inner product on rescaled Legendre polynomials

Let $z_n(t) = \sqrt{\frac{2n+1}{2}} \frac{1}{2^n n!} \frac {d^n}{dt^n} (t^2-1)^n$, a rescaled Legendre polynomial. As an intermediate step of a larger problem, I need to show that in terms of the ...
0
votes
3answers
36 views

Combinatorial - how many ways to divide objects into two groups

As a part of a bigger problem I have to determine In how many ways $37$ different objects can be divided among two groups of $32$ and $5$ objects each if i) object $A$ and $B$ cannot belong to the ...
3
votes
0answers
24 views

Bound on number of breakable sets

Let $\mathcal{S}$ be a finite family of finite sets. A finite set $A$ is called breakable if for every $B\subseteq A$, there exists $S\in \mathcal{S}$ such that $A\cap S=B$. Show that at least ...
-1
votes
1answer
57 views

how many people are at the party

At a party, each person shakes hands with 5 other people. There are a total of 60 handshakes. How many people are at the party? i am lost because of the 60 hand shake that is mentioned.
1
vote
3answers
65 views

Show that a set of vectors is linearly dependent

Show that the set $S = \{(3, 2), (−1, 1), (4, 0)\}$ is linearly dependent by finding a nontrivial linear combination of vectors in the set whose sum is the zero vector. (Use $s_1$, $s_2$, and ...
0
votes
1answer
22 views

Distributing different things into groups

How to distribute four different things in two groups.. Actual question was you have four different types of animals a wolf, a monkey, a tiger and a lion and you have two cages. Find No. Of ways of ...
0
votes
0answers
8 views

How many distinct partials of order $k$ for a function $f: \mathbb{R}^{n}\rightarrow\mathbb{R}$?

Studying for the math subject GRE, and I come across the titular question. I didn't take any combinatorics or probability courses in college, and I'm realizing I have no intuition for counting. Could ...
1
vote
0answers
21 views

Counting similar pairs

I was given a simple programming assignment: Your task is to quickly find the number of pairs of sentences that are at the word-level edit distance at most 1. Two sentences S1 and S2 they are ...
0
votes
0answers
41 views

Colorings of squares divided into four colored triangles

You have to form a square by combining four isosceles right triangles of various colors, as in FIGURE shown below. Two squares are considered equally colorful if you can arrange so that the ...
0
votes
1answer
18 views

permutations combinations

Q1. Total number of permutations of k diferent things , in a row , taken not more than r at a time(each thing may be repeated any no. of times) is equal to Q2. A teacher takes 3 children from her ...
0
votes
1answer
49 views

combinatorics- persons in group

Let $$ n = \binom {k + b-2}{k-1} \text{ and }k, b\ge 2 $$ Prove that in each group of at least n persons there is k person is familiar with everybody or there are b persons two did not know each ...
0
votes
4answers
46 views

Simple Combination Help! [closed]

Alright, I'm trying to do a simple combination but seem to forget the shortcut. It is (c(6,2)+c(4,2)) over c(10,2). Now finding the answer on my calculator is easy, the problem is that I need to know ...
1
vote
0answers
11 views

How to generate list of values that sum to X given n spots where each value is unique.

For example: Given 2 spots and sum 3 the list would be {1,2} Given 2 spots and sum 4 list would be {1,3} does not contain 2 as putting 2 in both spots violates the uniqueness of each value.
5
votes
1answer
65 views

Toss a fair die until the cumulative sum is a perfect square-Expected Value

Suppose we keep tossing a fair dice until we want to stop, at which point the game ends and our score is the cumulative sum, or until the cumulative sum is a perfect square, in which case we lose and ...
0
votes
1answer
45 views

Proof involving k-permutations

For any nonnegative integers k and m satisfying $0 ≤ k ≤ m$, prove that the total number of $k$-permutations of a set of m elements is $\frac{m!}{(m − k)!}$. I have learned about by proofs by strong ...
1
vote
0answers
25 views

Time for all ants to traverse cube

Let $n$ be a positive integer, and consider a hypercube of dimension $2n$ with $2^{2n}$ points given by $(a_1,a_2,\ldots,a_{2n})$, where $a_i\in\{0,1\}$. At the beginning, an ant is at each of the ...
1
vote
0answers
25 views

the probability of existence sequence [closed]

We have n fruit that they are apple or banana. If the probability of existence apple in a specific sequence be p. What is the probability of existence a sequence of k apple in that specific sequence?
1
vote
1answer
27 views

How to generate a single instance of multichoose (stars and bars)

So we know that if I have $k$ balls and $n$ buckets, I have $\binom{n+k-1}{k}$ unique ways to allocate the balls. Let's say $n=4$ and $k=2$ then I have $\binom{5}{2}=10$ ways. All possible allocations ...
-1
votes
1answer
23 views

tasks with balls and buckets

We have p identical balls and buckets. We want to know how many ways we can deploy in these buckets. Is my solution good? Why not, why yes (please confirm)? $$ \frac {w ^ p} {p!}$$ For each ball ...
0
votes
1answer
87 views

Probability in DNA segmentation

I have formulated these questions ss part of a research in medical science (DNA segmentation): A series of $M$ identical balls is arranged on a line. A partition is formed by placing a stick to ...
-5
votes
1answer
125 views

Pixel Permutations

How many possible arrangements of pixels can a 1024x768 pixel screen display if the color of a pixel is determined by mixing 3 values: red, green, and blue, ranging from an intensity of 0 to 255? The ...
4
votes
1answer
62 views

How many integers could be in such a way that any digits is not bigger than the left digits?

How many 4-digits integers could be in such a way that any digits is not bigger than it's left digits? I Try it with simulation, i get 714. anyone could describe a formula for me? My try:
1
vote
0answers
45 views

Aumann-Shapley Uniformly Better Principle

Let $n_1,..,n_r$ be $r$ positive integers, and let $1 \leq k \leq n$, where $n=n_1+...+n_r$. Consider an urn containing $r$ different types of balls, $n_1$ balls of type 1, $n_2$ balls of type ...
0
votes
0answers
14 views

Number of ways to transform bit string of length k with j ones

Suppose we can transform any bit string $s$ of length $k$ with $j$ 1s by moving every 1 in $s$ by at most $d$ positions to the right. The resulting string $s'$ is a string of length $k+d$ where every ...
0
votes
2answers
55 views

Probability that at least 1 of the 3 bridge hands is void of clubs given… [closed]

A bridge hand is dealt so each of 4 players has 13 cards from the 52 card deck. You have 8 clubs in your hand. What is the probability that at least one of the other three hands is void in clubs?